Три фокусника

[Edward_Tur]

Три фокусника показывают фокус. Они дают зрителю колоду карточек с числами от 1 до $2n + 1$ ($n > 6$). Зритель берет себе одну карточку, а остальные раздает поровну (произвольным образом) первому и второму фокусникам. Фокусники, не общаясь, изучают каждый свои n карт, отбирают из них по 2 карты, и, сложив их в (упорядоченную) стопочку, передают третьему фокуснику. Третий фокусник просматривает полученные 4 карты и сообщает, какая карта у зрителя. Объясните, каким образом может быть показан такой фокус.
Источник: СПб МО-1999

[ddn]

Edward_Tur писал(а):

Три фокусника показывают фокус. Они дают зрителю колоду карточек с числами от 1 до $2n + 1$ ($n > 6$). Зритель берет себе одну карточку, а остальные раздает поровну (произвольным образом) первому и второму фокусникам. Фокусники, не общаясь, изучают каждый свои n карт, отбирают из них по 2 карты, и, сложив их в (упорядоченную) стопочку, передают третьему фокуснику. Третий фокусник просматривает полученные 4 карты и сообщает, какая карта у зрителя. Объясните, каким образом может быть показан такой фокус.
Источник: СПб МО-1999

Все числа от $1$ до $2n + 1$ отличаются друг от друга по модулю числа $2n + 1$. Сумма всех этих чисел равна $(n+1)(2n+1)\mod 2n+1=0$ по модулю $2n + 1$, значит если в колоде отсутствует карта с числом $k$, то сумма чисел такой колоды равна $2n-k+1\begin{array}{cc}\geqslant 0\\<2n+1\end{array}$ по модулю $2n + 1$, откуда ее и определяет третий фокусник.
В каждой полуколоде (по $n$ карт) у первых двух фокусников два наибольших числа на картах составляют не менее $n$ и $n+1$ (кроме случая, когда у одного фокусника полуколода с числами от $1$ до $n$) - что достаточно, чтобы в сумме достигнуть величины $2n + 1$ - для чего первыми двумя фокусниками и выбирается по две карты из своих полуколод. Суть в том, чтобы выбрать из каждой полуколоды первого и второго фокусника по две карты с такими числами, что они в сумме равны по модулю $2n + 1$ сумме чисел во всей полуколоде каждого фокусника. Тогда, сумма чисел от четырех карт, выбранных первым и вторым фокусником, равна по модулю $2n + 1$ сумме чисел всей колоды, кроме числа выбранного зрителем - откуда его определяет третий.

[Dandan]

хороший фокус

[Edward_Tur]

Что делать первому фокуснику с набором 2,3,4,5,6,7 ? ($n=6$).
Не может ли возникнить такая же ситуация для некоторого ($n>6$)?

[Dave]

У меня получилось доказать (объяснить) для всех $n \geqslant 5$.

[Shadow]

Dave в сообщении #529134 писал(а):

У меня получилось доказать (объяснить) для всех $n \geqslant 5$.

Объясните. Интересно

[Руст]

По модулю $2n+1$ не удастся передать полную информацию. Пусть $n=2k+1$ и первому попали карты $(1,2n,2,2n-1,...k,2n+1-k,n)$. Сумма $n$ карт фокусника равна $n$ по модулю $2n+1$ и оно не представляется в виде суммы двух из полученных карт по модулю $2n+1$. Поэтому надо работать по другим модулям. Если карты нумеровать от 0 до $2n$, то вся сумма равна $n(2n+1)=0\mod n,=1\mod(2n-1),...$ При использовании меньшегомодуля надо передать еще дополнительную информацию. Например при работе по модулю $2n-1$ первому передать наличие или отсутствие карты 0, второму наличие или отсутствие карты 2n, вдобавок суммы по модулю $2n-1$.

[Dave]

Действовать нужно по модулю $2n+1$, но только немного не так, как говорил ddn.
Для простоты будем считать, что карточки нумеруются числами от $0$ до $2n$. Тогда в реальном применении фокусники просто меняют номер $0$ в нижеописанном методе на номер $2n+1$.
Нужно разбить множество $K=\{0,1,\dots,2n\}$ на $3$ тройки и $n-4$ пары, как - будет написано ниже. Будет набор из $n-1$ подмножеств, $T=\{T_1, T_2,\dots,T_{n-1}\}$, образующий разбиение $K$. Далее выписать из троек $3 \cdot 3 = 9$ возможных пар и упорядочить полученные $n+5$ пар:

$$P=\{(a_1,b_1), \; (a_2,b_2), \; \dots, \; (a_{n+5},b_{n+5})\}$$

