Русский
Двоичные палиндромы: разбор задачи 3 IMO 1988
Как решать Задачу 3?
Ответ: 92
На самом деле, правильные идеи уже были в комментариях — и это очень вдохновляет 🙂
В математике часто важен не только сам ответ, сколько путь к нему: как подумать, на что обратить внимание, какую структуру заметить. Часто ключевое — это не вычисления, а идея. А уже после неё всё выглядит почти очевидным.
Две ключевые идеи: двоичная запись и симметрия
В этой задаче таких идей две — двоичная запись и симметрия:
🧠 Двоичная запись: функция ведёт себя так, что её значения можно выразить через значения на меньших числах — часто при делении на 2 или 4. Это намекает, что f «смотрит» на число не в десятичной записи, а на его запись в двоичном виде.
🧠 Симметрия: если внимательно проследить за значениями f(n), то видно: f(n) = n тогда и только тогда, когда двоичная запись числа симметрична, то есть число n — палиндром в двоичной системе. Например: число 5 — это 101, перевернули — снова 101, значит f(5) = 5. Число 6 — это 110, перевернули — 011, то есть f(6) ≠ 6
Задача сводится к поиску двоичных палиндромов
📌 Значит, задача сводится к следующему:
Найти все положительные числа n ≤ 1988, у которых двоичная запись — палиндром. Именно для них будет f(n) = n.
Подсчёт двоичных палиндромов до 1988
На этом месте идеи заканчиваются и дальше нужно только считать. Для чисел длины m бит, количество двоичных палиндромов — это 2 в степени (m-1)/2 (округляем вверх). Если посчитать по длинам:
- от 1 до 2: 1 число
- от 2 до 4: 1 число
- от 4 до 8: 2 числа
- от 8 до 16: 2 числа
- от 16 до 32: 4
- от 32 до 64: 4
- от 64 до 128: 8
- от 128 до 256: 8
- от 256 до 512: 16
- от 512 до 1024: 16
Осталось посчитать, сколько симметричных чисел между 1024 и 1988.
Число 1988 в двоичной системе — это 11111000100. 11 бит. Значит, у нас ещё 30 симметричных чисел в этом диапазоне.
Итог: 92 двоичных палиндрома
📊 Суммируем всё вместе:
1 + 1 + 2 + 2 + 4 + 4 + 8 + 8 + 16 + 16 + 30 = 92 числа, для которых f(n) = n
Вот такой подход и идеи. А строгие решения можно найти здесь.