Shapovalov A.V.

A banker learned that among identical-looking coins, one is counterfeit (lighter). He asked an expert to identify this coin using a balance scale without weights, and required that each coin participate in weighings no more than twice. What is the maximum number of coins the banker can have so that the expert can definitely identify the counterfeit one in $n$ weighings?
Let's first solve a simpler problem. Suppose the banker allows placing coins on the scales no more than once. From what largest number of coins can a lighter one be identified in $k$ weighings?

If at some weighing there are more than one coin on the scale, it will not be possible to identify the fake coin (you cannot weigh a coin a second time!). Therefore, at each weighing, only one coin is placed on each pan.

If the scales are not in balance, the fake coin is obvious. If they are in balance, the number of suspicious coins decreases by 2. Therefore, with $k$ weighings, one can identify the fake coin from $2k + 1$ coins.

Returning to the original problem, let's denote the answer as $f(n)$. Suppose that in the first weighing, there are $s$ coins on each pan. If the scales are not in balance, it will be necessary to find the fake coin among $s$ coins, and only $n-1$ weighings remain. According to the proven result, $s \leq 2(n-1) + 1 = 2n - 1$.

If the scales are in balance, we get the original problem for the coins that did not go on the scales (there are $f(n) - 2s$ of them) and $n-1$ weighings, so

$$
f(n) - 2s \leq f(n-1)
$$

Therefore,

$$
f(n) \leq f(n-1) + 2s \leq f(n-1) + 2(2n - 1)
$$

Thus,

$$
f(n) \leq 2(2n - 1) + 2(2n - 3) + \ldots + 2 \cdot 3 + f(1)
$$

Since it is easy to check that $f(1) = 3$, we have $f(n) \leq 2n^2 + 1$ by the formula for the sum of an arithmetic progression.

On the other hand, if there are $2n^2 + 1$ coins and each time $s$ is taken to be maximal, i.e., $s = 2n - 1$ on the first step, $s = 2n - 3$ on the second, and so on, the expert will be able to identify the fake coin. Therefore, $f(n) = 2n^2 + 1$.

## Invariants  Derivative at a Point  Complexity: $5+$  Problem 107841 Topics:  Classes: 10,11  [Division of Polynomials with Remainder. GCD and LCM of Polynomials]  [Complex Numbers Help Solve the Problem.]

Author: Evokkimov $M$.

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) = 2x - 1$, and since we can add 1 and multiply the resulting expression $2x$ 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 from $f_{1}$ and $f_{3}$ using the specified operations 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.