12 авг. 2011 г.

Карты и теория кодирования

Добрый день.

Можно учить теории кодирования (или любому другому разделу математики) традиционно: читать скучные лекции, формулировать непонятные леммы, доказывать ненужные теоремы... А можно показать всего один карточный фокус, чтобы удивить и заинтересовать, а уже потом читать интересные лекции и доказывать нужные теоремы.

Кстати, вчера вышла статья «iPad за партой. Заменят ли планшеты учебники?», для подготовки второй половины которой у меня взяли интервью. Я скептически отношусь к полезности подобной электроники в школе, но отлично понимаю, что хорошая идея и на плохой технике сработает, а плохая идея и на суперкомпьютерах не принесёт плодов. Другими словами, если всё делать грамотно, то и на iPad, и на более бюджетных устройствах можно хорошо обучать. Ниже я предлагаю описание фокуса, для демонстрации которого хватит колоды карт и любого компьютера или даже смартфона (вообще говоря, пару десятилетий назад и человек справлялся, но сейчас это может выглядеть не так эффектно).

На столе стоит компьютер-фокусник (считаем, что без камеры, микрофона и сети). Обычная колода из 52 карт отправляется в аудиторию, откуда возвращаются 5 случайно выбранных карт. Лектор одну из этих карт кладёт на стол, а оставшиеся четыре называет помощнику, который, не зная карту со стола, последовательно нажимает на клавиатуре 8 кнопок (для каждой из четырёх карт сначала масть, а потом достоинство). После этого на экране компьютера появляется изображение пятой карты. Как ему это удаётся?

Надо исходить из того, что это не обман, а математическая задача (то есть, хитрость не в том, что ещё один помощник «как-то через blue-touth с сотового телефона сообщил компьютеру о пятой карте»). Да, всё очень честно! Этот фокус может ошарашить и удивить. Но если вдуматься, то окажется, что это всего лишь математическая задача, которую может решить любой студент.

Давайте сравним количество информации (мы и раньше решали задачи про количество информации), которую ввели в компьютер, с объёмом данных, который он должен вернуть.

Проще всего разобраться с выходными данными: раз всего карт 52, то компьютер, чтобы сообщить достоинство и масть карты со стола, должен вернуть число от 1 до 52 (т.е. всего 52 варианта).

А что со входными данными? Четыре карты можно сообщить 4! = 24 разными способами (меняя порядок карт). Не так уж и мало, хоть и меньше необходимых 52. Как же двигаться дальше? Надо поискать, где ещё можно спрятать хоть чуть-чуть информации.

Предлагаю в комментариях поделиться своими идеями, как подвинуть эти две оценки друг к другу, чтобы стало понятно, как обучить компьютер этому фокусу.

Хорошего дня!

(А если вы уже знаете эту задачу, то предлагаю её «небольшую модификацию»: добавим в нашу колоду джокера, тем самым расширив её до 53 карт. Всё остальное прежнее: выбираются 5 случайных карт, одна кладётся на стол, а оставшиеся четыре сообщаются компьютеру)

