?

Log in

No account? Create an account

Previous Entry | Next Entry

Карточный фокус, о котором я писал на прошлой неделе, исполни́м. На первый взгляд кажется, будто передаваемые карты не содержат достаточного количества информации. На самом деле, 4 карты можно передать в разном порядке 4!=24 способами, а пятая карта может быть одной из 52−4=48. И это действительно так: передать 4 случайные карты, чтобы однозначно указать на пятую, тоже случайную, нельзя.

Однако, можно сделать так, чтобы передаваемые карты содержали больше информации, если помнить о том, что помощник выбирает карты не случайно, а отбирает 4 карты из 5. Упомяну о трех различных вариантах решения задачи.

Во всех трех предполагается, что все карты колоды можно расположить по порядку. Сам порядок неважен, главное, чтобы он был одинаков у помощника и фокусника. Для меня, например, естественен «преферансный» порядок, по старшинству от двойки до десятки, затем от валета к королю, затем туз. Среди карт одного значения — например, среди шестерок — самая младшая шестерка пик, затем, по порядку старшинства, треф, червей и бубен. Если вы играете в бридж, удобный порядок для вас будет другой. Сейчас важно, что порядок возможно установить.

Первый вариант — «эстрадный», который легко запомнить и удобно показывать. dimmik нашел точное решение, и ni4_gaja_foksa была в одном маленьком шаге от него. Секрет этого фокуса такой. Среди 5 карт можно выбрать 2 одной масти, потому что мастей всего 4. Помощник особым образом выбирает одну из них и передает первой. Таким образом, первая переданная карта обозначает масть «секретной» карты. Оставшиеся три карты можно передать 3!=6 разными способами по порядку, таким образом, передав число от 1 до 6. Этого недостаточно, чтобы передать значение спрятанной карты, однако вспомним, что фокуснику передана одна карта той же масти, то есть в масти осталось 12 карт. Если мы расположим 13 значений карт по кругу (представьте часы, только не с 12 часовыми делениями, а с 13), то от одной из них до другой всегда можно дойти по часовой стрелке, сделав от 1 до 6 шагов. Например, от {2} до {8} 6 шагов: {3}, {4}, {5}, {6}, {7}, {8}. Если мы выберем {2} и {9}, то шагов тоже будет 6, только идти надо от {9} к {2}: {10}, {В}, {Д}, {К}, {Т}, {2}. Как мы видим, если выбрать одну из двух выпавших в масть карт, то числа от 1 до 6 достаточно, чтобы указать вторую. Передавая первую карту, помощник должен выбрать ту, от которой «по часовой стрелке» до другой идти не более 6 шагов. Первая переданная карта, таким образом, задает масть и точку отсчета, а три следующие своим порядком кодируют число шагов, которые надо отсчитать от значения первой карты, чтобы указать на спрятанную.

Число от 1 до 6 передается порядком карт так. Три переданные карты в уме надо отсортировать по старшинству; обозначим их в этом порядке числами от 1 для самой младшей до 3 для старшей из трех. Если первой передана самая младшая карта, то число шагов равно 1 или 2, если средняя, то 3 или 4, если старшая — 5 или 6. Выбрать меньшее или большее число шагов позволяет вторая переданная карта: если она старше третьей, то берется большее число шагов, если младше — меньшее. Это простой способ запомнить такую таблицу:

Если карты переданы
в порядке...
то число
шагов равно...
3—2—16
3—1—25
2—3—14
2—1—33
1—3—22
1—2—31

Само собой, числа от 1 до 6 в правой колонке тоже могут быть расставлены вами с помощником любым произвольным образом, лишь бы он был известен вам обоим. Предложенная мнемоника — только один из вариантов, удобный мне самому; ваш может быть и иным.

Например, пусть пять выбранных карт будут {3♠}, {7♠}, {Т♠}, {9♥}, {Т♦}. Помощник выбирает две любые карты одной масти, например, {3♠} и {7♠}. Путь от {3} к {7} укладывается в 4 шага, меньше максимального значения 6 шагов, поэтому первой помощник передаст {3♠}, а {7♠} отложит как карту, которую затем угадает фокусник. Теперь помощник должен передать фокуснику число шагов, 4, с помощью 3 карт, которые по возрастанию значения ложатся так: {9♥}, {Т♠}, {Т♦}. Первой он передаст среднюю из них, {Т♠}, чтобы сказать, что шагов «3 или 4». Второй передается {Т♦}, бо́льшая из двух оставшихся, чтобы указать на бoльшее число из 3 и 4, переданных первой картой, то есть на число 4. Последней из трех помощник отдаст фокуснику {9♥}. Получив все три карты и видя их относительный порядок, фокусник проделывает в уме те же рассуждения, получает число 4, отсчитывает именно столько шагов от переданной ранее {3♠}, получая в ответе {7♠}, и называет ее, приводя ученую публику в восторг.

Где-то здесь быть бы сказанным словам «счет по модулю 13», но в описании фокуса я решил обойтись без них.

