Карточный фокус

[fregimus]

Я даю вам обычную стандартную колоду из 52 карт. Вы выбираете из нее 5 карт любым способом и отдаете моему помощнику. Помощник передает мне по очереди 4 карты, я называю их вслух, а затем… называю и пятую!

Как это у меня так получается?

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

Доб 2. Хорошо бы еще система кодирования была практичной, чтобы помощнику и мне не надо было помнить громоздких таблиц или считать факториалы. Этот фокус действительно можно показывать после небольшой тренировки.

Comments

[aamonster.livejournal.com]

То ли у Дьюдени, то ли у Гарднера было злее - там битов на кодирование якобы не хватало =).
А тут интересно посчитать, для какого максимального размера колоды метод сработает.

[fregimus.livejournal.com]

Четырьмя картами можно закодировать, на первый взгляд, 4!=24 варианта. Недостаточно, чтобы назвать оставшуюся карту. Казалось бы.

[aamonster.livejournal.com]

Лично мне так не кажется. Вполне очевидно, что в данном случае можно закодировать больше (ведь помощник выбирает не только порядок 4 карт, но и то, какие 4 карты из 5 отдавать), только что-то никак не посчитаю, сколько именно.
В книжке же битов не хватало жёстче, и там был уже не математический трюк =) (да, карты в конверте подсовывали под дверь номера в гостинице).

[autoench.livejournal.com]

Прибавим еще 4 бита на то, правой или левой рукой передается карта.

[aamonster.livejournal.com]

Не, тут можно без этого. Считайте, что передаётся список из 4 номеров карт.

[autoench.livejournal.com]

В условии задачи этого не написано %)

[aamonster.livejournal.com]

Ну да, но если использовать такие трюки (можно ещё передавать их лицом или рубашкой вверх, по разному держать и так далее) - то можно на сами карты вообще не смотреть =). Так что интереснее рассматривать задачу в "математической" постановке.

[fregimus.livejournal.com]

Нет, это математическая задача. Щипать под столом и подмигивать не будем.

[autoench.livejournal.com]

Задавая математические задачи, неплохо бы научиться точно формулировать условие. Согласитесь, в заданном вами условии задача решена.

[fregimus.livejournal.com]

Хорошо. Вы всех победили. Поздравляю.

[aamonster.livejournal.com]

Да, метод, который, скорее всего, используется в фокусе: пятая карта того же цвета, что большинство из переданных (а если их поровну - то, скажем, красная). Это нам гарантирует в худшем случае выбор из 24 вариантов.

Но понятно, что это - не полное использование канала для передачи информации, и можно работать с большей колодой.

[janatem.livejournal.com]

И какую выбрать из 3 черных и 2 красных?

[aamonster.livejournal.com]

Упс... :-)

[dimrub.livejournal.com]

Допустим, что все 52 карты у нас пронумерованы (т.е. карта - это просто число от 1 до 52). Допустим также, что помощник выбирает четыре карты так, чтобы пятая была либо меньше их всех, либо, наоборот, больше (если при упорядочении пяти карт по ранжиру - c1, c2, .. c5 получается, что с2 - 1 <= 52 - c4, то выбирается c1, в обратном случае - c5). Тогда легко видеть, что для оставшейся пятой карты остается 24 варианта. Это ровно столько, сколько есть способов упорядочить оставшиеся 4 карты. Каждому из упорядочиваний ставится в соответствие один из 24 вариантов для c1/c5.

[fregimus.livejournal.com]

Одного бита не хватает в Вашем решении: больше или меньше карта, чем переданные.

[plakhov.livejournal.com]

у вас может быть даже 388 карт )
правда, в такой постановке зрители быстро разгадывают фокус!

[fregimus.livejournal.com]

Нет, не более 124.

[localghost.livejournal.com]

Ой, интересно, а я знаю решение, где, кажется, один-в-один хватает на 52 карты.

[fregimus.livejournal.com]

Я думаю, решений даже и не одно. Рассказывайте, если догадались!

[localghost.livejournal.com]

