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

[hippie]

Понятно, как выяснить за 5 вопросов.

1. Все 8 карт;
2–4. Попарно непересекающиеся пары карт.

По результатам первых четырёх вопросов вся восьмёрка карт разбивается на 4 пары, для каждой из которых известно, чётное ли число бубен в ней.

5. Из каждой "чётной" пары берём по одной карте и задаём вопрос об этом множестве.

Очень похоже, что четырёх вопросов уже недостаточно.

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

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

Зависит от первых двух ответов. (Если первый ответ 2, то третий вопрос задаётся об одной карте.)

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

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

Понятно, как выяснить за 5 вопросов.

1. Все 8 карт;
2–4. Попарно непересекающиеся пары карт.

По результатам первых четырёх вопросов вся восьмёрка карт разбивается на 4 пары, для каждой из которых известно, чётное ли число бубен в ней.

5. Из каждой "чётной" пары берём по одной карте и задаём вопрос об этом множестве.

Ну вот оказалось вдруг после первых четырёх вопросов, что в каждой паре чётное число бубей. А потом Вы взяли по одной карте из каждой пары и получили ответ $2$. При таком раскладе возможно как $2$, так и $6$ бубей в колоде! Не канает Ваш способ

[hippie]

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

Ну вот оказалось вдруг после первых четырёх вопросов, что в каждой паре чётное число бубей. А потом Вы взяли по одной карте из каждой пары и получили ответ $2$. При таком раскладе возможно как $2$, так и $6$ бубей в колоде! Не канает Ваш способ

А какой был ответ на первый вопрос ?

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

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

А какой был ответ на первый вопрос ?

А, у Вас есть первый вопрос про все $8$ карт! Не заметил.

Но тогда Вы неправильно посчитали количество вопросов. Один вопрос про всю колоду. Ещё четыре вопроса про пары. И один вопрос про карты из пар с чётным количеством. Получается $6$, а не $5$

-- Вс июл 22, 2012 22:23:52 --

Хотя да, достаточно трёх вопросов про пары, ибо в связи с первым вопросом мы знаем чётность общего количества. Получается пять

-- Вс июл 22, 2012 22:25:49 --

С предложенным hippie способом выяснения за 5 вопросов согласен. Надо думать про 4 вопроса

[Mathusic]

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

Понятно, как выяснить за 5 вопросов.
1. Все 8 карт;
2–4. Попарно непересекающиеся пары карт.

Я вот тоже покрутил различные варианты: по двойкам, тройкам, пересекающимся по 1 тройкам... Да больно перебора много. И совершенно непонятно, будет ли сходный алгоритм оптимальным для произвольного $N$, поэтому как-то альтруизма перебирать нет
$F(1,2,3,4) = (1,2,3,3)$ - известно. $F(7)=F(8)=5,$ наверное

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

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

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

Я себе представляю, что 8 карт находятся в вершинах куба Не знаю, правда, зачем...

-- Вс июл 22, 2012 22:45:22 --

Как бы мы не задавали 2 вопроса, останется пара карт, которая либо будет всегда входить в "множество вопроса", либо не входить. В эту пару можно поместить как 2 бубны, так и 0 бубей. И на любой вопрос, в "множество которого" входит эта пара, давать ответ $+1$, если в этой паре $0$ бубей, и ответ $-1$, если в этой паре 2 бубны. И ничего таким образом не выясним. Значит, двух вопросов недостаточно!

Тремя вопросами такую пару, увы, можно исключить Так что про 3 и 4 вопроса пока не знаю

-- Вс июл 22, 2012 23:05:46 --

Так. Вот, допустим, три вопроса. На них есть естественное требование: каждая карта должна войти в множество хотя бы одного из вопросов. Иначе мы про карту абсолютно ничего не узнаем.

Пусть множество $X$ состоит из восьми элементов. У нас есть $A_1, A_2, A_3 \subseteq X$, такие что $A_1 \cup A_2 \cup A_3 = X$. Какое максимальное число элементов может содержать булева алгебра, порождённая семейством $A_1, A_2, A_3$ внутри $\mathcal{P}(X)$?

В произвольном случае это $2^{2^3}$. Но тут половина элементов общего случая исключается, так как дополнение к $A_1 \cup A_2 \cup A_3$ пустое.Значит, не более чем $2^{2^3-1}$. У этой алгебры тогда не более чем $2^3 - 1 = 7$ атомов. И значит, снова найдётся пара, ибо как бы мы не делили 8-элементное множество на 7 подмножеств, обязательно найдётся подмножество, содержащее не менее двух элементов. Вывод: трёх вопросов тоже недостаточно!

