Перед Кристиной на столе стоит тарелка со стеклянными шариками. Она хочет переложить все шарики из тарелки в банку, но просто так ей это делать скучно, и она решила сыграть сама с собой в игру. Она может выполнять только два действия: 1) перекладывать ровно половину оставшихся в тарелке шариков в банку, при условии, что их осталось чётное количество, 2) перекладывать ровно 5 шариков. Она будет считать себя победившей, если она сможет переложить так все шарики в банку, оставив тарелку пустой. Сколько существует чисел от 1 до 1000, для которых такое количество шариков может привести Кристину к победе?

Решение:

Пусть \( N \) — начальное количество шариков. Кристина выигрывает, если сможет опустошить тарелку, используя два действия:

1. Переложить \( \frac{N}{2} \) шариков, если \( N \) — чётное.
2. Переложить 5 шариков.

Наша цель — найти все \( N \) от 1 до 1000, для которых возможно достичь 0.

Рассмотрим различные случаи:

1. Если \( N \) — нечётное: Единственное действие, которое можно применить, — это вычесть 5. Если \( N \) изначально нечётное, то после вычитания 5 оно останется нечётным. Чтобы достичь 0, нужно, чтобы \( N \) было равно 5, 15, 25, ..., т.е. \( N \) должно оканчиваться на 5.

• Если \( N = 5 \), то 5 - 5 = 0. Кристина выиграла.
• Если \( N = 15 \), то 15 - 5 = 10. Теперь шариков стало чётно. Можно разделить пополам: 10 / 2 = 5. Осталось 5 шариков. Затем 5 - 5 = 0. Кристина выиграла.
• Если \( N = 25 \), то 25 - 5 = 20. 20 / 2 = 10. 10 / 2 = 5. 5 - 5 = 0. Кристина выиграла.

Таким образом, если \( N \) нечётное, оно должно быть вида \( 5 + 10k \), где \( k \ge 0 \). В общем виде, \( N \equiv 5 \pmod{10} \). В диапазоне от 1 до 1000 таких чисел: \( \frac{1000 - 5}{10} + 1 = \frac{995}{10} + 1 \) — здесь проблема, так как \( 995 \) не делится на 10. Правильнее: \( 1000 = 10 \times 100 \). Числа: 5, 15, ..., 995. Всего \( \frac{995 - 5}{10} + 1 = \frac{990}{10} + 1 = 99 + 1 = 100 \) чисел.

2. Если \( N \) — чётное:

• Можно сначала вычесть 5, если \( N \ge 5 \). Если \( N \) чётное, то \( N-5 \) будет нечётным. После этого мы попадаем в предыдущий случай.
• Можно сразу разделить пополам: \( N/2 \).

Попробуем рассуждать с конца. Чтобы достичь 0, последнее действие должно быть либо \( 5-5=0 \), либо \( 10/2=5 \) (если было 10 шариков, и мы сделали \( N/2 \) когда \( N=10 \)), либо \( X/2=0 \) (что невозможно, т.к. \( X \) должно быть > 0).

Пусть \( S \) — множество выигрышных начальных чисел. \( 0 \in S \) (тривиально).

Если \( x \in S \), то \( x+5 \in S \) (обратное действие к вычитанию 5).

Если \( x \in S \), то \( 2x \in S \) (обратное действие к делению на 2).

Начнем с 0:

• \( 0+5 = 5 \in S \)
• \( 2 \times 0 = 0 \in S \) (бесполезно)
• \( 5+5=10 \in S \)
• \( 2 \times 5 = 10 \in S \)
• \( 10+5=15 \in S \)
• \( 2 \times 10 = 20 \in S \)
• \( 15+5=20 \in S \)
• \( 2 \times 20 = 40 \in S \)
• \( 20+5=25 \in S \)
• \( 2 \times 40 = 80 \in S \)
• \( 40+5=45 \in S \)
• \( 2 \times 80 = 160 \in S \)
• \( 80+5=85 \in S \)
• \( 2 \times 160 = 320 \in S \)
• \( 160+5=165 \in S \)
• \( 2 \times 320 = 640 \in S \)
• \( 320+5=325 \in S \)
• \( 2 \times 640 = 1280 \) (вне диапазона)
• \( 640+5=645 \in S \)

Это генерация чисел, которые можно получить из 0. Но нас интересуют числа, которые можно свести к 0. Это эквивалентно:

Если \( N \) — чётное, то \( N \) может перейти в \( N/2 \) или \( N-5 \). Если \( N \) — нечётное, то \( N \) может перейти в \( N-5 \).

Чтобы \( N \) сводилось к 0:

1. Если \( N \) — нечётное, то \( N \) должно быть вида \( 5, 15, 25, 35, ... \) (т.е. \( N lockquote{\pmod{10}} 5 \)).

2. Если \( N \) — чётное, то \( N-5 \) должно сводиться к 0 (т.е. \( N-5 \) должно быть нечётным, вида \( 5 + 10k \)). Тогда \( N = (5+10k) + 5 = 10 + 10k \). Это означает, что \( N \) должно быть кратно 10.

