Andjans A.
$N$ friends simultaneously learned $N$ pieces of news, with each person learning one piece of news. They started calling each other and exchanging news.
Each call lasts 1 hour. Any number of news items can be shared in one call.
What is the minimum number of hours required for everyone to learn all the news? Consider three cases:
a) $N=64$,
b) $N=55$,
c) $N=100$.
a) A piece of news known to one of the friends will be known to no more than two (including the first) after 1 hour, no more than four after the second hour, ..., and no more than 32 after the fifth hour. Therefore, it will take no less than 6 hours.

We will show that 6 hours are sufficient. The conversations can proceed according to the following scheme. Number the participants with six-digit binary numbers. In the $k$-th hour, people whose numbers differ only in the $k$-th digit converse (for example, in the 3rd hour, $a b c 0 d e$ converses with $a b c 1 d e$). Each hour, the number of pieces of news known to each person doubles. (For example, after the 2nd hour, each person knows four pieces of news known to four participants whose numbers differ from his number in the first two digits.)

Remark. This method of conversation is only suitable for powers of two. Below is a method that works for any even numbers.

b) That 6 hours are insufficient is evident from a). We will show that 7 hours are sufficient. Number the participants with elements from $\mathbf{Z}_{50} \times\{-1,1\}$. In the 1st hour, the participant with number $(x, y)$ converses with $(x,-y)$, in the 2nd hour with $(x+1,-y)$, in the 3rd hour with $(x+3,-y)$, and so on. The number of pieces of news each friend knows doubles each hour (except the last). (Number the pieces of news the same way as the friends who know them at the beginning. After the 1st hour, the participant with number $(0,0)$ knows all pieces of news with $x=0$, after the 2nd hour, all pieces of news with $x=0,1$, after the 3rd hour, all pieces of news with $x=0,1,2,3$; and so on.)

b) In the first hour, one of the participants does not converse with anyone. As seen from a), the others will need at least 6 more hours to learn his news.

Divide the participants into two groups: 32 and 23 people. In the 1st hour, all members of the second group converse with members of the first. Over the next 5 hours, the members of the first group exchange news (according to the scheme from a) or b); as a result, each knows all the news). In the last hour, they inform the members of the second group of all the information.

## Answer

a) 6 hours, b) 7 hours, c) 7 hours. On the board, three functions are written: $f_{1}(x)=x+1 / x, f_{2}(x)=x^{2}, f_{3}(x)=(x-1)^{2}$. You can add, subtract, and multiply these functions (including squaring, cubing, ...), multiply them by any number, add any number to them, and perform these operations on the resulting expressions. Obtain the function $1 / x$.

Prove that if any of the functions $f_{1}, f_{2}, f_{3}$ is erased from the board, it is impossible to obtain $1 / x$.

## Solution

Since $f_{2}(x)-f_{3}(x)=2 x-1$, and since we can add 1 and multiply the resulting expression $2 x$ by $1 / 2$, we can obtain the function $x$. Subtracting it from $f_{1}(x)$, we get $1 / x = f_{1}(x) - 1 / 2 (f_{2}(x) - f_{3}(x) + 1)$.

Since the division operation is not allowed, it is impossible to express $1 / x$ using only the functions $f_{2}$ and $f_{3}$: if you multiply and add polynomials, you will get polynomials again, and the function $1 / x$ is not a polynomial. The derivatives of the functions $f_{1}$ and $f_{3}$ at the point $x=1$ are 0. If the derivatives of two functions at the point 1 are 0, then the derivative of both their sum and their product is 0. So, all functions that can be obtained using the specified operations from the functions $f_{1}$ and $f_{3}$ have a zero derivative at the point 1. The derivative of the function $1 / x$ at the point 1 is not 0.

All our functions are defined for all complex $x \neq 0$. If we substitute $x=i$ into $f_{1}$ and $f_{2}$, we get $i + i^{-1} = 0, i^{2} = -1$ - real numbers. This means that each of the functions obtained from $f_{1}$ and $f_{2}$ will have a real value at the point $i$. And it is impossible to express the imaginary number $f_{3}(i) = -2i$ using only real numbers.