Решение задачи 482

Условие:

Каждому из двух мудрецов сообщили по натуральному числу, причём им известно, что эти числа отличаются на единицу. Они поочередно спрашивают друг друга: «Известно ли тебе моё число?» Докажите, что рано или поздно кто-то из них ответит «да».

Решение:

Пусть на первый вопрос первого мудреца второй мудрец ответил "нет" (предположим, что мудрецам сообщили достаточно большие числа). Это значит, что у него не единица. Аналогично, если первый мудрец ответить "нет" на первый вопрос второго мудреца, то у него тоже не единица. Получается, после первой пары вопросов оба мудреца знают, что у них обоих не единицы.

Теперь минимальное число в игре — двойка, поэтому, если второй мудрец на второй вопрос первого мудреца отвечает "нет", то у него не двойка (иначе бы он знал, что у первого тройка). Аналогично, после первой пары вопросов оба мудреца знают, что у них обоих не единицы и не двойки.

И так далее. Пусть у первого мудреца число N + 1, а у второго — N (симметричный случай аналогичен). Тогда после 2 * (N − 1) вопросов оба мудреца будут знать, что минимальное число в игре это N. И на следующий вопрос второй мудрец ответит "да", поняв, что у первого мудреца число N + 1.