НО! Есть еще вариант: если \( N \) чётное, то \( N \) может перейти в \( N/2 \). Это значит, что \( N/2 \) должно сводиться к 0.

Итак, \( N \) сводится к 0, если:

• \( N \) — нечётное и \( N lockquote{\pmod{10}} 5 \)
• \( N \) — чётное, и \( N/2 \) сводится к 0.
• \( N \) — чётное, и \( N-5 \) сводится к 0 (это случай, когда \( N \) нечётное, и \( N-5 \) нечётное, вида \( 5+10k \), значит \( N = 10k+10 \), т.е. \( N \) кратно 10).

Переформулируем: \( N \) сводится к 0, если:

• \( N lockquote{\pmod{10}} 5 \)
• \( N/2 \) сводится к 0.

Посмотрим, какие числа от 1 до 1000 можно свести к 0.

Проверим числа, кратные 10:

10: 10/2 = 5. 5-5=0. Да.

20: 20/2 = 10. 10/2=5. 5-5=0. Да.

30: 30/2 = 15. 15-5=10. 10/2=5. 5-5=0. Да.

40: 40/2 = 20. 20/2=10. 10/2=5. 5-5=0. Да.

50: 50/2 = 25. 25-5=20. 20/2=10. 10/2=5. 5-5=0. Да.

60: 60/2 = 30. ... Да.

70: 70/2 = 35. 35-5=30. ... Да.

80: 80/2 = 40. ... Да.

90: 90/2 = 45. 45-5=40. ... Да.

100: 100/2 = 50. ... Да.

Кажется, что все числа, кратные 10, подходят.

Рассмотрим число \( N \). Если \( N \) чётно, мы можем перейти к \( N/2 \). Если \( N \) нечётно, мы можем перейти к \( N-5 \). Мы хотим дойти до 0.

Любое число \( N \) можно представить в виде \( N = 2^k \times m \), где \( m \) — нечётное.

Если \( m = 5 \): \( N = 2^k \times 5 \).

При \( k=0 \): \( N=5 \). 5-5=0. (1 число)

При \( k=1 \): \( N=10 \). 10/2=5. 5-5=0. (1 число)

При \( k=2 \): \( N=20 \). 20/2=10. 10/2=5. 5-5=0. (1 число)

При \( k=3 \): \( N=40 \). 40/2=20. ... (1 число)

При \( k=4 \): \( N=80 \). ... (1 число)

При \( k=5 \): \( N=160 \). ... (1 число)

При \( k=6 \): \( N=320 \). ... (1 число)

При \( k=7 \): \( N=640 \). ... (1 число)

При \( k=8 \): \( N=1280 \) (вне диапазона).

Это 8 чисел.

Теперь рассмотрим другие нечётные \( m \). Например, \( m=1 \) (нечётное, но не 5). Если \( N \) нечётно, то \( N-5 \) — нечётное. Если \( N \) чётно, то \( N/2 \).

Если \( N \) сводится к 0, то либо \( N=5 \), либо \( N=10 \), либо \( N=20 \), ..., \( N=640 \).

Если \( N \) нечётное, оно должно быть \( 5, 15, 25, ... \).

Если \( N \) чётное, то \( N/2 \) должно сводиться к 0. Или \( N-5 \) должно сводиться к 0 (т.е. \( N-5 \) — число вида \( 5+10k \), а значит \( N \) должно быть вида \( 10+10k \), кратное 10).

Рассмотрим числа, сводимые к 0:

1. Числа вида \( 5 \cdot 2^k \): 5, 10, 20, 40, 80, 160, 320, 640. (8 чисел)
2. Числа вида \( (5+10m) lockquote{\cdot} 2^k \), где \( m lockquote{\ge} 1 \) (т.е. нечётные числа, которые не кратны 10, но заканчиваются на 5, умноженные на степень двойки).

Нечётные числа, заканчивающиеся на 5: 5, 15, 25, 35, 45, 55, 65, 75, 85, 95, ...

Нам нужно, чтобы после серии делений на 2 и вычитаний 5, мы пришли к 0.

Любое число \( N \) можно представить в виде \( N = 2^k \times m \), где \( m \) — нечётное.

Если \( N \) — нечётное, то \( N \to N-5 \). Чтобы дойти до 0, \( N \) должно быть \( 5, 15, 25, ... \).

Если \( N \) — чётное, то \( N \to N/2 \) или \( N \to N-5 \).

Если \( N \) кратно 10, то \( N=10k \). \( N/2=5k \). Если \( k \) — нечётное, то \( 5k \) оканчивается на 5. Если \( k \) — чётное, то \( 5k \) оканчивается на 0.

Рассмотрим все числа от 1 до 1000.

Выигрышные числа — это те, которые можно свести к 0.

Это числа, которые могут быть получены из 0 операциями \( x \to 2x \) и \( x \to x+5 \).

\( 0 \)

\( 0+5=5 \)

\( 2 \times 0 = 0 \)

\( 5+5=10 \)