так, чтобы разности $b_i-a_i$ давали попарно различные остатки при делении на $2n+1$.

Каждый из первых двух фокусников делает следующее:

1. Берёт сумму чисел на своих карточках по модулю $2n+1$. Пусть у него получается число $s$.
2. Прибавляет к каждому множеству из $T$ и каждой паре из $P$ число $s$ с циклическим сдвигом по модулю $2n+1$, т.е. $x \to (x+s) \mod (2n+1)$. Если разбить окружность на $2n+1$ одинаковых дуг и пронумеровать их по часовой стрелке, расположив множество $K$ соответственно номерам на дугах, то это эквивалентно повороту множества $K$, всех множеств $T$ и пар $P$ на $s$ секторов по часовой стрелке.
3. По принципу Дирихле, хотя бы одно из $n-1$ модифицированных множеств $T_i'$ содержит не менее $2$ чисел из тех, которые встречаются на карточках этого фокусника. Если $T_i'$ - тройка, то фокусник берёт упорядоченную пару $P_j'$, образованную из двух имеющихся чисел этой тройки, и иначе просто упорядоченную пару, соответствующую $T_i'$, и отдаёт её в этом же порядке третьему фокуснику.

Третий фокусник делает следующее:

1. Получив пару $(a_i',b_i')$ от первого фокусника, вычисляет разность $r=(b_i'-a_i') \mod (2n+1)$. Она равна разности до поворота круга, т.е. $r=r_i=(b_i-a_i) \mod (2n+1)$. Поскольку разности $r_i$ различны для всех $i$, то по $r$ однозначно восстанавливается номер пары $i$, а соответственно $a_i$ и $s=(a_i'-a_i) \mod (2n+1)$.
2. Аналогично проделывает первый пункт для второго фокусника и восстанавливает его сумму $s$.
3. Если $s_1$ и $s_2$ - числа, полученные на первых двух этапах, то, т.к. сумма всех чисел из $K$ по модулю $2n+1$ равна $0$, то номер на карточке, оставшейся у зрителя, равен $-(s_1+s_2) \mod (2n+1)$.

Теперь о том, как разбить множество $K$ при разных $n$. Числа в парах нужно брать в том же порядке, в котором числа записаны в соответствующем множестве. Так, в первом примере тройка $\{4,8,2\}$ даст пары $(4,8)$, $(4,2)$ и $(8,2)$ с разностями $4$, $9$ и $5$ по модулю $11$ соответственно.

$$\begin{tabular}{|l|l|l|l|l|} \hline \quad n=5 : & \quad n=6 : & \quad n=7 : & \quad n=8 : & \quad n \geqslant 9 : \\ \hline \{0, 3, 10\} & \{0, 5, 12\} & \{0, 4, 9\} & \{0, 4, 9\} & \{0, 2, 10\} \\ \{1, 7, 9\} & \{1, 3, 11\} & \{1, 7, 14\} & \{1, 7, 14\} & \{1, 4, 8\} \\ \{4, 8, 2\} & \{6, 7, 10\} & \{2, 3, 5\} & \{2, 3, 5\} & \{5, 6, 11\} \\ \{5, 6\} & \{8, 4\} & \{11, 6\} & \{15, 6\} & \{7, 3\} \\ & \{9, 2\} & \{12, 8\} & \{10, 8\} & \{9, 2n\} \\ & & \{13, 10\} & \{12, 11\} & \{2n-1, 12\} \\ & & & \{16, 13\} & \{2n-2, 13\} \\ & & & & \cdots \\ & & & & \{n+7, n+4\} \\ & & & & \{n+6, n+5\} \\ \hline \end{tabular}$$

[Edward_Tur]

Два фокусника показывают такой фокус.
Первый фокусник выходит из комнаты. Другой фокусник достаёт колоду из $100$ карт, занумерованных числами $1,2,...,100$, и просит трёх зрителей выбрать по одной карте. Посмотрев на выбранные каждым из зрителей карты, он добавляет к ним ещё одну карту из колоды. Зрители тасуют эти четыре карты и зовут первого фокусника. Он смотрит на четыре карты и угадывает, какую из них выбрал первый зритель, какую другой и какую третий.
Доказать, что фокусники могут договориться между собой так, чтобы всегда угадывать карты.

[Dave]

Любое число $n$ от $1$ до $100$ можно единственным образом представить в виде

$$n=16a+4b+c+1,$$

где $a,b,c$ - целые числа, $0 \leqslant a \leqslant 6$, $0 \leqslant b \leqslant 3$, $0 \leqslant c \leqslant 3$, причём, если $a<6$, то число $n$, задаваемое таким выражением, гарантированно попадёт в диапазон от $1$ до $100$. Пусть $i$-й зритель, $i=\overline {1,3}$, выбрал карту с номером $n_i=16a_i+4b_i+c_i+1$.

Тогда второй фокусник должен:

1. Подобрать число $b_4$ от $0$ до $3$, отличное от $b_1$, $b_2$ и $b_3$.
2. Взять $c_4 = (b_4-(c_1+c_2+c_3)) \bmod 4$.
3. Запомнив, какую карту дал каждый из зрителей, расположить их в порядке возрастания номеров и выбрать $a_4$, исходя из следующей таблицы:
   $\begin{tabular}{|l|l|} \hline a_4 & \text{Номера зрителей}\\ \hline 0 & \qquad 1, 2, 3 \\ 1 & \qquad 1, 3, 2 \\ 2 & \qquad 2, 1, 3 \\ 3 & \qquad 2, 3, 1 \\ 4 & \qquad 3, 1, 2 \\ 5 & \qquad 3, 2, 1 \\ \hline \end{tabular}$
4. Посчитать $n_4=16a_4+4b_4+c_4+1$, выбрать соответствующую карту, которая всегда будет отлична от трёх уже выбранных в силу выбора $b_4$, и отдать зрителям.

Первый фокусник делает следующее:

1. Восстанавливает $b_4=(c_1+c_2+c_3+c_4) \bmod 4$.
2. Определяет карту, добавленную вторым фокусником, исходя из того, что карта с $b=b_4$ ровно одна.
3. Располагает остальные три карты в порядке возрастания номеров и, зная $a_4$, по вышеприведённой таблице находит, какую из них дал какой зритель.

[Shadow]

У меня такой вариант: Первый фокусник должен угадать какая из 4-х карт кому из 4-х человек "принадлежит". Всего 24 вариантов, так что второй должен передать ему число от 0 до 23. И это будет сумма чисел на картах по модулю 24. Если расставить все карты в круг, то выбранные карты делят круг на 3 сектора. В наибольший сектор будут не менее 33 карт. Карта второго фокусника будет из этого сектора. Теперь он уже знает какое число должен передать и из 33 последовательных чисел может выбрать нужную карту (чтобы сумма 4-карт по модулю 24 была правильная)

-- 28.02.2012, 18:33 --

Shadow в сообщении #543543 писал(а):

Если расставить все карты в круг, то выбранные карты делят круг на 3 сектора. В наибольший сектор будут не менее 33 карт.

Корекция. Не в круг, а на прямую. Делит на 4 отрезка. В наибольший не менее 24 карт.

[hippie]

Edward_Tur в сообщении #543168 писал(а):

Два фокусника показывают такой фокус.
Первый фокусник выходит из комнаты. Другой фокусник достаёт колоду из $100$ карт, занумерованных числами $1,2,...,100$, и просит трёх зрителей выбрать по одной карте. Посмотрев на выбранные каждым из зрителей карты, он добавляет к ним ещё одну карту из колоды. Зрители тасуют эти четыре карты и зовут первого фокусника. Он смотрит на четыре карты и угадывает, какую из них выбрал первый зритель, какую другой и какую третий.
Доказать, что фокусники могут договориться между собой так, чтобы всегда угадывать карты.

А давайте усложним фокус.

Когда приходит очередь фокусника выбирать карту, зрители указывают ему одно из четырёх множеств: нижние (от 1 до 50), верхние (от 51 до 100), чётные или нечётные, из которого он и должен выбрать карту.
Первому фокуснику НЕ сообщают, из какого из четырёх множеств выбрал карту второй фокусник.

Доказать, что и в этом случае фокусники могут договориться между собой так, чтобы всегда угадывать карты.

[Dave]

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

Edward_Tur в сообщении #543168 писал(а):

Два фокусника показывают такой фокус.
Первый фокусник выходит из комнаты. Другой фокусник достаёт колоду из $100$ карт, занумерованных числами $1,2,...,100$, и просит трёх зрителей выбрать по одной карте. Посмотрев на выбранные каждым из зрителей карты, он добавляет к ним ещё одну карту из колоды. Зрители тасуют эти четыре карты и зовут первого фокусника. Он смотрит на четыре карты и угадывает, какую из них выбрал первый зритель, какую другой и какую третий.
Доказать, что фокусники могут договориться между собой так, чтобы всегда угадывать карты.

А давайте усложним фокус.

Когда приходит очередь фокусника выбирать карту, зрители указывают ему одно из четырёх множеств: нижние (от 1 до 50), верхние (от 51 до 100), чётные или нечётные, из которого он и должен выбрать карту.
Первому фокуснику НЕ сообщают, из какого из четырёх множеств выбрал карту второй фокусник.

Доказать, что и в этом случае фокусники могут договориться между собой так, чтобы всегда угадывать карты.

Задача заведомо неразрешима
Допустим, что зрители всегда выбирают $3$ карты из множества $D$ $25$ карт с чётными номерами от $2$ до $50$ и говорят второму фокуснику, что он должен выбрать карту также из этого множества. Если бы схема реализации фокуса существовала, то она задавалась бы неким отображением $f \colon A \to C$ из множества $A$ $3$-элементных размещений множества $D$ во множество $C$ $4$-элементных сочетаний множества $D$. При этом это отображение может, по желанию фокусников, быть неоднозначным, но обязано быть инъективным, т.е. образы двух разных элементов $A$ не могут пересекаться, иначе первый фокусник по точке пересечения не сможет однозначно восстановить её прообраз. Из инъективности $f$ следует, что количество элементов в $C$ должно быть не меньше количества элементов $A$, что не так, ибо $A_{25}^3>C_{25}^4$.

[hippie]

Dave в сообщении #543661 писал(а):

Допустим, что зрители всегда выбирают $3$ карты из множества $D$ $25$ карт с чётными номерами от $2$ до $50$ и говорят второму фокуснику, что он должен выбрать карту также из этого множества.

Но такого множества в условии нет. Множества допускаются только те, которые указаны в условии:
1) Нижние;
2) Верхние;
3) Чётные;
4) Нечётные.
(Каждое из множеств содержит по 50 элементов.)

