Условие
На
n карточках написаны с разных сторон числа — на 1-й: 0 и 1;
на 2-й: 1 и 2; ...; на
n-й:
n - 1 и
n.
Один человек берёт из стопки несколько карточек и показывает второму одну
сторону каждой из них. Затем берёт из стопки еще одну карточку и тоже
показывает одну сторону.
Указать все случаи, в которых второй может определить число, написанное на
обороте последней показанной ему карточки.
Решение
Пусть
k — последнее показанное число.
Докажем, что второй может определить число, написанное на обороте последней
карточки тогда и только тогда, когда выполнена одна из следующих возможностей:
1) Были показаны все числа от
k до
n включительно.
2) Были показаны все числа от 0 до
k включительно.
3) Были показаны все числа между
k и
l 
k, а число
l было показано
дважды.
Сначала докажем, что в каждом из этих случаев число, написанное на обороте
последней карточки, восстановить можно.
Действительно, в случае 1) второй знает, что на карточке, которая была
показана стороной
n, с другой стороны написано число
n - 1, на карточке,
показанной стороной
n - 1 — число
n - 2, ..., на карточке, показанной
стороной
k — число
k - 1.
Случай 2) симметричен случаю 1). В случае 2) на обратной стороне написано
число
k + 1.
В случае 3) на обратной стороне будет написано число
k + 1, если
l <
k, и
k - 1 в противном случае.
Пусть теперь второй может восстановить число, написанное на обороте последней карточки.
Докажем, что выполнен один из случаев 1)— 3).
Без ограничения общности можно считать, что число, написанное на обороте
последней карточки, равно
k + 1. Заметим, что второй может сделать вывод, что
на обороте последней карточки написано число
k + 1, только из того, что
карточка (
k - 1,
k) уже встречалась ранее, причём она была показана стороной
k - 1. Если встречалась только одна карточка, показанная стороной
k - 1, то
мы знаем, что второй может про неё установить, что на обороте написано
k.
Таким образом, мы попадаем в ситуацию, аналогичную ситуации с исходной
карточкой, но с меньшим
k. Уменьшая таким образом
k, мы придём как раз в
одну из ситуаций 2) или 3), ч. т. д.
Источники и прецеденты использования
