Solution

We have 70 Mercedes cars and 30 ‘other’ cars. We are given that next to a given Mercedes car there can either be another Mercedes car of the same colour, or an ‘other’ car. The more Mercedes cars are parked in pairs the fewer ‘other’ cars we need. But there are 35 pairs of Mercedes cars, so to wrap them we need at least 33 ‘other’ cars. If the Mercedes cars are not all parked in pairs then we would need even more ‘other’ cars. But we are given that there are only 30 ‘other’ cars, meaning we can only have at most 32 pairs of cars. Therefore there must be a group of 3 Mercedes cars of the same colour somewhere along the road.

Hint

–

Solution

See the solution of problem 107986.

Answer

12 or 13 friends.

Hint

–

Solution

Let us represent the product of an arbitrary pair $(a, b)$ from the numbers given as the square of a natural number multiplied by prime factors to the first power, for example, if $a=2^{13} \times 3^4 \times 19^3, \ b=5^6 \times 7^7 \times 19$ then $ab=K^2 \times 2 \times 7$ where $K= 2^6 \times 3^2 \times 5^3 \times 7^3 \times 19^2$.

Compare the number of possible pairs $(a, b)$ and the number of possible combinations of prime factors. The total number of possible pairs from 48 numbers is equal to $^{48}C_2=1128$, and the total number of combinations possible from 10 prime factors, including an empty combination, is $2^{10}=1024$. Since $1128>1024$ there will be two different pairs $(a, b)$ and $(c, d)$ from the group that have the same combination of prime factors $(p_1, p_2, …, p_k)$ present $(0 \le k \le 10)$. Hence $abcd$ must be a perfect square.

If in this situation $(a, b)$ and $(c, d)$ do not share an element then the numbers $a, b, c, d$ are the ones required. If there is a shared element, for example $b=d$, then $ac$ must be a perfect square.

If we ignore $a$ and $c$ for a moment, we are left with a group of 46 numbers, the product of which has no more than 10 prime factors. Using the same reasoning as above, we get that $^{46}C_2=1035 > 2^{10}$, and that there must exist two different pairs $(x, y)$ and $(z, t)$ from the group, so that $xyzt$ is a perfect square. If $(x, y)$ and $(z, t)$ do not share an element, then $x, y, z, t$ are the numbers required. If they do, for example $x=t$, then $yz$ must be a perfect square. In this case the required group of 4 numbers would be $(a, c, y, z)$.

Answer

Comparable to problem 79488

Hint

–

Solution

Consider the original set of 1986 numbers grouped singly, in pairs, groups of 3, and son on. In total there are $2^{1986}-1$ such possible groups. We will take the numbers in each group, multiply them together and express the product in the form of the largest possible square number multiplied by some prime factors – for example $2^{16} \times 3^{15} \times 5^{13} \times 17^9 = (2^8 \times 3^7 \times 5^6 \times 17^4 )^2 \times 3 \times 5 \times 7$ and $2^{16} \times 13^{10} = (2^8 \times 13^5 )^2$. For each of the groups assign the set of prime factors created when the product of each group is divided by the largest square factor, so for the previous examples the first would have 3, 5, 7, and the second set would be empty. The number of different possible groups from 1985 prime factors is equal to $2^{1985}$, which is less than the $2^{1986}-1$ groups possible from the original numbers. Therefore some two groups $A$ and $B$ will correspond to the same set of prime factors, that is $A = a^2p_1p_2 …p_k, B=b^2p_1…p_k$.

Therefore the product $AB$ will give a perfect square $C$. Furthermore, $AB$ is equal to the product of the numbers in group $A$ and the numbers in group $B$. By throwing out from group $A$ and $B$ any numbers which occur in both, which will multiply to give a perfect square, we get that the product of the remaining numbers will also be a perfect square.

Hint

–

Solution

Notice that amongst the given numbers at least two are greater than 1 – if 99 of the numbers are 1 then the 100th number must be 101 which contradicts the conditions given in the problem. Therefore it must be possible to divide the 100 numbers into two groups of 50 so that the sum of the numbers in each group is greater than 50.

From problem 103964 we get that it is possible to choose several numbers from each group whose sum is a multiple of 50. However no sum from either of the groups can equal 150 or 200. Therefore the sum from one of the groups is equal to 100, or the sum from both groups is equal to 50. In both cases we will have found a group of numbers whose sum is equal to 100, as required.

Hint

–

Solution