Про 4 вопроса пока ничего не знаю

-- Вс июл 22, 2012 23:16:22 --

Вот, допустим, $X$ - множество карт. Мы задаём 4 вопроса для $A_1, A_2, A_3, A_4 \subseteq X$. Пусть $Y \subseteq X$ - множество бубей. Нам известны числа $| A_i \cap X| \pm 1$ для всех $i$ от $1$ до $4$. Можно ли подобрать два различных $Y$ так, чтобы все эти числа были одинаковы?

Более строгая формулировка.

Верно ли, что для любых $A_1, A_2, A_3, A_4 \subseteq X$ существуют $Y_1, Y_2 \subseteq X$, такие что $|Y_1| \neq |Y_2|$ и для любого $i$ верно $| |A_i \cap Y_1| - |A_i \cap Y_2| | \in \{ 0,2 \}$?

[Mathusic]

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

Я себе представляю, что 8 карт находятся в вершинах куба Не знаю, правда, зачем...

Я ваш куб не трогал

А я использовал функции-предположения $f_1,f_2, \dots, f_n$ (для $n$ карт), дающие возможные значения количества бубей в группе, в зависимости от ответа (то число, которое нам называют). Эти функции могут принимать значения в виде множества из двух чисел $\{a,b\}$ ("нечёткое значение") или одного - $\{c\}$, которое просто записывается как $c$.
$f_s$ показывает возможное кол-во бубей в группе из $s$ элементов.
Например, $f_1(1)=f_1(-1)=0,$ а $f_7(4)=\{2,3\}.$ Просто удобно тогда составить пару табличек и перебирать.

$\begin{array}{|c||c|c|c|c|} x & -1 & 0 & 1 & 2 \\ \hline f_1(x)&0&1&0&1\\ \end{array}$

$\begin{array}{|c||c|c|c|c|c|} x & -1 & 0 & 1 & 2 & 3 \\ \hline f_2(x)&0&1&\{0,2\}&1&2\\ \end{array}$

$\begin{array}{|c||c|c|c|c|c|c|} x & -1 & 0 & 1 & 2 & 3 & 4\\ \hline f_3(x)&0&1&\{0,2\}&\{1,3\}&2&3\\ \end{array}$

и так далее...

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

Вывод: трёх вопросов тоже недостаточно!

Ну вот, я как раз перебором получил, что для трёх карт двух предположений недостаточно, то есть $F(3)=3$. Вы же доказывали случай для 3-х предположений из $8$ карт.
Может я туплю, но почему-то непонятно, почему всегда $F(n+1) \geqslant F(n)$. Интуитивно кажется, что так должно быть для большинства $n$, но может произойти где-то локальное нарушение?

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

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

Вы же доказывали случай для 3-х предположений из карт.

Да, трёх вопросов для 8 карт недостаточно, это я доказал. То есть доказал, что $F(8) > 3$.

-- Вс июл 22, 2012 23:25:17 --

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

Может я туплю, но почему-то непонятно, почему всегда $F(n+1) \geqslant F(n)$.

Это всегда так. Просто введите в рассмотрение мнимую не бубовую карту.

-- Вс июл 22, 2012 23:28:13 --

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

Ну вот, я как раз перебором получил, что для трёх карт двух предположений недостаточно

Это интересно, поскольку $2^2 - 1 \geqslant 3$ и мой метод доказательства бы не проканал! А вот для четырёх уже канает; в смысле, доказывает, что $F(4) > 2$.

-- Пн июл 23, 2012 00:19:27 --

А если такое разбиение предложить?

У нас $X = \{ 0, 1 \}^3$, то есть $X$ - множество вершин куба. Для $i = 1,2,3$ берём $A_i = \{ (a_1, a_2, a_3) : a_i = 0 \}$. И $A_4 = X$. Надо показать, что пары $Y_1, Y_2$ с требуемыми свойствами не существует.

