ВОПРОС 25: Автомат обрабатывает натуральное число N > 1 по следующему алгоритму. 1. Строится двоичная запись числа N. 2. Последняя цифра двоичной записи удаляется. 3. Если исходное число N было нечётным, в конец записи (справа) дописываются цифры 10, если чётным - 01. 4. Результат переводится в десятичную систему и выводится на экран. Пример. Дано число N = 13. Алгоритм работает следующим образом. 1. Двоичная запись числа N: 1101. 2. Удаляется последняя цифра, новая запись: 110. 3. Исходное число нечётно, дописываются цифры 10, новая запись: 11010. 4. На экран выводится число 26. Какое число нужно ввести в автомат, чтобы в результате получилось 2018?

Решение:

Задача сводится к обратному преобразованию числа 2018 в десятичной системе к исходному числу N. Рассмотрим алгоритм в обратном порядке:

1. Обратное действие к шагу 4: Результат 2018 — это десятичное представление двоичной записи. Нам нужно перевести 2018 в двоичную систему.

\( 2018_{10} = 11111100010_2 \)

1. Обратное действие к шагу 3: Перед дописыванием цифр 10 (для нечётного N) или 01 (для чётного N) была двоичная запись числа.
• Если число нечётное, дописывали '10'. Значит, перед этим двоичная запись заканчивалась на '10'.
• Если число чётное, дописывали '01'. Значит, перед этим двоичная запись заканчивалась на '01'.

В нашем случае, двоичная запись 2018 — 11111100010. Она заканчивается на 10. Это значит, что исходное число было нечётным, и мы отбрасываем последние '10'. Получаем: 111111000.

1. Обратное действие к шагу 2: Последняя цифра двоичной записи удалялась. Значит, чтобы восстановить исходную запись, нужно добавить к концу 111111000 ту цифру, которая была удалена.
• Если последняя цифра была 0, значит, исходное число было чётным.
• Если последняя цифра была 1, значит, исходное число было нечётным.

Поскольку двоичная запись, полученная на предыдущем шаге (111111000), заканчивается на 0, это означает, что исходное число было чётным, и удалённая цифра была 0. Восстанавливаем её: 1111110000.

1. Обратное действие к шагу 1: Построение двоичной записи числа N. У нас есть двоичная запись, полученная на предыдущем шаге: 1111110000.

Теперь переведём полученную двоичную запись в десятичную систему:

\( 1111110000_2 = 1 × 2^9 + 1 × 2^8 + 1 × 2^7 + 1 × 2^6 + 1 × 2^5 + 1 × 2^4 + 0 × 2^3 + 0 × 2^2 + 0 × 2^1 + 0 × 2^0 \)

\( = 512 + 256 + 128 + 64 + 32 + 16 = 1008 \)

Проверим: если N = 1008 (чётное), то его двоичная запись 1111110000. Удаляем последнюю цифру (0), получаем 111111000. Число чётное, дописываем 01, получаем 11111100001. Это не 2018.

Давайте пересмотрим шаг 3:

Обратное действие к шагу 3:

Двоичная запись результата: 11111100010.

Если исходное число было нечётным, дописали '10'. Отбрасываем '10' -> 1111110001. Теперь проверим, было ли это число нечётным. Последняя цифра '1', значит, число нечётное. Это соответствует условию. Переведём 1111110001 в десятичную систему:

\( 1111110001_2 = 1 × 2^9 + 1 × 2^8 + 1 × 2^7 + 1 × 2^6 + 1 × 2^5 + 1 × 2^4 + 0 × 2^3 + 0 × 2^2 + 0 × 2^1 + 1 × 2^0 \)

\( = 512 + 256 + 128 + 64 + 32 + 16 + 1 = 1009 \)

Проверим: если N = 1009 (нечётное), то его двоичная запись 1111110001. Удаляем последнюю цифру (1), получаем 111111000. Число нечётное, дописываем 10, получаем 11111100010. Переводим в десятичную: \( 1008 + 1 = 1009 \). Это не 2018.

Давайте начнем с шага 4, где результат — 2018.

1. Обратное к шагу 4: Переводим 2018 в двоичную систему. \( 2018_{10} = 11111100010_2 \).

2. Обратное к шагу 3: Смотрим на последние две цифры двоичной записи результата (10). Эти цифры были добавлены согласно правилу. Если были добавлены 10, значит, исходное число было нечётным, и мы отбрасываем 10. Если были добавлены 01, значит, исходное число было чётным, и мы отбрасываем 01. В нашем случае, последние две цифры — 10. Это означает, что исходное число было нечётным, и мы отбрасываем 10. Получаем двоичную запись: 1111110001.

3. Обратное к шагу 2: Последняя цифра двоичной записи была удалена. Следовательно, чтобы восстановить исходную двоичную запись, нужно добавить к концу удалённую цифру. В записи 1111110001 последняя цифра — 1. Значит, исходное число было нечётным (что совпадает с выводом из предыдущего шага), и удалённая цифра была 1. Добавляем её обратно: 11111100011.

4. Обратное к шагу 1: Получили исходную двоичную запись числа N: 11111100011.

Теперь переведём её в десятичную систему:

\( 11111100011_2 = 1 × 2^{10} + 1 × 2^9 + 1 × 2^8 + 1 × 2^7 + 1 × 2^6 + 1 × 2^5 + 0 × 2^4 + 0 × 2^3 + 0 × 2^2 + 1 × 2^1 + 1 × 2^0 \)

\( = 1024 + 512 + 256 + 128 + 64 + 32 + 2 + 1 = 2019 \)

Проверим:

Если N = 2019 (нечётное):

1. Двоичная запись 2019: 11111100011.
2. Удаляем последнюю цифру (1): 1111110001.
3. Число нечётное, дописываем 10: 111111000110.
4. Переводим в десятичную: \( 1008 × 2 + 2 = 2016 + 2 = 2018 \).

Соответствует!

Ответ: 2019