32 комментария:

  1. Про каждую карту можно сначала сообщать масть, потом достоинство, а можно наоборот. Но тогда 24*16 сильно больше нужных 52, так что это вряд ли ожидаемый ответ.

    ОтветитьУдалить
  2. Анонимный12.08.2011, 0:44

    если рассматривается вариант, когда помощник в курсе что за карта осталась и "помогает" компьютеру, то 8 нажатий можно рассматривать как 8 битное кодирование значения. 0 нажатие клавиши меньше какого-то времени, 1 - больше. и пожалуйста, хоть 2 колоды карт с определением из какой колоды осталась, все равно 256 значений.

    ОтветитьУдалить
  3. На первый взгляд ни одной идеи! И вообще это кажется невозможным и невероятным. Я просто не знаю, с какого конца подойти к задаче. С нетерпением жду решения.

    ОтветитьУдалить
  4. Обратите внимание вот на какой момент - для передачи значения искомой карты необходимо передать 6 бит информации: 2 бита на определение масти и 4 бита на определение значения карты.
    4 бита на значение карты передаются легко - назвая, к примеру, масть перед значением карты получаем 0, значение перед мастью - 1. итого 4 карты - 4 бита - 16 значений, чего с лихвой хватает на определение значения карты, даже джокера не проблема передать.

    А вот откуда взять ещё два бита... Думаю, можно как-то их передать, поределяя порядок передачи карт. Скажем, повышение номинала карты - 1, уменьшение номинала - 0. Только вот как быть со случаем, когда номиналы трёх или четырёх карт совпадают...

    ОтветитьУдалить
  5. Мне не хватает строгости, но общая идея такая:

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

    (52-4)/2 - как раз 24.

    Считаем, что все карты однозначно нумерованы, в результате из этих четырёх сказанных распределение будет одним из четырёх (0/1/2 вверху, 4/3/2 внизу == загаданная внизу, 3/4 вверху, 1/0 внизу - загаданная вверху).

    ОтветитьУдалить
  6. Анонимный12.08.2011, 2:52

    Если порядок указания масти карты и её значения не фиксирован, то появляется еще одна "степень свободы", соответственно число комбинаций 24*2=48 (как раз количество карт за исключением названных 4-х)

    ОтветитьУдалить
  7. С одной стороны, компьютер после получения информации о 4 картах должен выбрать уже только одну из 48, а не 52. Со стороны лектора, задача стоит иначе - не в каком порядке передать 4 карты (тогда действительно только 24 варианта), а как из 5 карт выбрать 1 и какой порядок сформировать из оставшихся 4 карт. К примеру, какая-то масть обязательно в 5 картах встретится два раза. Пусть карта этой масти всегда идет первой, а другая остается неизвестной - уже доп. инф. Тогда значение карты задается порядком оставшихся трех карт (3! = 6), а значений всего 12 (без той, что дали компьютеру) - не сходится :). Хорошо, пусть, дополнительно, первая карта тоже несет информацию . Например, располагаем все карты одной масти по кругу. Смещением между двумя картами назовем расстояние между ними, если обходить их по часовой стрелке. Таких смещений будет для двух карт два - одно больше или равно 6, другое меньше или равно 6. Вот и будем передавать первой ту карту, смещение от которой до неизвестной меньше или равно 6.

    ОтветитьУдалить
  8. lenesh, верное замечание. Спасибо, я поправил условие, указав, что сначала в компьютер вводят масть каждой карты, а потом её достоинство (иначе получается слишком просто).

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

    Но Вы верно подметили, что компьютер должен назвать не одну из 52 возможностей, а одну из 48.

    Александр, Вы почти всё рассказали :)

    ОтветитьУдалить
  9. На хабре месяц назад была статья с исследованием на тему «Какие книги лучше — электронные или бумажные?» http://habrahabr.ru/blogs/ebooks/123647/
    По опыту — читать художественную литературу на электронной книге приятнее некуда, а вот учебники и научпоп лучше иметь в бумаге.

    ОтветитьУдалить
  10. Вначале хотел предложить достать лишний бит путем множественного именования карт ("восемь ←→ восьмерка"), потом понял, что не могу придумать альтернатив для картинок.

    ОтветитьУдалить
  11. sash-2003, да нет, тут всё без обмана.
    Карты называют одними и теми же именами (собственно, для этого я и написал, как их сообщают компьютеру). Никто не хитрит! Всё дело только в порядке тех четырёх карт, которые вводят в компьютер.

    ОтветитьУдалить
  12. Да, Александр уже всё практически рассказал.
    Идею с совпадением первой карты с нужной по масти достаточно быстро нашел сам, идею со смещением даже с подсказкой не сразу понял.
    Осталось сформулировать то, как оставшимися тремя совершенно случайными картами закодировать число от 1 до 6-ти. Но это уже достаточно тривиальная задача - оставшиеся три карты распределяем по старшинству и "весу" масти (можно преферансную схему) и назначаем номер от 1 до 3. И уже в зависимости от того, в какой последовательности эти номера были введены - определяем значение смещения.

    ОтветитьУдалить
  13. Решение для 52 карт уже прозвучало. Но я вот довольно напряженно думал как его размножить до 53 карт. Тут гораздо интереснее. Пока что не получается. Пробовал принципиально другие подходы, но пока что ответ не нашел.

    ОтветитьУдалить
  14. Раз уж я все равно болею, и потому не могу работать, а задачка в голове крутится, то вот подход для 53 карт:
    если джокера нет среди отобранных 5 карт, то
    алгоритм как для 52 карт
    если джокер среди отобранных 5 карт, то
    если среди 5 есть две карты одной масти, то
    алгоритм как для 52 карт, и джокер среди указующих 3 карт, причем считается за самую большую карту
    если отобраны все карты разной масти и джокер, то джокер выдается первым, и указывает на отсутствующую масть. Но вот непонятно, как узнать значение скрытой карты... (

    ОтветитьУдалить
  15. Если джокер на поле - то считаем мастью - отсутствующуя, а базовой картой слева от него (циклично)

    от неё и считаем достоинство стандартным способом (джокер может лежать где угодно)

    Если есть 2 карты одной масти, откладываем Джокера.

    Если джокера на поле нету, считаем как обычно, но если попадаем на карту которая уже на поле - значит отложен джокер.

    ОтветитьУдалить
  16. Анонимный12.08.2011, 18:12

    В условиях задачи не хватает одного ограничения. Варьируя темп и ритм нажатий, можно передать столько информации, что еще на несколько колод хватит. Особенно, если у помощника хорошо развито чувство ритма :)

    ОтветитьУдалить
  17. Александр, выздоравливайте!

    Уважаемый аноним, хорошо, я добавил условие о том, что помощник не знает пятую карту, поэтому вводит данные в компьютер, не стараясь как-либо подсказать :)

    ОтветитьУдалить
  18. Без компьютера вполне можно обойтись.

    Загадка здесь: http://fregimus.livejournal.com/145468.html

    А отгадка здесь. Только не подглядывайте раньше срока! http://fregimus.livejournal.com/145468.html

    ОтветитьУдалить
  19. Лектор может отправить закодированное сообщение, передав данные о картах помощнику в нужном порядке. Так как карт пять, значить всегда будет две карты одной масти. Поэтому достаточно одну из этих карт положить на стол, а вторую всегда называть первой. И всё, компютеру масть известна. Осталось угадать карту из 13 возможных вариантов.

    ОтветитьУдалить
  20. Если бы не было бы ограничения на порядок ввода занчений масть/достоинство было бы намного проще.

    ОтветитьУдалить
  21. fregimus Посмотрел отгадку, всё хорошо, но не понял один момент: что делать если на руках оказались карты одинакового достоинства, но разной масти?
    Тогда надо масти по старшинству ранжировать.

    ОтветитьУдалить
  22. Информацию спрятать очень легко. Особенно если вы играли в карточную игру "это 1, это 2, это 10, но это 0". Потопывание, цоканье языком, почесывание. Я боюсь, что использование порядка карт и порядка названия достоинства/масти окажется слишком сложным на общем фоне.

    ОтветитьУдалить
  23. fregimus, спасибо за ссылки на разборы! Теперь все желающие смогут ознакомиться с подробным обсуждением задачи.

    Искатель и ZW, мы исходим из того, что человек, вводящий данные в компьютер, не знает пятую карту (пусть это каждый раз будет случайный человек из аудитории). Другими словами, лектор ему сообщает только состав и порядок четырёх карт, а воспринять другую информацию он не готов. Поэтому ни цоканье языком, ни перемена порядка масти и достоинства карт не имеет смысла. Это честная математическая задачка, а не шулерство.

    > не понял один момент: что делать если на руках оказались карты одинакового достоинства, но разной масти? Тогда надо масти по старшинству ранжировать.
    Да, конечно, на всех 52 картах задан порядок. Можно вообще считать, что у нас не игральные карты, а таблички с числами от 1 до 52. Тогда вообще всё легко.

    ОтветитьУдалить
  24. Проще кодировать очередностью достоинства и масти карты. Если сначала сообщили масть - 0, если сначала сообщили достоинство - 1.
    :)

    ОтветитьУдалить
  25. Прочитал решение, оказывается всё так просто. :-) (статью с доказательством обобщённой задачи не читал :-)).
    Я первый раз прочитал эту заметку ночью и не понял, рассуждение с 4!=24 перестановками, потом читал комментарии здесь и тоже мало, что понимал. В общем, на будущее, первый шаг в решении задачи, особенно, если это подсказка в тексте самой заметки, нужно объяснить подробнее, чтобы в 2 часа ночи тоже можно было понять. :-)

    Можно поступить и иначе, не читать такие заметки в 2 часа ночи. :-)

    ОтветитьУдалить
  26. Перечитал ещё раз условие задачи, изложенное тут http://falcao.livejournal.com/180432.html Я просто не до конца понял условие задачи, в смысле, что порядком карт можно передавать информацию.

    ОтветитьУдалить
  27. ZW, ещё проще было бы сразу назвать пятую карту, а не выдумывать глупости с четырьмя другими :)

    alexsmail, спасибо за замечание!

    ОтветитьУдалить
  28. В сложном варианте при 53 картах. Возможны варианты с жокером и без жокера. Открытым сообщением назовем 4 карты передаваемых комьютеру.
    Без жокера алгоритм описан в сообщении Александра от 12.08.11 5:50.
    С жокером расклады из 5 карт разделяются на две группы 1 группа с двойным и более совпадением масти
    2 группа без совпадения масти

    Для 1 группы отложеная карта - жокер. Такой вариант может кодироваться двойным, тройным, четверным совпадением масти в открытом сообщении. Причем расклад сообщения должен содержать ошибку с точки зрения правил кодирования. Еще раз напомню, что стоит прочитать предложение Александра от 12.08.11 5:50.
    То есть, наличие ошибки в сообщении - признак жокера в отложенной карте.

    Для 2 группы используется дополнительная система кодирования. Признаком перехода к которой является наличие жокера в открытом сообщении. Масть отложеной карты соответствует отсутствующей масти в открытом сообщении. Осталось построить дополнительную систему кодирования с учетом того, что можно закодировать 4!=24 значения.

    ОтветитьУдалить
  29. Анонимный15.08.2011, 12:32

    По моему в соображениях chukchatel комментирует...
    есть ошибка.

    Если есть джокер в пяти картах, то надо поступить так.

    Если есть 2 карты одной масти, то масть пятой карты передается мастью карты, идущей после джокера. В остальном алгоритм как и прежде.

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

    Меня только волнут как теперь расширить колоду до 124 карт.

    ОтветитьУдалить
  30. Анонимный15.08.2011, 12:45

    PS
    Если все четыре карты одного достоинства и еще есть джокер, то такой вариант не знаю как закодировать.

    ОтветитьУдалить
  31. Продолжение разговора (предлагаю перенести обсуждение других аспектов задачки в новое место)

    ОтветитьУдалить
  32. Анонимный10.01.2012, 12:08

    nik_vic ЖЖ
    ИЛЬЯ ВЕСЕННИЙ: """"...добавим в нашу колоду джокера, тем самым расширив её до 53 карт.

    Колоду можно расширять до 124 карт,далее нельзя. Последнее доказывается легко: если N>124, то C(N,5)>A(N,4).

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний