| $\left[\begin{array}{l}{[\text { Theory of algorithms (other) }}\end{array}\right]$ |
| :--- |
| $\left[\begin{array}{l}\text { Identical transformations }\end{array}\right]$ |
| $\left[\begin{array}{l}\text { Induction (other) }\end{array}\right]$ |
| $\left[\begin{array}{l}\text { Processes and operations }\end{array}\right]$ |

Petya bought a microcalculator at the "Turing Machines and Other Computing Devices" store, which can compute $x y + x + y + 1$ for any real numbers $x$ and $y$ and has no other operations. Petya wants to write a "program" to compute the polynomial $1 + x + x^2 + \ldots + x^{1982}$. By "program," he means a sequence of polynomials $f_{1}(x), \ldots, f_{n}(x)$ such that $f_{1}(x) = x$ and for any $i = 2, \ldots, n$, $f_{i}(x)$ is a constant or

$f_{i}(x) = f_{j}(x) \cdot f_{k}(x) + f_{k}(x) + f_{j}(x) + 1$, where $j < i, k < i$, and $f_{n}(x) = 1 + x + \ldots + x^{1982}$.

a) Help Petya write the "program".

b) Can a "program" be written if the calculator has only one operation $x y + x + y$?
a) Let $\varphi(x, y)=x y+x+y+1=(x+1)(y+1)$.

The polynomial $x-1$ is computed by the program $P(x-1): x,-3 / 2,-3, \varphi(-3 / 2, x)=-1 / 2(x+1), \varphi(-3,-1 / 2(x+1))=$ $-2(1 / 2-x / 2)=x-1$

From this, it follows that if there is a program for computing the polynomial $g(x)$, then there is also a program for computing the polynomial $g(x)-1$.

The program $P\left(f_{n}\right)$ for computing the polynomial $f_{n}(x)=1+x+\ldots+x^{n}$ is constructed inductively using "Horner's scheme":

$$
\left.P(x-1), \ldots, f_{n-1}, P\left(f_{n-1}-1\right), \varphi\left(f_{n-1}-1, x-1\right)=x f_{n-1}=f_{n}-1,0, \varphi\left(f_{n-1}, 0\right)\right)=f_{n}
$$

b) Let $g_{1}, g_{2}, \ldots, g_{n}$ be an arbitrary program. We will prove by induction that if $g_{n}$ is not a constant, then $g_{n}(-1)=-1$.

Base case. $g_{1}(x)=x$.

Inductive step. $g_{n}=g_{i} g_{j}+g_{i}+g_{j}(i, j<n)$, and, for example, $g_{i}$ is not a constant. Then $g_{i}(-1)=-1$ and $g_{n}(-1)=-$ $g_{j}(-1)-1+g_{j}(-1)=-1$.

If $f(x)=1+x+x^{2}+\ldots+x^{1982}$, then $f(-1)=1$. Therefore, a program for computing $f(x)$ does not exist. Comment

![](https://cdn.mathpix.com/cropped/2024_05_06_caf98da37e6d9925b347g-21.jpg?height=172&width=2038&top_left_y=980&top_left_x=-1)

What is the smallest number of weights in a set that can be divided into 4, 5, and 6 equal-mass piles?

## Solution

First, we will prove that there cannot be fewer than eleven weights in the set. Suppose this is not the case, i.e., there are no more than ten weights. Let $60 m$ be the total mass of all the weights in the set. First, note that the set cannot contain weights with a mass greater than $10 m$ (since the set can be divided into six piles of $10 m$ each). Therefore, each of the five piles of $12 m$ must contain at least two weights. Therefore, there are at least ten weights in total. This means there are exactly ten weights, and each of the five piles of $12 m$ consists of exactly two weights. When we divide these ten weights into six piles, there will be at least two piles with one weight each. Therefore, there are at least two weights with a mass of $10 m$. This means there are at least two weights with a mass of $2 m$ (weights that lie in the same piles of $12 m$ as the weights with a mass of $10 m$). Clearly, there cannot be four weights with a mass of $10 m$.

Suppose there are three weights with a mass of $10 m$. Then there are at least three weights with a mass of $2 m$. The remaining four weights together have a mass of $24 m$. In three piles of $15 m$, there is one weight of $10 m$ each, and there must be one of the remaining four in each (since it is impossible to make $15 m$ from weights of $10 m$ and $2 m$). This means that three of these four have a mass of no more than $5 m$, so the last one has a mass of at least $24 m-15 m=9 m$. This means it has a mass of exactly $9 m$, otherwise there would be four weights with a mass of $10 m$. There is a pile of $10 m$ where the weights of $9 m$ and $1 m$ lie. The remaining two will have a total mass of $14 m$, but each weighs no more than $5 m$. Contradiction.

Suppose there are two weights with a mass of $10 m$. Then four piles of $10 m$ contain exactly two weights each. There are two weights with a mass of $2 m$ (forming piles of $12 m$ with weights of $10 m$). This means there are two weights with a mass of $8 m$ (forming piles of $10 m$ with weights of $2 m$). Further, there are two weights with a mass of $4 m$ (forming piles of $12 m$ with weights of $8 m$), and there are two weights with a mass of $6 m$. We get that all weights have a mass of $2 k m$. But it is impossible to form a pile of $15 m$ from them. Contradiction.

It remains to prove that there is a set of eleven weights. For example, a set of weights with masses 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 10 grams fits. We leave the verification that this set can be divided into 4, 5, and 6 equal-mass piles to the reader as an exercise.