6. 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?

## 9 t h g r a d e
6. 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 be impossible to identify the fake coin (since we 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 $2 k+1$ coins.

Returning to the original problem, let's denote the answer as $f(n)$. Suppose that at the first weighing, there are $s$ coins on each pan. If the scales are not in balance, then we need to find the fake coin among $s$ coins, and each of them can only be used once, with $n-1$ weighings remaining. By the proven result, $s \leqslant 2(n-1)+1=2 n-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)-2 s$ of them) and $n-1$ weighings, so

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

From this,

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

Therefore,

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

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

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

## 9 t h g r a d e