Ладно, упоротые упёртые упорные товарищи. Я вижу, вы принципиально отказываетесь понимать, что это задача не из теории кодирования... Давайте сделаем небольшую поправку к условию: пусть мы имеем дело с математиками не только гениальными, но и безумными, чьи мозги зохаваны Ктулху, причём зохаваны одинаково. Таким образом, у них есть некоторый (неизвестный и, возможно, принципиально нам непонятный) способ рассуждать, причём каждый из них понимает, как рассуждает другой. Задумаемся же о свойствах этого способа.
Во-первых, последовательность ответов может выглядеть так и только так: до некоторого момента - сплошные "нет", затем - сплошные "да". Почему так? Если математик в некоторый момент понял, какое число у другого, он уже не может перестать это понимать, и после одного ответа "да" остальные ответы также будут "да". Для другого математика, в свою очередь, ответы первого перестают нести информацию - поэтому если он в принципе способен понять, какое число у первого, он должен это сделать после первого же "да".
Пусть математикам загадана пара чисел (х, х+1). Здесь и далее первое число пары относится к математику, задававшему первый вопрос в игре. Не нарушая общности, пусть математик с числом х первым ответил "да". Пусть теперь загадана пара (х, х-1). Математик с числом х не мог ответить "да" первым - иначе получилось бы, что он, получая одну и ту же последовательность ответов "нет" от другого, тем не менее как-то различает две неразличимых ситуации. Значит, первым ответит "да" математик с числом (х-1). Пусть это произойдёт на вопросе под номером (Ы-1) (чтоб никто не догадался). Теперь рассмотрим ситуацию с точки зрения математика, которому загадано число х и он не знает, какое число у оппонента. Если математик с числом х на вопрос под номером (Ы-1) получает ответ "да", он понимает, что реализовалась ситуация (х, х-1), и вопрос под номером (Ы-1) становится последним. Если же он получает ответ "нет", он понимает, что реализовалась ситуация (х, х+1) и отвечает "да" на Ытый вопрос, после чего второй математик (см. предыдущий абзац) обязан также всё понять. Следовательно, ситуация (х, х+1) разрешается за Ы вопросов. Или, что то же самое, ситуация (х, х-1) разрешается на один вопрос быстрее ситуации (х, х+1).
Рассмотрим теперь ситуации (х, х-1) и (х-2, х-1) с точки зрения математика с числом (х-1). Рассуждая аналогично, приходим к выводу, что для разруливания ситуации (х-2, х-1) понадобится (Ы-2) вопроса. Продолжая спуск, мы получим, что для ситуации (1, 2) либо (2,1), в зависимости от чётности, понадобится (Ы-х+1) вопросов. Для разруливания ситуации (1, 2) необходимо и достаточно двух вопросов, для ситуации (2,1) - одного. Следовательно, Ы=х либо Ы=х+1, в зависимости от чётности.
Если же в ситуации (х, х+1) первым отвечает "да" тот математик, у которого число больше, мы совершенно аналогично сводим всё к случаям (999, 1000) и (1000, 999).
Ктулхический мозг математиков способен обойти тот парадокс, о котором я говорил. Например, они одновременно могут прийти к мысли забить на верхний (или нижний) предел. Если я правильно понял, пользователь Tomar чем-то в этом роде и воспользовался (возможно, его мозг зохаван Ктулху, ня?). Однако даже при этом им заведомо понадобится количество вопросов не меньше, чем расстояние от одной из границ интервала. В противном случае для передачи дополнительной информации кому-то из них придётся врать.
Вот это уже претендует на то, чтобы называться корректным обоснованием)) Лично я решение признаю корректным, обсуждать с моей точки зрения больше нечего.
