Solution

See the solution of problem 107986.

Answer

12 or 13 friends.

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

–

Solution

Solution 1

Amongst the given numbers there must be at least one positive number as if all 25 numbers were negative then their sum would also be negative which would contradict the conditions given. In a similar way we can prove that no fewer than 22 of the numbers in the group must be positive – but for the proof we need only one such number. Take this number and place it to one side. Consider the 24 remaining numbers. Split these into groups of 4 at random. All of these groups must be positive by definition. The sum of all 25 numbers is equal to the sum of all of the groups and the single known positive number. Therefore, since the sums of all 4 groups and the positive term is positive, the sum of all 25 numbers must also be positive.

Solution 2

If the sum of any 4 of the numbers is positive, then the sum of any 24 numbers must also be positive. There are only 25 combinations of 24 numbers. If we sum all 25 combinations, we get $24 \times$ the sum of all 25 numbers which is greater than 0 – each number is excluded from the group of 24 only once, so occurs in the sum 24 times. It follows therefore that the sum itself is also greater than 0.

Hint

–

Solution

a) Consider a graph with 4 vertices $A, B, C, D$ that corresponds to people, and edges connecting them that correspond to a common language. The conditions given mean that any three vertices are connected by at least two edges. It remains to prove that there are two edges that do not share a vertex; assume this is not true.

Scenario 1: If in the group of 3 $(A, B, C)$ the edges $AB$ and $AC$ are present then the edges $BD$ and $CD$ do not exist. But then the group of 3 $(B, C, D)$ would not have a shared vertex. This is a contradiction.

Scenario 2: There are a total of 4 possible groups of 3. Each edge connects two of these groups. Therefore there are no fewer than $4 \times 2 \div 2=4$. On the other hand, each edge must have a corresponding ‘missing’ edge. Therefore there are no more than 3 edges. This is a contradiction.

c) Take two people, who have a common language. Divide the remaining 100 people, as in part b$)$ into groups of 4. From a) we get that it is possible to split every group of 4 into two pairs with a common language.

Hint

–

Solution

See problem 60299.

Hint

–

Solution

Split the 100 people into 50 pairs, such that each pair sits opposite one another around the table. It is clear that in at least one of these pairs, both ‘slots’ will be filled by men.

Hint

–

Solution

See problem ID 30599.

Hint

–

Solution

Consider all of the possible groups of three members. The sums of the ages of all of the possible groups is $15 \times 332$, as each member of the group occurs in $\frac{3}{7}$ of the 35 possible groups. Therefore there must be a group of three whose combined age is no less than $\frac{15 \times 332}{35}$, which is greater than 142.

Hint

–