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

[-Ромка-]

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

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

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

то есть как?
они сидят:
-ты знаешь, какое у меня число?
-нет, а ты про мое?
-нет, а ты про мое?
....
или еще что-то?

[Романтик]

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

Нужны комментарии.
p.S опоздал с вопросом.

Сообщение отредактировано: Романтик - 11.04.2006 20:18

[-Ромка-]

то есть как?
они сидят:
-ты знаешь, какое у меня число?
-нет, а ты про мое?
-нет, а ты про мое?

Да. Например, 4 и 2 -первый сразу не знает. Второй думает: "У 1-го может быть 1 или 4. Но если у него 1, то он сразу сказал бы "знаю", так как у меня не может быть 1/2. => у него 4". Т.е. игра -
1-й. Я не знаю (1 ход)
2-й. Я знаю - 2 (2 ход)

[Malice]

У меня вот так получилось:

function check(a,b:integer):integer;
var i:integer;
begin
if (a xor b) and 1=1 then check:=1 {типа, а чего тут думать - и так все очевидно} else begin
i:=0;
while ((a and 1)=0) do begin
 a:=a shr 1; inc (i);
 b:=b+a; a:=b-a; b:=b-a;
end;
check:=i-1;
end;
end;

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

а если 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). При этом предполагается, что они оба предельно умные и никогда не ошибаются. Если произойдет ошибка - "игра" и вовсе утрачивает смысл. По-моему, тут таится какое-то противоречие, парадокс, который никто пока не сформулировал, насколько мне известно.

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

[Гость]

Ну здесь она находится, так как она с моего школьного олимпиадного программирования. А прога сделанная Malice, работает немного неправильно...

[volvo]

Гость, но вообще-то, если ты уж взялся утверждать, что ЧТО-ЛИБО работает неправильно, то будь добр не просто так трепать языком, а АРГУМЕНТИРОВАННО доказать, что это действительно работает не так, как ТЫ ДУМАЕШЬ, что должно работать.

[-Ромка-]

упс, забыл подписатся в предпреведущем посте, сорри. Ну она(прога) работает напрвильно на примере 2,1 и некоторых других ответ выдает выдает на 1 меньше. Может и еще где-то работает неправильно...

[Malice]

А какой ответ должен быть в примере 2,1 ? Первым if-ом я отсек такие варианты, считая, что если одно из чисел нечетное, то и гадать незачем Если должно быть 2 (т.е. первый успеет сказать, что не знает), то можно исправить строку "then check:=1" на "then check:=1+byte(a>b)"