Рассмотрим симметрическую разность $Y_1 \Delta Y_2$. Она непустая. На каждой из трёх прилегающих к "нулевой вершине" граней куба она содержит либо $0$, либо $2$ элемента. И сама содержит ровно $2$ элемента. Эти 2 элемента надо поместить на одну из прилегающих граней так, чтобы каждая прилегающая грань либо содержала оба, либо не содержала. В нулевую вершину элемент помещать нельзя, ибо как бы мы не разместили второй элемент, выйдет бяка. А если не помещать в нулевую, то в силу симметрии куба достаточно перебрать варианты на одной из граней и ещё один вариант, когда оба элемента на разных гранях. Помещаем оба на смежных с нулевой вершинах - получается бяка. Помещаем один на смежной, а один на отдалённой вершине грани - получается бяка. Наконец, оба элемента не лежат на одной прилегающей грани. Очевидно, что снова бяка!

УРА!!! Доказал, что $F(8) = 4$. То есть четырёх вопросов достаточно. А трёх уже нет.

Извиняюсь за поток сознания. Сейчас оформлю всё более строго.

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

Для начала опишу схему задаваемых вопросов.

У нас 8 карт. Пометим их элементами множества $\{ 0, 1 \}^3$, то есть тройками, составленными из нулей и единиц. Первый вопрос зададим про карты, у которых первая координата метки равна $0$. Второй вопрос - про карты с нулевой второй координатой метки. Третий вопрос будет про карты с третьей нулевой координатой метки. Наконец, четвёртый вопрос будет про всю колоду. Я утверждаю, что задав эти четыре вопроса, можно будет выяснить точное количество карт бубовой масти.

[hippie]

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

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

На все 4 вопроса получим ответ "2".
Сколько бубен на столе ?

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

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

На все 4 вопроса получим ответ "2".

Одна. Если Вы утверждаете, что их может быть 3, покажите как это возможно. Я не вижу.

-- Пн июл 23, 2012 00:51:38 --

Извиняюсь. Да, возможно 3. Где-то я напутал

-- Пн июл 23, 2012 00:53:38 --

Понял, где ошибка. Буду думать дальше!

-- Пн июл 23, 2012 00:58:11 --

Чтобы рассуждать строго, формализуем задачу. Пусть $|X| = 8$. Имеем $F(8) > 4$ тогда и только тогда, когда для любых $A_1, A_2, A_3, A_4 \subseteq X$ существуют $Y_1, Y_2 \subseteq X$ такие, что $|Y_1| \neq |Y_2|$ и для всякого $i$ от $1$ до $4$ числа $|A_i \cap Y_1|$ и $|A_i \cap Y_2|$ либо совпадают, либо отличаются на двойку.

Надеюсь, с такой формулировкой все согласны?

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

Я теперь уже сам с этой формулировкой не согласен! Она для случая, когда следующие вопросы не зависят от ответов на предыдущие.

Отсюда мораль: по ночам решать задачи вредно.

[Руст]

Алгоритм hippie дает ответ всегда за $[\frac{n+3}{2}]$ хода. Можно уменьшит число ходов в зависимости от ответов по другому алгоритму. При этом в худшем случае придется задать столько же вопросов.
Заметим, что получив ответ $r(n)$ на вопрос о количестве бубей в множестве из n карт мы знаем ответ $r(n)\pm 1$, если ответ был $r(n)=-1,0$, тогда количество $r(n)+1$ и если ответ $r(n)=n,n+1$, тогда количество $r(n)-1$. Соответственно, точная информация получается только у границы. Поэтому задав вопрос о всем количестве и получив ответ $r(n)$, спросим о количестве бубей в множестве k карт и получив ответ r(k) мы знаем, что количество карт в этом множестве $r(k)\pm 1$, а в дополнении $r(n)-r(k)-2,r(n)-r(k), r(n)-r(k)+2$. Мы быстрее узнаем точный ответ, в той половине $k,n-k$, где меньше не определенность $min(r(k),k-r(k)), min(r(n)-r(k),n-k-r(n)+r(k)$. Продолжим деление попалам, в той половине, где меньше не определенность. Таким образом получается ответ в самом худшем исходе ответов за столько же вопросов, а часто за меньшее количество. Например для n=8, получив ответ 1, и получив ответ для половины k=4 число 0 или 2, сразу заключаем, что общее количество 2.

[arqady]

Ktina, можно полюбопытствовать, откуда эта задача?

[Ktina]

arqady в сообщении #598139 писал(а):

Ktina, можно полюбопытствовать, откуда эта задача?

Можно.

Разумеется, из "Кванта".