Пустьk — последнее показанное число. Докажем, что второй может определить число, написанное на обороте последней карточки тогда и только тогда, когда выполнена одна из следующих возможностей:

1. Были показаны все числа отkдоnвключительно.

2. Были показаны все числа от 0 доkвключительно.

3. Были показаны все числа междуkиl$\neq$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), ч. т. д.

Ответ задачи отсутствует