Ну я не догадался, а знаю, как раз после того Турнира городов, видимо, мне ее рассказывали, поэтому отправил удаленным комментарием.

[janatem.livejournal.com]

Ограничение в 124 мне мне представляется очевидным (4 + 5!), но я пока не понимаю, как к нему можно приблизиться. Даже не решил пока, как для случая 52 передать недостающий бит выбором одной (секретной) карты из пяти...

[baph.livejournal.com]

А ответ для несообразительных будет?
Например я выбрал 2 бубей, даму червей, даму пик и 10 червей. Какая 5-я?

[fregimus.livejournal.com]

Какая пятая — зависит от того, в каком порядке мне передаст эти 4 карты помощник. :-)

[baph.livejournal.com]

Ок. Если 5-я 9 бубей, какой будет порядок?

[localghost.livejournal.com]

Например, двойка бубей, дама червей, 10 червей, дама пик.

[fregimus.livejournal.com]

9 бубей, дама червей, дама пик, 10 червей. Я назову 2 бубей.

[localghost.livejournal.com]

Стоп-стоп, вы (как зритель) выбрали *пять* карт, а не четыре. А уж какие из них отдал фокуснику помощник - он сам решит.

электронный помощнег

[falcao.livejournal.com]

У меня это было подробно описано -- я студентам демонстрировал этот фокус. В роли "помощнега" выступал я сам, а в роли меня -- "лэптоп": они туда сами заносили данные, а он выдавал ответ.

http://falcao.livejournal.com/180432.html

Re: электронный помощнег

[fregimus.livejournal.com]

Есть гораздо более практичный способ кодирования, когда считать почти ничего не надо. Годится для демонстрации фокуса прямо на ходу. Угадаете?

принцип отбора

[falcao.livejournal.com]

Я вряд ли угадаю, потому что задачу эту знаю давно, и ничего более простого мне никогда в голову не приходило. В принципе, я все требуемые вычисления (как в плане "кодирования", так и в плане "декодирования") легко осуществляю в уме. Но было бы интересно узнать, какой способ Вы имеете в виду. Тут ведь важен прежде всего принцип отбора оставляемой карты. Он у Вас такой же или другой?

Re: принцип отбора

[fregimus.livejournal.com]

Способ, который я знаю, работает только для колоды карт. Вашим способом можно угадать пятое по четырем из максимально возможных в принципе 124 чисел, а этим — только из 52, и он оптимизирован для человеческого пользования именно за счет уменьшения количества возможных чисел. Там mod 4 и mod 13 в кодировании используются, как совершенно естественные именно для карт.

Я расскажу обязательно, когда все надумаются, ладно?

равномерный выбор

[falcao.livejournal.com]

Если речь не идёт об использовании этого дела "под завязку", то могут быть, конечно, разные упрощения. Но я когда решал эту задачу много лет назад (она была на Турнире Городов), то сразу исходил из принципа равномерного выбора карт, и потом проверил, что он работает для максимального числа.

Ваш способ любопытно будет прочитать. Это планируется сделать в отдельном посте, или здесь же?

Re: равномерный выбор

[fregimus.livejournal.com]

Да, Ваше решение полное. Пожалуй, оно и вправду немногим сложнее, надо просто алгоритм хорошо запомнить, а вычисления ведь несложные.

Наверное, лучше в отдельном.

[sizif73.livejournal.com]

Исключительно размышления вслух.
Первая поданная карта делит массив карт на две части, она же может указывать, в какой половине загаданная. Последующие делят оставшуюся часть.

[fregimus.livejournal.com]

Не хватит карт. Четыре раза поделить 48 карт — получатся кусочки по 3.

[spamsink]

Я эту задачу знаю давно, со способом кодирования, видимо, таким же, какой знает falcao (Зная преферанс или бридж, им пользоваться очень легко - главное, не перепутать). Интересно, как можно проще.

[fregimus.livejournal.com]

Проще — это кому как проще. Я расскажу через пару дней.

[spamsink]

