Задачка про игру, логика Опции

[-Ромка-]

Однажды два математика придумали математическую игру и решили в нее сыграть. Они попросили постороннего человека написать на разных листах бумаги два натуральных числа, причем одно должно быть больше другого ровно в 2 раза. Затем один математик взял один лист, а второй взял оставшийся. В чужие листы они не заглядывали и единственное, что знал каждый из них – на другом листе записано число либо в 2 раза большее, либо в 2 раза меньшее, чем у него. Затем началась игра. Игра заключается в том, что игроки по очереди отвечают на вопрос, знают ли они, какое число записано на листе соперника, до тех пор, пока один из них не сможет назвать это число. В процессе игры игроки всегда учитывают всю информацию, которую им дает ответ соперника, и говорят только правду.

Нужно вывести на каком ходе будет получен правильныей ответ. Ответ явно связан со степенью двойки "входящей в число". Пример числа 8 и 16 ответ 5. Числа 4 и 2 ответ 2.

[мисс_граффити]

а если 8 и 16?
как-то пока не понимаю.

[Lapp]

а если 8 и 16?

Здесь уже разобрали случай с 2 и 4. В этом случае игрок с 2 догадался на втором ходу.
Теперь рассмотрим случай с 4 и 8. После двух ходов игрок с 4 думает: "У него может быть либо 2, либо 8. Но если бы у него было 2, то он бы догадался на втором ходу, так как это был бы случай 2 и 4, который уже разобран. Раз он не догадался, значит, это не есть случай 2 и 4. Тогда это случай 4 и 8, и у него - 8".
Таким образом, в случае 4 и 8 игрок с 4 догадывается на 3-ем ходу.

Далее - рекурсия. В случае 8 и 16 игрок с 8 догадается на 4-ом ходу, так как он будет ссылаться на альтернативный случай 4 и 8, который должен быть решен на 3-ем ходу. И так далее..

Строго говоря, это не игра в изначальном смысле этого слова. Ибо в ней нет выигравших и проигравших. Игрок с меньшим числом должен догадываться на ходу порядка Log2(n). При этом предполагается, что они оба предельно умные и никогда не ошибаются. Если произойдет ошибка - "игра" и вовсе утрачивает смысл. По-моему, тут таится какое-то противоречие, парадокс, который никто пока не сформулировал, насколько мне известно.

Это головоломка на рекурсивное мышление, похожая на мудрецов с колпаками. Что она делает в этом разделе - ума не приложу. Она скорее для раздела Математика..