\( 2 \times 5 = 10 \)

\( 10+5=15 \)

\( 2 \times 10 = 20 \)

\( 15+5=20 \)

\( 2 \times 15 = 30 \)

\( 2 \times 20 = 40 \)

\( 20+5=25 \)

\( 30+5=35 \)

\( 2 \times 25 = 50 \)

\( 2 \times 30 = 60 \)

\( 2 \times 35 = 70 \)

\( 2 \times 40 = 80 \)

\( 2 \times 50 = 100 \)

\( 2 \times 60 = 120 \)

\( 2 \times 70 = 140 \)

\( 2 \times 80 = 160 \)

...

Все числа, которые можно получить таким образом, будут иметь вид \( 5 \times (2^k) + 5 \times (2^{k-1}) + ... + 5 \times (2^0) \) (если последняя операция была +5) или \( 5 \times (2^k) \) (если последняя операция была \( \times 2 \)).

Это числа вида \( 5 \times \text{любое число} \) или \( \text{число, оканчивающееся на 5} \).

Если \( N \) — любое число, то оно сводится к 0, если \( N=0 \).

Мы хотим узнать, для каких \( N \in [1, 1000] \), \( N \to 0 \).

Если \( N \) — нечётное, то \( N \to N-5 \).

Если \( N \) — чётное, то \( N \to N/2 \) или \( N \to N-5 \).

1. \( N \) нечётное. \( N \to N-5 \to (N-5)/2 \) (если \( N-5 \) чётное) или \( N \to N-5 \to N-10 \) (если \( N-5 \) нечётное).

Заметим, что если \( N lockquote{\pmod{10}} 5 \) (т.е. \( N=5, 15, 25, ... \)), то \( N-5 \) будет кратно 10 (\( 0, 10, 20, ... \)).

Если \( N lockquote{\pmod{10}} 5 \) (нечётное): \( N \to N-5 \). \( N-5 \) кратно 10. \( N-5 = 10k \).

\( 10k \to 5k \).

Если \( k \) — нечётное, \( 5k \) оканчивается на 5. \( 5k \to 5k-5 \).

Если \( k \) — чётное, \( 5k \) оканчивается на 0. \( 5k \to 5k/2 \).

Числа, которые могут привести к победе: все числа, которые можно свести к 0.

Это числа, которые:

• \( N lockquote{\pmod{10}} 5 \)
• \( N \) чётное, и \( N/2 \) может привести к победе.
• \( N \) чётное, и \( N-5 \) может привести к победе (т.е. \( N-5 = 5+10k \), тогда \( N = 10+10k \), кратно 10).

Значит, выигрышные числа:

1. Числа, оканчивающиеся на 5. (100 чисел: 5, 15, ..., 995)
2. Числа, кратные 10, у которых \( N/2 \) является выигрышным числом.

Проверим числа, кратные 10:

10: \( 10/2 = 5 \). 5 выигрышное. Да.

Все числа, кратные 10, у которых \( N/2 \) сводится к 0, также подходят. Получается, что все числа, кратные 10, подходят, потому что \( N/2 \) будет либо число, заканчивающееся на 5, либо число, кратное 10 (и тогда \( N/4 \) будет число, заканчивающееся на 5, или кратное 10, и так далее, пока не дойдем до числа, кратного 5, которое делится на 2 степени).

В диапазоне от 1 до 1000:

1. Числа, оканчивающиеся на 5: 5, 15, 25, ..., 995. Количество = \( \frac{995-5}{10} + 1 = 99 + 1 = 100 \).

2. Числа, кратные 10: 10, 20, ..., 1000. Количество = \( \frac{1000-10}{10} + 1 = 99 + 1 = 100 \).

Мы должны убедиться, что нет пересечений между этими двумя группами, и все ли числа учтены.

Числа, оканчивающиеся на 5, не кратны 10.

Значит, общее количество = 100 + 100 = 200.

Проверим:

• \( N \) — нечётное. \( N \to N-5 \). \( N-5 \) — кратно 10. \( N-5=10k \). \( N = 10k+5 \). Эти числа мы посчитали (100 шт.).
• \( N \) — чётное.
• \( N \to N/2 \). Если \( N/2 \) сводится к 0, то \( N \) выигрышное.
• \( N \to N-5 \). \( N-5 \) — нечётное. \( N-5 \) должно быть вида \( 5+10m \). Тогда \( N = 10m+10 \), т.е. \( N \) кратно 10.

Все числа, кратные 10, сводятся к 0. Так как \( N = 10k \), то \( N/2 = 5k \).

Если \( k \) — нечётное, \( 5k \) оканчивается на 5. \( 5k \to 5k-5 \) (выигрышное).

Если \( k \) — чётное, \( 5k \) оканчивается на 0. \( 5k=10j \). \( 5k \to 5k/2 = 10j/2 = 5j \) (выигрышное).

Значит, все числа, кратные 10, являются выигрышными.

Итого: числа, оканчивающиеся на 5 (100 шт.) + числа, кратные 10 (100 шт.) = 200.

Ответ: 200