Второе решение, которое интересно рассмотреть, связано с обобщением исходной задачи: оно отвечает на вопрос о том, какое наибольшее количество информации можно передать пятью картами, или, иначе, каково максимальное число карт в колоде, при котором можно из пяти выбрать четыре, однозначно указывающие на пятую из них. Очень подробное конструктивное решение замечательно описывает falcao, так что нет никакой нужды здесь его пересказывать. Скажу лишь, что в ответе получается 124 — именно столько различных карт может быть в исходной колоде, чтобы фокус можно было проделать. Более общие вычисления несколько сложнее, но тоже вполне могут быть проделаны в уме. Если фокус с колодой карт будет общеизвестен и скучен, можете показывать его с колодой из 124 пронумерованных карточек.

Третья задача и решение — обобщение второй на n выбираемых карт, а именно, каков максимальный размер колоды, при котором помощник передает фокуснику n−1 карт, однозначно указывая на оставшуюся. Это решение подробно рассматривает М. Клебер[1]. В общих чертах, как верно заметил dimmik в одном из комментариев, легко найти верхнюю границу числа карт в такой колоде. Всего возможных вариантов выбора n (неупорядоченных) карт из колоды в N



Фокуснику передается n−1 упорядоченных карт, и всего возможных вариантов таких наборов в колоде



Сравнивая знаменатели, видим, что количества переданной и полученной информации сравниваются при условии



и, таким образом,



Например, для n=5 карт получаем уже знакомый нам максимальный размер колоды N=124. Однако, это лишь верхняя граница: с 5 картами фокус с колодой из более чем 124 карт точно не удастся. Но то, что найдется алгоритм кодирования информации для 124 карт (или какого-то меньшего числа) — это из нашего рассуждения никак не следует.

М. Клебер в своей статье доказывает, что верхняя граница всегда достижима при любом заданном n, то есть, существует алгоритм, позволяющий осуществить фокус при нашем максимальном вычисленном объеме колоды. Доказательство я здесь повторять не буду, потому что оно приводится в статье; упомяну лишь, что в нем используется теорема Бирхофа — фон Неймана о выпуклой оболочке множества матриц перестановок и теорема Холла о свадьбах. Желающим докопаться до самых глубин рекомендую прочитать саму статью.

_________________________
1. Michael Kleber. The Best Card Trick. Mathematical Intelligencer 24 No. 1 (Winter 2002).

Tags:

Comments

( 9 comments — Leave a comment )
brutal_radish
Mar. 25th, 2011 01:31 pm (UTC)
Здравствуйте
Спасибо. Очень понравился Ваш блог
(Anonymous)
Mar. 25th, 2011 03:43 pm (UTC)
Не очень понятно, что произойдет в случае выбора 4 карт одного достоинства + 1 любую. Я выбрал 4 туза и, например, даму и передал вашему помощнику. Epic fail?
3bl
Mar. 25th, 2011 03:46 pm (UTC)
Пардон, подумал внимательнее, масти также имеют старшинство...
Выше мой же коммент, просто без авторизации.
fat_crocodile
Mar. 25th, 2011 04:16 pm (UTC)
> Если мы расположим 13 значений карт по кругу (представьте часы, только не с 12 часовыми делениями, а с 13), то от одной из них до другой всегда можно дойти по часовой стрелке, сделав от 1 до 6 шагов.

О! Это круто. До этого я не додумался.
ushastyi
Mar. 29th, 2011 01:15 pm (UTC)
Я прочитав задачу, отложил ее "на потом" и подумал как-то перед сном. Получился вариант близкий к варианту уважаемого falcao, с той лишь разницей, что поскольку карт всего 52 и 4 из них известны, то достаточно закодировать оставшиеся 48. То есть помимо 24 вариантов из 4 выбранных карт достаточно передать еще один бит информации. Что можно сделать, например четностью (то есть оставлять всегда четную карту, кроме случая, когда все нечетные, и угадывающий из четности 4х карт получает этот бит).
fregimus
Mar. 29th, 2011 06:22 pm (UTC)
Да, тут возможно много вариантов. С четностью не понял: первый расклад — 1 четная из 5, второй — все нечетные. Как их отличить?
184467440737095
May. 15th, 2011 09:54 pm (UTC)
эта задача в том числе была на турнире городов году в ~98-м.
fregimus
May. 16th, 2011 12:56 am (UTC)
А я даже никогда не слышал о турнире городов. Любопытно.
nik_vic
Jan. 13th, 2012 12:42 pm (UTC)
теорема Бирхофа — фон Неймана
Есть и элементарное построение. Карты "надписываются" числами 0..123, пятёрка выстраивается по порядку, "выкидывается" карта, порядковый номер которой в этом порядке(из 0..4) равен сумме (по модулю 5) надписанных чисел.
Для реализации обратного перехода используется одна из 24-х перестановок.
( 9 comments — Leave a comment )