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

[Ktina]

На столе лежат катринками вниз 8 игральных карт. Вы можете указать на любую группу карт (в частности, на одну карту или, например, на все восемь) и спросить, сколько карт бубновой масти в этой группе? В качестве ответа Вам сообщат число, отличающееся от истинного значения на 1. За какое наименьшее число вопросов можно наверняка узнать количество бубновых карт, лежащих на столе?

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

За 8. Ощущение такое. Правда, строгого доказательства у меня пока нет.

[Ktina]

Профессор Снэйп в сообщении #597889 писал(а):

За 8. Ощущение такое. Правда, строгого доказательства у меня пока нет.

Можно меньше.

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

Для начала хотелось бы понять ситуацию с меньшим числом карт.

Если карта одна, то минимум один вопрос задать необходимо.

Если карт две, то потребуется минимум два вопроса. Это тоже очевидно.

Если у нас три карты, то... надо подумать.

-- Вс июл 22, 2012 18:47:34 --

Наверное, то, что в исходном условии количенство карт равно степени двойки - это не зря...

[Руст]

Профессор Снэйп в сообщении #597895 писал(а):

Наверное, то, что в исходном условии количенство карт равно степени двойки - это не зря...

Это не причем.
Возьмите одну карту и спросите. Тут ясно увеличил или уменьшил. Берите дополнение, потом все карты. По трем таким вопросам всегда узнаете общее количество.

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

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

Это не причем.
Возьмите одну карту и спросите. Тут ясно увеличил или уменьшил. Берите дополнение, потом все карты. По трем таким вопросам всегда узнаете общее количество.

На первуя карту ответил $1$. На дополнение ответил $4$. На все карты ответил $4$. Сколько бубей, $3$ или $5$, осталось неизвестным.

[hippie]

Количество бубен среди четырёх карт легко определяется за 3 хода (первый вопрос о всех четырёх картах; второй — о двух). Следовательно, 6 ходов достаточно.
Остаётся понять, можно ли обойтись меньшим числом ходов.

[Mathusic]

Профессор Снэйп в сообщении #597950 писал(а):

На первуя карту ответил $1$. На дополнение ответил $4$. На все карты ответил $4$. Сколько бубей, $3$ или $5$, осталось неизвестным.

Проблема в том, что такая ситуация невозможно в принципе
P.S. Для 3-х карт - три вопроса.

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

hippie в сообщении #597959 писал(а):

Количество бубен среди четырёх карт легко определяется за 3 хода (первый вопрос о всех четырёх картах; второй — о двух).

Не понимаю. Вот, допустим, на вопрос о четырёх картах ответ был $1$. Потом на вопрос о двух картах ответ был снова $1$. Какой третий вопрос надо задавать?

[Ktina]

hippie в сообщении #597959 писал(а):

Количество бубен среди четырёх карт легко определяется за 3 хода (первый вопрос о всех четырёх картах; второй — о двух). Следовательно, 6 ходов достаточно.
Остаётся понять, можно ли обойтись меньшим числом ходов.

Можно

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

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

Профессор Снэйп в сообщении #597950 писал(а):

[quote="Руст в
На первуя карту ответил $1$. На дополнение ответил $4$. На все карты ответил $4$. Сколько бубей, $3$ или $5$, осталось неизвестным.

Проблема в том, что такая ситуация невозможно в принципе

С какой это радости она невозможна?

Представьте себе ситуацию с $3$ бубновыми картами. Выбираете не бубновую, потом дополнение, потом вся "колода". Возможны именно такие ответы, которые я написал. А теперь $3$ замените на $5$ и представьте, что тоже выбираете не бубновую карту. Возможны те же самые ответы.

[Mathusic]

Профессор Снэйп в сообщении #597968 писал(а):

Представьте себе ситуацию с $3$ бубновыми картами. Выбираете не бубновую...

А, ну да. Почему-то я считал, что первая карта у вас - бубновая
Кстати, интересно бы было найти $F(n)$ - искомый ответ для произвольного $n$.

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

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

Кстати, интересно бы было найти $F(n)$ - искомый ответ для произвольного $n$.

Тут бы для начала $F(8)$ найти

[hippie]

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

Возьмите одну карту и спросите. Тут ясно увеличил или уменьшил. Берите дополнение, потом все карты. По трем таким вопросам всегда узнаете общее количество.

Если бы так действительно было можно определить, то всегда хватило бы двух вопросов (второго и третьего, т.к. по ним однозначно восстанавливается "ответ" на первый вопрос).

Профессор Снэйп в сообщении #597966 писал(а):

hippie в сообщении #597959 писал(а):

Количество бубен среди четырёх карт легко определяется за 3 хода (первый вопрос о всех четырёх картах; второй — о двух).

Не понимаю. Вот, допустим, на вопрос о четырёх картах ответ был $1$. Потом на вопрос о двух картах ответ был снова $1$. Какой третий вопрос надо задавать?

Нужно спросить о двух картах, одна из которых входит в "опрошенную" пару, а вторая — нет.
При ответе "1" или "–1" на столе 0 бубен;
При ответе "0" или "2" на столе 2 бубны.

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

hippie в сообщении #597987 писал(а):

Нужно спросить о двух картах, одна из которых входит в "опрошенную" пару, а вторая — нет.

А, ну да, согласен.

У Вас третий вопрос всегда такой, как Вы описали, или он зависит от ответов на первые два вопроса?