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

Решение:

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

Рассмотрим обратный ход:

1. Если в тарелке 0 шариков, Кристина победила.
2. Предыдущее состояние могло быть:
• Добавление 5 шариков (обратная операция к вычитанию 5): если стало 0, то было 5.
• Удвоение шариков (обратная операция к делению пополам): если стало 0, то было 0.

Таким образом, чтобы прийти к 0, последняя операция должна была быть вычитанием 5 (если предыдущее число было 5). Перед этим шариком могло быть либо 10 (при делении пополам, если было чётное число) или 5 (при вычитании 5).

Давайте проследим возможные пути, начиная с 0:

• 0
• 5 (добавили 5)
• 10 (добавили 5)
• 20 (удвоили)
• 15 (вычли 5)
• 30 (удвоили)
• 25 (вычли 5)
• ...

Это сложная задача для прямого перебора. Попробуем рассуждать иначе.

Обозначим операцию \( A(n) \) — переложить ровно половину (если \( n \) чётно), \( B(n) \) — переложить 5 шариков.

Условие победы: \( N \) должно привести к 0, используя операции \( A \) и \( B \).

Ключевой момент: операция \( A \) возможна только если количество шариков чётное.

Рассмотрим числа, которые можно получить, начиная с 0:

1. \( 0 \)
2. \( 5 \) (применили \( B^{-1} \) к 0)
3. \( 10 \) (применили \( B^{-1} \) к 5)
4. \( 20 \) (применили \( A^{-1} \) к 10)
5. \( 15 \) (применили \( B^{-1} \) к 20)
6. \( 30 \) (применили \( B^{-1} \) к 15)
7. \( 60 \) (применили \( A^{-1} \) к 30)
8. \( 55 \) (применили \( B^{-1} \) к 60)
9. \( 110 \) (применили \( A^{-1} \) к 55)
10. \( 105 \) (применили \( B^{-1} \) к 110)
11. \( 210 \) (применили \( A^{-1} \) к 105)
12. \( 205 \) (применили \( B^{-1} \) к 210)
13. \( 410 \) (применили \( A^{-1} \) к 205)
14. \( 405 \) (применили \( B^{-1} \) к 410)
15. \( 810 \) (применили \( A^{-1} \) к 405)
16. \( 805 \) (применили \( B^{-1} \) к 810)
17. \( 1610 \) (применили \( A^{-1} \) к 805) ...

Числа, которые могут привести к победе, должны быть представимы в виде \( N = \alpha \cdot 2^k - 5m \) или \( N = \alpha \cdot 2^k + 5m \) где \( \alpha \) — результат применения операции \( B^{-1} \) и \( k \) — число применений \( A^{-1} \).

Рассмотрим возможные конечные состояния перед 0:

• Если последнее действие было «переложить 5», то предыдущее число было 5.
• Если последнее действие было «переложить половину», то предыдущее число было 0, что противоречит условию.

Значит, последней операцией всегда было «переложить 5». Таким образом, все числа, приводящие к победе, должны оканчиваться на 5 (если мы идем от 0 к N).

Давайте рассмотрим числа, которые могут привести к 0:

Любое число, которое мы можем получить, является результатом применения операций \( +5 \) или \( \times 2 \) к 0 (в обратном порядке). Однако, операция \( \times 2 \) требует, чтобы число перед ней было чётным. В обратном ходе, если мы имеем число, которое получилось делением на 2, то оно должно быть чётным. Но в прямом ходе, если число чётное, мы можем разделить пополам.

Важно, что если мы применяем \( +5 \) то следующее число будет \( n+5 \). Если \( n+5 \) чётно, то мы можем применить \( /2 \). Если \( n+5 \) нечётно, мы можем применить \( +5 \) снова.

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

Ключевой момент: Любое число, которое мы хотим достичь (т.е. 0), должно быть получено либо вычитанием 5, либо делением на 2. Поэтому, идя обратно от 0:

• \( 0 \)
• \( 5 \) (обратная операция к -5)
• \( 10 \) (обратная операция к -5, или \( 5 \times 2 \) если \( 5 \) было чётным, что не так)
• \( 20 \) (обратная операция к -5, или \( 10 \times 2 \))
• \( 15 \) (обратная операция к -5)
• \( 30 \) (обратная операция к -5, или \( 15 \times 2 \))
• \( 25 \) (обратная операция к -5)
• \( 50 \) (обратная операция к -5, или \( 25 \times 2 \))
• \( 55 \) (обратная операция к -5)
• \( 100 \) (обратная операция к -5, или \( 50 \times 2 \))
• \( 105 \) (обратная операция к -5)
• \( 200 \) (обратная операция к -5, или \( 100 \times 2 \))
• \( 210 \) (обратная операция к -5, или \( 105 \times 2 \))
• \( 400 \) (обратная операция к -5, или \( 200 \times 2 \))
• \( 420 \) (обратная операция к -5, или \( 210 \times 2 \))
• \( 405 \) (обратная операция к -5)
• \( 800 \) (обратная операция к -5, или \( 400 \times 2 \))
• \( 840 \) (обратная операция к -5, или \( 420 \times 2 \))
• \( 810 \) (обратная операция к -5)
• \( 1600 \) (обратная операция к -5, или \( 800 \times 2 \))
• \( 1680 \) (обратная операция к -5, или \( 840 \times 2 \))
• \( 1620 \) (обратная операция к -5)
• \( 1610 \) (обратная операция к -5)

Если число \( x \) является достижимым, то \( x+5 \) также является достижимым (если \( x+5 \) чётно, то \( (x+5)/2 \) может быть достижимо, если \( x \) достижимо). Это не совсем верно.

Правильный подход: начнем с 0 и применим обратные операции: \( +5 \) и \( \times 2 \). При этом \( \times 2 \) можно применять к любому числу, а \( +5 \) нужно применять так, чтобы следующее число стало чётным (для обратного \( /2 \)).

Давайте построим дерево достижимых чисел, начиная с 0, применяя \( +5 \) и \( \times 2 \). Нас интересуют числа \( \notin [1, 1000] \) которые в итоге приведут к 0.

Все числа, которые могут привести к победе, должны быть вида \( N \). Если \( N \) чётное, мы можем получить \( N/2 \). Если \( N > 5 \), мы можем получить \( N-5 \).

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

Любое число, приведённое к 0, должно быть в таком виде, что последовательное применение \( -5 \) или \( /2 \) (если чётное) приводит к 0.

Это эквивалентно тому, что если мы начинаем с \( N \) и применяем \( +5 \) или \( \times 2 \), мы можем получить 0. Но это неверно.

Начнём с 0 и будем применять обратные операции: \( +5 \) и \( \times 2 \). Однако, \( \times 2 \) — обратная к \( /2 \). Если мы получили число \( x \) путём \( /2 \), то \( x \) должно быть чётным. В обратном ходе, если мы применяем \( \times 2 \), то нет ограничений.

Итак, все достижимые числа, начиная с 0, с операциями \( +5 \) и \( \times 2 \) (бесконечно):

• \( 0 \)
• \( 5 \)
• \( 10 \)
• \( 15 \)
• \( 20 \)
• \( 25 \)
• \( 30 \)
• \( 35 \)
• \( 40 \)
• \( 45 \)
• \( 50 \)
• \( 55 \)
• \( 60 \)
• \( 65 \)
• \( 70 \)
• \( 75 \)
• \( 80 \)
• \( 85 \)
• \( 90 \)
• \( 95 \)
• \( 100 \)

Не все числа из этого ряда являются