Однако, можно сделать так, чтобы передаваемые карты содержали больше информации, если помнить о том, что помощник выбирает карты не случайно, а отбирает 4 карты из 5. Упомяну о трех различных вариантах решения задачи.
Во всех трех предполагается, что все карты колоды можно расположить по порядку. Сам порядок неважен, главное, чтобы он был одинаков у помощника и фокусника. Для меня, например, естественен «преферансный» порядок, по старшинству от двойки до десятки, затем от валета к королю, затем туз. Среди карт одного значения — например, среди шестерок — самая младшая шестерка пик, затем, по порядку старшинства, треф, червей и бубен. Если вы играете в бридж, удобный порядок для вас будет другой. Сейчас важно, что порядок возможно установить.
Первый вариант — «эстрадный», который легко запомнить и удобно показывать.
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=2){kind=small}
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—1 | 6 |
| 3—1—2 | 5 |
| 2—3—1 | 4 |
| 2—1—3 | 3 |
| 1—3—2 | 2 |
| 1—2—3 | 1 |
Само собой, числа от 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).
Комментарии (0)