8,9,10,11 |

Authors: Shapovalov A.V., Knop K.A.

To pass the test, a thousand sages form a column. One of the caps numbered from 1 to 1001 is hidden, and the rest are put on the sages in random order. Each sage can only see the numbers on the caps of all those in front of them. Then, starting from the back to the front, the sages call out integers. Each number must be between 1 and 1001, and no number that has already been said can be repeated. The test result is the number of sages who correctly name the number on their own cap. The sages knew the conditions of the test in advance and could agree on how to act.

a) Can they guarantee a result of more than 500?

b) Can they guarantee a result of at least 999?
a) Let the last sage name the remainder of the division by 1001 of the sum of the numbers he sees (naming 1001 if the remainder is 0). Then the next one can calculate his number by subtracting the sum of what he sees from the named number. This continues until someone's calculated number matches what the last one named. This unlucky one instead of his number will name the number of the foremost sage. By agreement, the others will understand that he meant the number of the last one, and will act accordingly. In the end, all sages will answer correctly, except possibly the last one, the unlucky one, and the foremost.

b) Let the hidden hat lie behind the back of the last sage. Then the hat numbers form a permutation. The last one does not see two numbers, and there are two possible arrangements for them. In one of the arrangements, the permutation is even (and in the other - it is not). According to this arrangement, the last one names his number (with a 50% chance of being wrong). In the resulting even permutation, the second from the back does not know the arrangement of only two numbers: his own and the one that, according to the first, lies behind. There are two possible arrangements of the unknown numbers, and only in one of them the permutation is even. According to this, the second correctly calculates his number. Similarly, all the others sequentially calculate their numbers. As a result, all will answer correctly, except perhaps the last one.

## Answer

They can (in both cases).
a) Out of 19 balls, 2 are radioactive. For any pile of balls, one check can determine if there is at least one radioactive ball (but not how many). Prove that in 8 checks, both radioactive balls can always be identified.

b) Out of 11 balls, two are radioactive. Prove that fewer than 7 checks cannot guarantee the identification of both radioactive balls, but 7 checks can always identify them.

## Solution

a) Note that in $n$ checks, one radioactive ball can be identified from $2^{n}$ (or fewer) balls (see problem $\underline{60907}$ a).

1) Among $n$ balls, two radioactive ones can be found in $n-1$ checks (by checking $n-1$ balls in sequence, we will know the $n$-th one without checking).
2) We will show how to identify two radioactive balls from seven in five checks. First, check a group of two balls. If the result is negative (there are no radioactive ones among them), then it remains to identify two balls from the remaining five in four checks, which is possible.

If the result is positive, check a group of four balls. If this result is negative, it remains to identify two balls from three suspicious ones (2 checks). If positive, it remains to identify one ball from two (one check) and another ball from four (another two checks).

3) We will show how to identify two radioactive balls from nine in six checks. First, check a group of two balls. If the result is negative, it remains to identify two balls from the remaining seven in five checks (see point 2).

If the result is positive, check a group of four balls. If this result is negative, it remains to identify two balls from five suspicious ones (four checks). If positive, it remains to identify one ball from two (one check) and another ball from four (another two checks).

4) We will show how to identify two radioactive balls from 13 in seven checks. First, check a group of four balls. If the result is negative, it remains to identify two balls from the remaining nine in six checks (see point 3).

If the result is positive, check a group of eight balls. If this result is negative, it remains to identify two balls from five suspicious ones (four checks). If positive, it remains to identify one ball from four (two checks) and another ball from eight (another three checks).

5) Let's return to solving the problem. Check a group of six balls. If the result is negative, it remains to identify two balls from the remaining 13 in seven checks (see point 4).

If the result is positive, check a group of eight balls. If this result is negative, check four balls from the remaining five. If this result is negative, it remains to identify two balls from seven suspicious ones in five checks (see point 2). If positive, it remains to identify one ball from six (three checks) and another ball from four (another two checks).

If the result of checking eight balls is positive, it remains to identify one ball from six (three checks) and another ball from eight (another three checks).

b) In a), it is shown that in seven checks, two radioactive balls can be identified even from 13, let alone from 11 balls. (A simpler method for 11 balls is given in the solution to problem $\underline{35794 .)}$ We will prove that six checks are insufficient.

Note that $n$ checks do not allow guaranteeing the selection of more than $2^{n}$ possible options (each check, in the "unfavorable" outcome, allows eliminating no more than half of the options; see problem $\underline{60907}$ a).

Suppose the first time we check no more than two balls and get a negative result. In the remaining five checks, it will not be possible to identify two balls from nine (the number of remaining options is the number of pairs $C_{9}^{2}>2^{5}$). Suppose the first time we check no fewer than four balls and get a positive result. There remain $\dot{C}_{11}^{2}-C_{7}^{2}=34>2^{5}$ options, and again, they cannot be "divided".

Suppose the first time we check a group of three balls and get a negative result. Now we need to identify two balls from eight in five checks. Similar estimates show that checking one or three balls is "unprofitable" $\left(C_{8}^{2}>2^{4}, C_{9}^{2}-C_{6}^{2}>2^{4}\right)$. Thus, in the second check, two balls should participate, and with a negative result, it will be necessary to identify two balls from six in four checks.

But this is impossible: checking one ball, we can leave $C_{5}^{2}=10$ options, and checking two balls, $C_{6}^{2}-C_{4}^{2}=9$ options; both these numbers are greater than $2^{3}$.

How many six-digit numbers exist in which there is at least one even digit?

## Solution

There are 900000 six-digit numbers in total (see the solution to problem $\underline{60336}$), out of which numbers with all digits odd are $5^{6}$ (see problem $\underline{60349})$. The remaining $9 \cdot 10^{5}-5^{6}$ numbers contain at least one even digit.

## Answer

$9 \cdot 10^{5}-5^{6}$ numbers.