Let n denote the number of removed pairs of teeth $($in our case, n = 6$)$. Then each gear has $n^2$ – n + 2 teeth $($in our case 32$)$. In total, there are $n^2$ – n + 1 such rotations of the top gear relative to the bottom gear, in which all the teeth of both gears are aligned. We call a hole the place on the gear where there is no tooth. Consider an arbitrary hole in the bottom gear. At n – 1 positions of the top gear $($except the original one$)$, above this hole is a hole on the upper gear. But there are n holes on the bottom gear, so out of $n^2$ – n + 1 turns of the top gear only for no more than n$($n – 1$)$ of them do the holes of both gears coincide. Since $(n^2 – n + 1) – n(n-1) $ = 1, there is such a rotation of the upper gear, when no holes will coincide. This turn is the desired one.

Hint

–

Solution

Note that

By searching, we can find on the board a pair of numbers, where a $<$b, whose arithmetic mean is equal to the geometric mean of the remaining pair of numbers c and d. Below we shall prove that such a partition is unique $($up to a permutation of equal numbers$)$, therefore a = x - y, b = x + y, and hence

we can prove uniqueness. If in the equation,

two unequal numbers from different parts of the equation are exchanged, then the equality is violated: one of the parts will increase and the other will decrease. It is also impossible to change pairs entirely: a negative number cannot stand under the root, and if all the numbers are nonnegative, then

and the equality is achieved only when all four numbers are equal, which is impossible as: x + y$>$x – y.

Answer

Years 8-9 6 points, years 10-11 5 points.

Hint

–

Solution

See problem number 34976.

Answer

$½$.

Hint

–

Solution

See question 105180.

Answer

Both a$)$ and b$)$ can be done

Hint

–

Solution

Consider four counters lying in a row. By condition, among them there can not be more than one three-point counter, more than two two-point counters and more than two one point counters. If in this case there are two two-point counters in the four, then between them there are two counters, one of which is a three-point counter: the one point counters can not lie beside each other. Thus, among any four counters lying in succession, there is exactly one three point counter.
Since 101 = $4 \times 25$ + 1, then there are either 25 or 26 three-point counters. Examples: for 25 counters: 1, 3, 1, 2, 1, 3, 1, 2, …, 1, 3, 1, 2, 1; for 26 counters: 3, 1, 2, 1, 3, 1, 2, 1, …, 3, 1, 2, 1, 3.

Answer

25 or 26.

Hint

–

Hint

For each column there will always be at least two of the fractions whose digits coincide in that column.

Solution

Write out the 11 fractions one above the other so that each column is in the same position for each decimal. Each column now contains 11 digits, therefore each must contain at least one digit at least twice. Let the two decimal fractions containing the same digit in this column be numbered as the $k$th and the $m$th fractions. In this way each column in the decimals has a pair of numbers from 1 to 11 corresponding to it, equal to the values of $k$ and $m$ for that columm. Since the number of possible pairs of these 11 numbers is finite, but the number of columns $($decimal places of all the decimals$)$ is infinite and at least one of the pairs $(k_0, m_0)$ occurs in an infinite number of columns. This means that the decimal fractions with the numbers $k_0$ and $m_0$ coincide in an infinite number of columns, as required.

Hint

For each column there will always be at least two of the fractions whose digits coincide in that column.

Solution

We will prove by induction that if out of the numbers from $1$ to $2n-2$ $(n \geq 3)$ we choose $n+1$ different numbers, it is always possible to choose three numbers so that the sum of two of them is equal to the third.

Base case: for $n=3$, the statement is obviously true. We have the numbers 1 to 4, of which 4 are chosen, so we can always choose $1+2=3$

Induction step:

Assume that the statement is true for $n=k$

Consider the case $n=k+1$.

If $k+1$ of the given numbers lie between $1$ and $2k$ then the assumed case applies so is true. If this is not the case then the numbers $2k-1$ and $2k$ will always be among the numbers given. The remaining $k$ given values lie in the range $1$ to $2k-2$. If we divide this range into pairs $ (1, 2k-2), (2, 2k-3),…,(k-1, k)$ we get that one of the pairs contains two numbers that we are given. This pair however has a sum of $2k-1$.

Therefore if the statement is true for $n=k$ then it is true for $n=k+1$. As it is true for $n=3$ then by induction it is true for all $n \geq 3$ – including the case where $n=1001$ given in the problem.

If we replace 1002 with 1001 the statement ceases to be true. A counter-example could be the group of given integers $1000, 1001,…,2000$

Hint

–

Solution

Arrange the given numbers from smallest to largest and split them into groups based on the digit in their ‘tens’ column. The number $m$ of such groups satisfies the inequality $6 \le m \le 10$. Among the $m$ groups there will be a group $A_6$ which contains at least 6 numbers. Analogously, using proof by contradiction, we can show that the groups $A_5, …, A_1$ also exist. We can take the first number from $A_1$, the second from $A_2$ so that its unit digit differs from that of the number in A_1, and so on, giving us the required 6 numbers.

Hint

–

Solution

