Zkov G.

A bank serves a million customers, the list of whom is known to Ostap Bender. Each has a six-digit PIN code, and different customers have different codes. In one move, Ostap Bender can choose any customer he has not yet chosen and peek at the digits of the code at any $N$ positions (he can choose different positions for different customers). Ostap wants to find out the code of the millionaire Koreiko. For what smallest $N$ can he guarantee to do this?
It is not difficult to do when $N=3$. Since any combination of the first three digits occurs exactly 1000 times, by looking at these digits for everyone except Koreiko, Bender will know them for Koreiko as well. Then it is sufficient to look at the last three digits of Koreiko's code.

We will prove that when $N<3$, it is impossible to reliably determine Koreiko's code $K$. For each of the 6 positions, choose a code that differs from $K$ only in that position. The corresponding digit in the chosen code will be called bad. Suppose Bender is unlucky, and on the first check of a non-Koreiko code, he gets the chosen code, but does not check the bad digit (there are four unchecked positions, so a code with a bad digit in one of these positions could have been selected). Suppose the same happens on the second and third checks of non-Koreiko codes (there are four unchecked positions, and of the four chosen codes with bad digits in these positions, no more than two have been previously checked, so such a code could have been selected). When all codes have been checked, we will see which $N<3$ positions have been checked in code $K$. Among the four unchecked positions, at least one coincides with the position of the bad digit in one of the three checked chosen codes - code $L$. But if $L$ and $K$ are swapped, the results of all checks will not change. Therefore, Bender will not be able to distinguish $L$ from $K$.

## Answer

When $N=3$.