Карточная игра

[Mathusic]

Прогуглил задачу
Оказалось, что Ktina предложила нам более сложную задачу. Оригинальная концовка имеет такой смысл:

Цитата:

Как при помощи пяти вопросов наверняка узнать количество бубновых карт, лежащих на столе?

[Профессор Снэйп]

Mathusic в сообщении #598169 писал(а):

Оказалось, что Ktina предложила нам более сложную задачу. Оригинальная концовка имеет такой смысл:

Ктина, я в шоке! Как ты могла!!!

Я ведь всю ночь, до 6 утра с этой задачей парился. А в 8 чистить зубы и на работу. Сутки подряд не спать вредно, моё драгоценное здоровье безвозвратно подорвано

А ведь дело было так: Хиппи ещё в час ночи предложил решение с пятью вопросами, а всю ночь начиная с этого времени я убил, изучая возможность решения в четыре вопроса. Попутно доказал, что за 3 вопроса нельзя... А оказывается, ничего этого не надо было

Впрочем, после этой ночи я стал всерьёз подозревать, что задача про 4 вопроса не олимпиадная, а научно-исследовательская. Не вылазит там ниоткуда красивой изящной идеи, вылазит лишь тупой перебор расположения восьми множеств на вершинах четырёхмерного куба...

Впрочем, по прикидкам, тупой компьютерный перебор всех возможных стратегий из четырёх вопросов займёт не так уж много времени. Так что, если накатит настроение, можно будет прогу писать и добивать задачу по принципу "сила есть - ума не надо".

[Mathusic]

Руст в сообщении #598117 писал(а):

Алгоритм hippie дает ответ всегда за $[\frac{n+3}{2}]$ хода.

Вполне может быть, что это оптимальное решение ($F(n)=1$).
Это утверждение эквивалентно системе из двух условий (с учётом того, например, что $F(2)=2$):
1) $F(2n+1) = F(2n+2)$
2) $F(2n)+1=F(2n+1)$
Для всех $n=1,2,3, \dots$

Соответственно, если хотя бы одно опровергнуть хотя бы на конкретном примере, то утверждение неверно.

[Профессор Снэйп]

Надо программу писать, однако