Consider the largest odd divisors of the selected numbers. The numbers from 1 to 2n have exactly n distinct largest odd divisors $($numbers 1, 3, …, 2n – 1$)$. So, two of the selected numbers have the same largest odd divisors. This means that the two chosen numbers differ only in that the factor 2 enters into them in different degrees. The greater of them is divided into smaller.

Hint

–

Hint

Divide all the numbers into pairs of adjacent numbers.

Solution

Let us divide all of the numbers into 25 adjacent pairs $1-2, 3-4, …, 49-50$ If in each pair no more than one number was chosen, there would be no more than 25 numbers chosen in total. However the question states that 26 numbers are chosen. This means, for one of the pairs, both of the numbers in the pair are chosen. This pair therefore constitutes the pair of numbers chosen whose difference is 1.

Answer

Yes.

Hint

Divide all the numbers into pairs of adjacent numbers.

Hint

All cells of a square of size $n \times n$ can be divided into non-intersecting groups of four cells, which are combined by rotations around the centre of the square. In the key-stencil, exactly one cell from each group should be cut out.

Solution

All cells of a square of size $n \times n$ can be divided into non-intersecting groups of four cells. We will assign cells to the same group, if at each turn of the square before its self-alignment each cell moves to the location of another cell in the same group. The total number of such groups will be $n^2$/4. When the stencil is applied to the square, exactly one cell from each group will appear under its cut-outs. We associate an ordered set of all cells with each stencil from such groups that appeared under the cut-outs of the stencil when it was placed on the square with the marked side up. There are $n^2$/4 such cells $($one in each group$)$, hence, in total, there are $4^{n^{2/4}}$ of these sets.

Answer

$4^{n^{2/4}}$.

Hint

All cells of a square of size $n \times n$ can be divided into non-intersecting groups of four cells, which are combined by rotations around the centre of the square. In the key-stencil, exactly one cell from each group should be cut out.

Hint

If three vertices of a regular pentagon are painted, then they lie on the vertices of an isosceles triangle.

Solution

Let’s split all of the vertices of the regular 5000-gon into 1000 groups of five vertices, located on 999 consecutive vertices. The points in each group are the vertices of a regular pentagon. There are 2001 = $2 \times 1000$ + 1 painted vertices, therefore, at least three vertices are coloured in a certain group. But every three vertices of a regular pentagon lie at the vertices of an isosceles triangle.

Answer

Compare with problem number 35758.

Hint

If three vertices of a regular pentagon are painted, then they lie on the vertices of an isosceles triangle.

Hint

Consider the figures that complement the given 100 figures to complete the square.

Solution

Denote the given 100 figures as $A_{1}$, $A_{2}$,…, $A_{100}$, and their areas as $S_{1}$, $S_{2}$,…, $S_{100}$, respectively. By the condition, $S_{1}$ + $S_{2}$ + … + $S_{100}$$<$99. Let us denote by $B_{i}$ a figure that complements the figure $A_{i}$ to complete the square $($that is, it consists of all points of the square that do not belong to the figure $A_{i}$$)$. Then the area of the figure $B_{i}$ is 1-$S_{i}$ $($for i = 1,2,..., 100$)$. Then the sum of the areas of the figures $B_{1}$, $B_{2}$, ..., $B_{100}$ is $($1-$S_{1}$$)$ + $($1-$S_{2}$$)$ + ... + $($1-$S_{100}$$)$ = 100 - $($$S_{1}$ + $S_{2}$ + ... + $S_{100}$$)$, which is less than 1. So, the sum of the areas of the figures $B_{1}$, $B_{2}$,..., $B_{100}$ is less than the area of the square. This means that there is a point in the square that does not belong to one of the figures $B_{1}$, $B_{2}$,..., $B_{100}$. Therefore, this point belongs to each of the figures $A_{1}$, $A_{2}$,..., $A_{100}$.

Hint

Consider the figures that complement the given 100 figures to complete the square.

Solution

The events “the second coin shows heads more than the first” and “the second person’s coin shows tails more than the first’s” are, obviously, equiprobable. But they also complement each other $($since the second person tossed the coin exactly one time more than the first, there are either more heads or tails, but not both$)$. Therefore, the probability of each event is ½.

Answer

½.

Hint

–

Solution

Assume that 57 such two-digit numbers can be found. Then in each pair of the form $(n, 100-n)$, where $n$ has a value of between 10 and 49 inclusive, no more than one number is chosen. There are 40 such pairs, therefore between 10 and 90 there can be no more than 41 numbers chosen – we can also choose 50. This leaves 9 numbers from 91 to 99 therefore we have chosen 50 numbers in total. However, we assumed that we could choose 57 such numbers which is a contradiction. Therefore our assumption was false.

Answer

No, it is not possible.

Hint

–