Алгоритм Пети с минимальной чётной цифрой

Условие

У Пети есть доска. Слева — натуральное число. Справа — он хочет записать минимальную чётную цифру в записи этого числа (предположим, такая есть).

Алгоритм:

1. Сначала записать справа последнюю цифру числа.
2. Стирать последнюю цифру слева; если она чётная и меньше, чем цифра справа — заменить ту, что справа.
3. Повторять, пока не сотрут всё число слева.

(а) Что получит, если слева было 18543? (б) Чему равна предпоследняя цифра числа, дающего остаток 23 при делении на 25, для которого алгоритм сработал неверно?

В ответе — сумма ответов (а) и (б).

Решение

(а) Симуляция для 18543

Слева: 18543. Справа сразу: 3 (последняя цифра).

Стираем 3 — нечётная, не подходит. Справа всё ещё 3. Слева 1854.

Стираем 4 — чётная, 4 < 3? Нет, 4 > 3. Не заменяем. Справа 3. Слева 185.

Стираем 5 — нечётная. Справа 3. Слева 18.

Стираем 8 — чётная, 8 < 3? Нет. Справа 3. Слева 1.

Стираем 1 — нечётная. Справа 3. Слева пусто.

Итог справа: 3.

Но минимальная чётная цифра в 18543 — это 4 (есть 8 и 4). Алгоритм выдал 3 — то есть сработал неверно.

Хм, выходит, в постановке (а) ожидался ответ 4 (минимальная чётная цифра). Но алгоритм даёт 3. Это и есть подвох — Петя ошибается, и (а) — это тот ответ, который алгоритм дал, а не «правильный».

Перечитаем условие: «Что он получит, если изначально...». То есть — что окажется на доске справа. Это 3.

(б) Когда алгоритм неверен

Алгоритм:

• Инициализируется последней цифрой числа.
• Сравнивает каждую следующую сте́ртую цифру только если она чётная и меньше текущей справа.

Алгоритм некорректен, потому что он сразу записывает справа последнюю цифру, не проверяя её чётность. Если последняя цифра нечётна и меньше всех чётных — она там и останется, а минимальная чётная не будет найдена (как в примере (а): начальная 3 нечётна, но меньше всех чётных 4 и 8 — заменена не будет).

Поэтому алгоритм работает неверно ⇔ последняя цифра нечётна и меньше минимальной чётной цифры в числе.

Условие: число даёт остаток 23 при делении на 25 ⇒ его последние две цифры — 23, 48, 73, 98 (всё что в mod 100, дающее 23 mod 25).

23 — последняя 3 (нечётна), 2 — чётная. Минимальная чётная во всём числе ≥ 2. 3 < 2? Нет, 3 > 2. Алгоритм заменит 3 на 2 ⇒ алгоритм сработает. Не подходит.

48 — последняя 8 (чётна). Алгоритм возможно работает. Если в числе есть меньшая чётная — заменит. Не подходит для «неверно».

73 — последняя 3 (нечётна). Предпоследняя — 7. Минимальная чётная в этом числе зависит от старших цифр. Если все старшие нечётные, кроме каких-то чётных — 3 останется. Алгоритм даст 3. Если в числе минимальная чётная — 2, то правильный ответ — 2, а алгоритм дал 3 — неверно.

Например, 273. Минимальная чётная — 2. Алгоритм: справа 3, стираем 7 (нечёт), 2 чётная, 2 < 3 — да, заменяем справа на 2. Итог 2. Алгоритм работает!

Хм. Тогда подвох — 3 остаётся ↔ ни одна стираемая цифра не оказалась чётной и меньше 3. Это значит — в числе вообще нет чётной цифры < 3, то есть нет цифры 0 или 2.

Но условие говорит «предположим, что [минимальная чётная] цифра есть». Значит, есть хотя бы одна чётная (0, 2, 4, 6, 8), и она ≥ 4 (иначе 2 < 3 всё-таки сработает).

Если минимальная чётная ≥ 4, то она > 3. Алгоритм НЕ заменит 3 (потому что условие «чётная и меньше 3»), и оставит 3. Это и есть случай неверной работы.

98 — последняя 8. Предпоследняя 9. Алгоритм инициирует справа 8. Если в числе нет цифры меньше 8 чётной, оставит 8. Так и должно. Если есть — заменит.

98 mod 25 = 23? Проверим: 98 = 3 * 25 + 23, да.

Чтобы алгоритм работал НЕВЕРНО, нужна последняя цифра нечётная и она меньше существующей минимальной чётной. Последние две дают mod 100. У нас четыре варианта: 23, 48, 73, 98. Из них последняя цифра нечётна: 23, 73. То есть предпоследняя цифра — 2 или 7.

Из них только 73 (предпоследняя 7) реально может дать неверный алгоритм (для 23, как мы видели, алгоритм сработает: 2 < 3).

Предпоследняя цифра = 7.

Сумма

(а) = 3 (то, что Петя получит); (б) = 7. Сумма = 10.

Альтернатива: если в (а) спрашивается «правильный ответ алгоритма» = 3, и (б) = 7, всё равно 10.

Или если (а) понимается как «минимальная чётная» (т.е. правильный ответ задачи) = 4, тогда сумма 4 + 7 = 11. На собесе уточните формулировку.

Эталонный ответ

3 + 7 = 10 (или 4 + 7 = 11 в зависимости от трактовки (а)).

Подводные камни

1. «Что он получит» — буквально, что окажется справа после симуляции. Не «правильный» ответ.
2. Анализ когда алгоритм неверен. Ключевая мысль: последняя цифра пишется справа без проверки чётности; значит, сбой возможен ровно когда она нечётна и меньше всех чётных в числе.
3. mod 25 = 23 даёт ровно 4 варианта последних двух цифр: 23, 48, 73, 98.