Pooolish A.

Chichikov is playing with Nozdryov. First, Nozdryov distributes 1001 nuts into three boxes. After looking at the distribution, Chichikov names any integer \( N \) from 1 to 1001. Then Nozdryov must, if necessary, move one or several nuts to an empty fourth box and present Chichikov with one or several boxes, where the total number of nuts is exactly \( N \). As a result, Chichikov will receive as many dead souls as the number of nuts Nozdryov moved. What is the maximum number of souls Chichikov can guarantee for himself, regardless of how Nozdryov plays?
Upper Bound. By placing 143,286 = 2 * 143 and 572 = 4 * 143 nuts in the boxes, Nozdryov can, for any N, move no more than 71 nuts. Indeed, N can be represented as 143k + r, where 0 ≤ k ≤ 7, and -71 ≤ r < 71. The number 143k can be collected with one or several boxes without moving anything. If r < 0, then 1001 - N = 143(7 - k) - r. By moving r nuts, we will get several boxes with 1001 - N nuts. Then, in the remaining boxes, there will be N nuts, which we will present.

Lower Bound. We will show that for any arrangement, there is an N that will require moving at least 71 nuts. Let x, y, and z be the number of nuts in the boxes. The six numbers x, y, z, x + y, x + z, y + z divide the large interval [0, 1001] into seven smaller intervals (some of which may be degenerate). Among them, there is an interval of length at least 1001 / 7 = 143. On this interval, there is an integer that is at least 71 units away from the endpoints of the interval. Without moving any nuts, we can only obtain sets where the total number of nuts lies at the end of one of the seven smaller intervals. To change this number by r, we need to move at least r nuts.

## Answer

71 souls.

Author: $\underline{\text{Golovanov A.S.}}$

Find all natural numbers $k$ such that for each odd $n > 100$, the number $20^n + 13^n$ is divisible by $k$.

## Solution

For any odd $n$, the number $20^n + 13^n$ is divisible by $20 + 13 = 33$. Therefore, if $k$ is a divisor of 33, the condition is satisfied. We will prove the converse.

First Method. The numbers $A = 20^{101} + 13^{101}$ and $B = 20^{103} + 13^{103}$ are divisible by $k$. Therefore, the numbers $20^2 A - B = (400 - 169) \cdot 13^{101} = 231 \cdot 13^{101}$ and $B - 13^2 A = 231 \cdot 20^{101}$ are also divisible by $k$. Since $\gcd(231 \cdot 20^{101}, 231 \cdot 13^{101}) = 231 = 7 \cdot 33$, 231 is divisible by $k$.

On the other hand, $20^n + 13^n = (20^n - 13^n) + 2 \cdot 13^n$. The first term is divisible by $20 - 13 = 7$, but the second term is not. Therefore, $k$ is a divisor of 231 and does not divide 7; hence, $k$ is a divisor of 33.

Second Method. Note that $1 = \gcd(20^{101}, 13^{101}) = \gcd(20^{101} + 13^{101}, 20^{101})$ divides $\gcd(20, k)$. Therefore, $\gcd(20, k) = 1$. Similarly, $\gcd(13, k) = 1$.

According to the remark to problem $\underline{73597}$, the numbers $20^u - 1$ and $13^v - 1$ are divisible by $k$ for some natural numbers $u$ and $v$. Consider an odd number $n > 100$ such that $n - 1$ is divisible by $uv$ (for example, $n = 1 + 100uv$). Then the number $(20^n + 13^n) - 33 = 20(20^{n-1} - 1) + 13(13^{n-1} - 1)$ is divisible by $k$. Therefore, 33 is divisible by $k$.

## Answer

$k = 1, 3, 11, 33$.