При этом одной и той же карте нельзя присвоить разные "значения" в зависимости от того, из какого множества эта карта.
(Например карту с числом 50 из "нижнего" множества от карты с числом 50 из "чётных" первый фокусник отличить не может!)

[Dave]

Я исходил из того, что указанные четыре множества не пересекаются и образуют разбиение множества всех карт, а условия "нижние (от 1 до 50), верхние (от 51 до 100), чётные или нечётные" попарно комбинируются для того, чтобы получить эти четыре множества. Значит неправильно понял.
Когда множества в два раза больше, то решение, конечно, существует. Для этого нужно немного модифицировать моё решение исходной задачи. А именно, разложение $n=16a+4b+c+1$ заменяем на

$$n=50a+8b+2c+d+1, \eqno(1)$$

где $0 \leqslant a \leqslant 1$, $0 \leqslant b \leqslant 6$, $0 \leqslant c \leqslant 3$, $0 \leqslant d \leqslant 1$, $8b+2c+d \leqslant 49$. $b_4$ выбирается по тому же принципу, что и $a_4$ в предыдущем решении (всегда $b_4 \leqslant 5$, что обеспечивает $8b+2c+d \leqslant 47 <49$), после чего в распоряжении второго фокусника остаётся $16$ вариантов выбора $a$, $c$ и $d$, при этом зрители ограничивают один из битов $a$ или $d$ определённым значением, но из пары $(a,d)$ всё равно можно извлечь один лишний бит, даже несмотря на то, что первый фокусник не знает какой бит был ограничен, а именно рассматривая условный бит $e=a \oplus d$. Тогда, выбрав вначале пару $(c_4,e_4)$ так, чтобы она отличалась от любой из пар $(c_1,e_1)$, $(c_2,e_2)$, $(c_3,e_3)$, но в то же время из неупорядоченного набора четырёх таких пар можно было однозначно восстановить $(c_4,e_4)$, второй фокусник определяет "свободный" бит из пары $(a_4,d_4)$ так, чтобы $a_4 \oplus d_4=e_4$, подсчитывает $n_4$ по формуле $(1)$ и отдаёт соответствующую карту зрителям.
Первый фокусник считает все числа $c_i$ и $e_i=a_i \oplus d_i$, находит индекс $i$ карты второго фокусника, который после перемешивания не обязательно равен $4$, ну а дальше - по-старому: число $b_i$ даст нужный порядок.
О том, как выбрать пару $(c_4,e_4)$ или, переходя к представлению $f=2c+e$, число $f_4$ от $0$ до $7$, отличное от $f_1$, $f_2$, $f_3$, чтобы из неупорядоченного набора $(f_1,f_2,f_3,f_4)$ можно было однозначно восстановить $f_4$, пока умолчу, ибо, честно говоря, не уверен, что такое громоздкое решение кого-либо заинтересует.