у меня есть стойкое чувство, что 52 карты - максимум. однако, доказать, что путём выбора одной карты из пяти, больше одного бита не передать, не смогу никак

Это сообщение отредактировал Vot_Blin - 15/01/2009, 22:45

да, 52 карты определённо максимум. Оптимальная стратегия в загадывании карт из как минимум дублетной масти - тут согласились все. Тогда партнёр видит одну карту в масти и остаётся передать номер одной карты из 12. 3 других карты, из которых мы изначально достоверно не знаем ничего, ни ранга, ни масти имеют 3!=6 вариантов расположения. Ещё один бит информации передаётся тем, что партнёр знает нашу стратегию прятанья двух карт в масти. Больше нельзя по определению, ибо у нас изначально в худшем случае всего 2 карты в длиннейшей масти, а значит всего 2 возможности выбора - прятать старшую и прятать младшую. Больше одного бита передать уж точно не получится. Способ tgeorge понравился, хотя можно и так - если у карт одинаковая чётность, то прячем младшую, а если разная чётность - старшую. Тогда видя, например, чётную карту, партнёр знает, что у нас либо нечётная карта младше, либо чётная карта старше - всего 6 возможностей, которые мы передаём тремя остальными картами.

Это сообщение отредактировал pactamah - 18/01/2009, 03:02

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

Про мой обещанный изначальный алгоритм для 52 карт.
(в реальных условиях не слишком удобный)

Без потери общности забываем про масти и номиналы карт – у нас просто 52 различные упорядоченные точки на окружности. По условию задачи (задано 5 точек) мы имеем разбиение окружности на 5 соприкасающихся дуг длиной от 1 до 48 (это легко сообразить). Сумма длин всех дуг очевидно равна 52. Для определённости зададим направление движения (отсчёта) на окружности – «по ходу часовой стрелки» (но можно и наоборот).

Правило отбрасывания.
Находим среди 5 дуг самую длинную. В случае, если таких дуг более одной, то из них выберем произвольную обособленную (т.е. , не смежную с такой же длинной дугой) либо, если обособленных нет (все длинные идут плотно в ряд), то возьмём первую из ряда (ведь такая обязательно найдётся, т.к. 52 не делится на 5 без остатка).
Итак, выбрана Большая Дуга. Рассмотрим смежную ей меньшую Малую Дугу. Длина МД не может быть больше 24. И это легко доказать: если она больше 24, то БД больше 25 и, далее, сумма всех дуг становится больше 52. Пограничная точка между выбранными БД и МД – искомая. Её мы и выбрасываем. При помощи 4-ёх оставшихся точек формируем 24-вариантный ключ, кодируя длину МД.

Правило восстановления.
Глядя на окружность с 4-мя точками выбираем Самую БД (такая очевидно есть и она ровно одна) и вставляем туда пятую (выброшенную) точку, прибавляя значение ключа (число от 1 до 24) к начальной точке этой дуги.


(Можно было и без окружности обойтись, она просто для наглядности взята)

Для начала Джиму первое место за решение.
Второй приз присуждаю своему решению.
2.....Четыре карты рассматриваем в двоичном коде. "0" - мордой вниз, "1"- открытая.
Прелесть решения в том, что номинал карты отражаем самым непосредственным образом:
- семерка = 7,
- десятка = 10,
- Король = 12 и т.п.
Да, масть показываем первой открытой картой слева. (идею повторения мастей конечно используем).
========================
Теперь будем считать, что все карты должны быть открыты и лежать смирно.
Тогда есть решение очень похожее на задуманное автором.
1.Две карты одной масти понятно.
Представим карты в виде непрерывного кольца, -К-Т-2-3-..-Д-К-
Условимся считать только "вверх", тогда от одной карты (которую оставим) до второй карты (которую спрячем)всегда будет "вверх" от 1 до 6-ти.
Ибо всего 13.
2."Одномастную" карту кладем первой ,обозначая масть.
3.Три оставшиеся карты всегда можно разложить по старшинству. (если одинаковые номиналы, то по старшинству мастей).Тогда имеем ровно 6 перестановок.
(Например 3,9,К это =1 : 9,3,К =2 и т.д.)
Прелесть этого решения в строгой достаточности. Ни прибавить, ни убавить.

2Олежек ну давай, закодируй мне пожалуйста п:Т2 т:3 б:9 ч:К. Разность меньше 6 говоришь?

Т,3,9,К (2 пик под .опой)
=============
Давай посложнее !

Если не ошибся, что маловероятно, то есть решение:



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

До последнего момента думал, что решение-96 не единственное (симметричные варианты не в счёт). Сейчас в этом не столь уверен. Дело том, что всё время казалось, что остается много неиспользуемой информации. Поэтому последние три недели пытался ее утизизировать и увеличить потолок размера колоды до 100 карт. Много раз казалось, обычно умозрительно, что вот оно - решение! Но всегда находилась ошибка. Правда, еще пара неопробованных идей осталась...

Если будет время, попробую написать две маленькие программки: одна прячет карту, другая угадывает. Хотя алгоритм вполне можно уложить в голове.

Классная задачка! Процесс решения увлекательный, попробуйте!

Уважаемый зенкер!
Позволю слегка подшутить - "увлекательность" процесса решения сильно зависит от условий задачи, которые Вы себе сформулировали :))
------------
1. "Улучшенный Хокинс". Используем такую понятную вещь как циферблат часов.
Тогда получим 12*4 =20736! Ту же цифру, что и сам Джим, только "по человечески".
Учитывая,что считаем только "вверх", умножаем еще на 2.
(чем циферблат хуже шахматной таблицы ?)
2.В картах абсолютно естественным выглядит расположение карт и вверх и вниз рубашкой.
В пасьянсах карты располагаются рядами и колоннами.
Это дополнительный источник информации, или ?
3.Можно еще "задуманную" карту "спрятать" путем переворачивания !
Тогда к 6-ти перестановкам добавиться еще 18, итого 24.
Получится 49 карт в одной масти.
Разве не изячно ?!
4. А вот еще красивое решение!
Карту обозначающую масть кладем на стол.
Следующую карту, которая кодирует "расстояние" кладем справа как раз на искомом "расстоянии".
Спрашивается, а как точно определить это "расстояние" ?
Так у нас для этого есть еще две карты! Мы их последовательно перекладываем одну за другой и считаем "расстояние".

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