Прочитав falcao внимательно, я понял, что знал не falcaoвский способ кодирования, а Ваш.

[dimmik.livejournal.com]

Самый простой вариант - помощник отдает их вверх или вниз рубашкой, кодируя тем самым одно из 13 чисел, последняя из четырех - той же масти что и оставшаяся у помощника.

Есть еще чисто математические мысли, но пока не сходится...

[fregimus.livejournal.com]

Нет, у фокуса чисто математические решение есть.

[ni4-gaja-foksa.livejournal.com]

в 5 картах у нас всегда будут хотя бы две одной масти. одну из них помошник откладывает как пятую, вторую передает первой. таким образом, первой картой он сообщает масть финальной карты. остается 13 вариантов (потому что масти 4 штуки).
мы передаем 4 карты, каждую из них можем передавать прямо или перевернуто (либо рубашкой вверх/вниз, либо - чтобы не так заметно - торцом или длинной стороной к фокуснику). то есть каждая карта - это 0 или 1, к концу передачи карт получается, что фокусник знает число в двоичном коде из 4 позиций, плюс еще и масть. двоичное число такого масштаба быстро переводится в 10-ричное исчисление (реально быстро). при этом 2 кодируется 2-кой, 3 -3 итд (запоминать надо только что валет - 11, дама - 12, король - 13 и туз - 14)

[ni4-gaja-foksa.livejournal.com]

и еще проще:
первая карта несет информацию о масти и "знаке": если мы ее даем прямо, то это значит "+" , а если повернутой, то "-". следующие карты - это "3", "2", "1" к номиналу первой. прямое положение следующих карт - "не считается", повернутое - "считается". то есть я даю первую карту определенным номиналом, с помощью следующих я могу номинал карты увеличить или уменьшить на 1,2,3,4,5 или 6 пунктов - таким образом мы получаем число - номинал 5 карты. то же самое, что и предыдущий вариант, но не надо из двоичной переводить:)

[fregimus.livejournal.com]

Вы в одном шаге от хорошего решения. Оно чисто математическое, вся информация кодируется номиналом карт, никакой ловкости рук с рубашкой не требуется.

[ni4-gaja-foksa.livejournal.com]

меня пугает ситуация, когда на руках у помощника окажется, например, 8 червей, 8 треф, 8 бубен, туз пик и 10 пик. Тогда туза или 10 он отдаст первыми, чтобы сообщить масть. а с помощью трех 8-к не получится же воспользоваться номиналом.

[fregimus.livejournal.com]

С помощью трех карт можно передать 3!=6 различных сообщений (то есть, например, число от 1 до 6).

[dimmik.livejournal.com]

О.
Итак, две карты из 5 у нас гарантированно одной масти.

Если все карты перенумеровать от 0 до 51, то первые три можно передать одним из 6 способов (среди них будет 1-я, 2-я и 3-я - соответственно, шесть перестановок:
123
231
312
132
321
213
).

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

Первыми тремя картами мы кодируем это самое расстояние, четвертая - "первая" от которой считать это расстояние "вперед".

Пример:
Выбраны
2т, 3т, 4т, 6п, тп.
Выбираем в качестве "двух карт одной масти" 6п и тп.
Между ними "расстояние" 5: т -> 2 -> 3 -> 4 -> 5 -> 6
Соответственно, первыми тремя число 5 (4т, 3т, 2т == 321), четвертой выдаем тп.
Вычисляем что наша - 6п.

Я думаю, идея понятна, еще подумаю как более лаконично сформулировать.

[fregimus.livejournal.com]

Совершенно верно. Именно этот способ я и знаю.

[dimmik.livejournal.com]

Альтернативный, "более сложный в реализации", но более простой в формулировке вариант:
Перечисляем все сочетания из 52 карт по 4 (их 270725), составляем таблицу соответствия каждого осташвейся карте.
И имеем таблицу у ведущего и помощника.

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

[fregimus.livejournal.com]

Marriage Theorem?
http://www.cut-the-knot.org/arithmetic/elegant.shtml