Добрый день.
Можно учить теории кодирования (или любому другому разделу математики) традиционно: читать скучные лекции, формулировать непонятные леммы, доказывать ненужные теоремы... А можно показать всего один карточный фокус, чтобы удивить и заинтересовать, а уже потом читать интересные лекции и доказывать нужные теоремы.
Кстати, вчера вышла статья «iPad за партой. Заменят ли планшеты учебники?», для подготовки второй половины которой у меня взяли интервью. Я скептически отношусь к полезности подобной электроники в школе, но отлично понимаю, что хорошая идея и на плохой технике сработает, а плохая идея и на суперкомпьютерах не принесёт плодов. Другими словами, если всё делать грамотно, то и на iPad, и на более бюджетных устройствах можно хорошо обучать. Ниже я предлагаю описание фокуса, для демонстрации которого хватит колоды карт и любого компьютера или даже смартфона (вообще говоря, пару десятилетий назад и человек справлялся, но сейчас это может выглядеть не так эффектно).
На столе стоит компьютер-фокусник (считаем, что без камеры, микрофона и сети). Обычная колода из 52 карт отправляется в аудиторию, откуда возвращаются 5 случайно выбранных карт. Лектор одну из этих карт кладёт на стол, а оставшиеся четыре называет помощнику, который, не зная карту со стола, последовательно нажимает на клавиатуре 8 кнопок (для каждой из четырёх карт сначала масть, а потом достоинство). После этого на экране компьютера появляется изображение пятой карты. Как ему это удаётся?
Надо исходить из того, что это не обман, а математическая задача (то есть, хитрость не в том, что ещё один помощник «как-то через blue-touth с сотового телефона сообщил компьютеру о пятой карте»). Да, всё очень честно! Этот фокус может ошарашить и удивить. Но если вдуматься, то окажется, что это всего лишь математическая задача, которую может решить любой студент.
Давайте сравним количество информации (мы и раньше решали задачи про количество информации), которую ввели в компьютер, с объёмом данных, который он должен вернуть.
Проще всего разобраться с выходными данными: раз всего карт 52, то компьютер, чтобы сообщить достоинство и масть карты со стола, должен вернуть число от 1 до 52 (т.е. всего 52 варианта).
А что со входными данными? Четыре карты можно сообщить 4! = 24 разными способами (меняя порядок карт). Не так уж и мало, хоть и меньше необходимых 52. Как же двигаться дальше? Надо поискать, где ещё можно спрятать хоть чуть-чуть информации.
Предлагаю в комментариях поделиться своими идеями, как подвинуть эти две оценки друг к другу, чтобы стало понятно, как обучить компьютер этому фокусу.
Хорошего дня!
(А если вы уже знаете эту задачу, то предлагаю её «небольшую модификацию»: добавим в нашу колоду джокера, тем самым расширив её до 53 карт. Всё остальное прежнее: выбираются 5 случайных карт, одна кладётся на стол, а оставшиеся четыре сообщаются компьютеру)
Про каждую карту можно сначала сообщать масть, потом достоинство, а можно наоборот. Но тогда 24*16 сильно больше нужных 52, так что это вряд ли ожидаемый ответ.
ОтветитьУдалитьесли рассматривается вариант, когда помощник в курсе что за карта осталась и "помогает" компьютеру, то 8 нажатий можно рассматривать как 8 битное кодирование значения. 0 нажатие клавиши меньше какого-то времени, 1 - больше. и пожалуйста, хоть 2 колоды карт с определением из какой колоды осталась, все равно 256 значений.
ОтветитьУдалитьНа первый взгляд ни одной идеи! И вообще это кажется невозможным и невероятным. Я просто не знаю, с какого конца подойти к задаче. С нетерпением жду решения.
ОтветитьУдалитьОбратите внимание вот на какой момент - для передачи значения искомой карты необходимо передать 6 бит информации: 2 бита на определение масти и 4 бита на определение значения карты.
ОтветитьУдалить4 бита на значение карты передаются легко - назвая, к примеру, масть перед значением карты получаем 0, значение перед мастью - 1. итого 4 карты - 4 бита - 16 значений, чего с лихвой хватает на определение значения карты, даже джокера не проблема передать.
А вот откуда взять ещё два бита... Думаю, можно как-то их передать, поределяя порядок передачи карт. Скажем, повышение номинала карты - 1, уменьшение номинала - 0. Только вот как быть со случаем, когда номиналы трёх или четырёх карт совпадают...
Мне не хватает строгости, но общая идея такая:
ОтветитьУдалитьЕсли позволено выбрать, какую именно карту оставить, то мы можем выбирать оставляемую карту так, чтоб она была однозначно из "верхней" или "нижней" половины колоды.
(52-4)/2 - как раз 24.
Считаем, что все карты однозначно нумерованы, в результате из этих четырёх сказанных распределение будет одним из четырёх (0/1/2 вверху, 4/3/2 внизу == загаданная внизу, 3/4 вверху, 1/0 внизу - загаданная вверху).
Если порядок указания масти карты и её значения не фиксирован, то появляется еще одна "степень свободы", соответственно число комбинаций 24*2=48 (как раз количество карт за исключением названных 4-х)
ОтветитьУдалитьС одной стороны, компьютер после получения информации о 4 картах должен выбрать уже только одну из 48, а не 52. Со стороны лектора, задача стоит иначе - не в каком порядке передать 4 карты (тогда действительно только 24 варианта), а как из 5 карт выбрать 1 и какой порядок сформировать из оставшихся 4 карт. К примеру, какая-то масть обязательно в 5 картах встретится два раза. Пусть карта этой масти всегда идет первой, а другая остается неизвестной - уже доп. инф. Тогда значение карты задается порядком оставшихся трех карт (3! = 6), а значений всего 12 (без той, что дали компьютеру) - не сходится :). Хорошо, пусть, дополнительно, первая карта тоже несет информацию . Например, располагаем все карты одной масти по кругу. Смещением между двумя картами назовем расстояние между ними, если обходить их по часовой стрелке. Таких смещений будет для двух карт два - одно больше или равно 6, другое меньше или равно 6. Вот и будем передавать первой ту карту, смещение от которой до неизвестной меньше или равно 6.
ОтветитьУдалитьlenesh, верное замечание. Спасибо, я поправил условие, указав, что сначала в компьютер вводят масть каждой карты, а потом её достоинство (иначе получается слишком просто).
ОтветитьУдалитьjerom, идея хорошая, её надо развивать. Проблема у него, например, в том, что все пять карт, выбранных зрителями, могут оказаться из "не той" половины колоды.
Но Вы верно подметили, что компьютер должен назвать не одну из 52 возможностей, а одну из 48.
Александр, Вы почти всё рассказали :)
На хабре месяц назад была статья с исследованием на тему «Какие книги лучше — электронные или бумажные?» http://habrahabr.ru/blogs/ebooks/123647/
ОтветитьУдалитьПо опыту — читать художественную литературу на электронной книге приятнее некуда, а вот учебники и научпоп лучше иметь в бумаге.
Вначале хотел предложить достать лишний бит путем множественного именования карт ("восемь ←→ восьмерка"), потом понял, что не могу придумать альтернатив для картинок.
ОтветитьУдалитьsash-2003, да нет, тут всё без обмана.
ОтветитьУдалитьКарты называют одними и теми же именами (собственно, для этого я и написал, как их сообщают компьютеру). Никто не хитрит! Всё дело только в порядке тех четырёх карт, которые вводят в компьютер.
Да, Александр уже всё практически рассказал.
ОтветитьУдалитьИдею с совпадением первой карты с нужной по масти достаточно быстро нашел сам, идею со смещением даже с подсказкой не сразу понял.
Осталось сформулировать то, как оставшимися тремя совершенно случайными картами закодировать число от 1 до 6-ти. Но это уже достаточно тривиальная задача - оставшиеся три карты распределяем по старшинству и "весу" масти (можно преферансную схему) и назначаем номер от 1 до 3. И уже в зависимости от того, в какой последовательности эти номера были введены - определяем значение смещения.
Решение для 52 карт уже прозвучало. Но я вот довольно напряженно думал как его размножить до 53 карт. Тут гораздо интереснее. Пока что не получается. Пробовал принципиально другие подходы, но пока что ответ не нашел.
ОтветитьУдалитьРаз уж я все равно болею, и потому не могу работать, а задачка в голове крутится, то вот подход для 53 карт:
ОтветитьУдалитьесли джокера нет среди отобранных 5 карт, то
алгоритм как для 52 карт
если джокер среди отобранных 5 карт, то
если среди 5 есть две карты одной масти, то
алгоритм как для 52 карт, и джокер среди указующих 3 карт, причем считается за самую большую карту
если отобраны все карты разной масти и джокер, то джокер выдается первым, и указывает на отсутствующую масть. Но вот непонятно, как узнать значение скрытой карты... (
Если джокер на поле - то считаем мастью - отсутствующуя, а базовой картой слева от него (циклично)
ОтветитьУдалитьот неё и считаем достоинство стандартным способом (джокер может лежать где угодно)
Если есть 2 карты одной масти, откладываем Джокера.
Если джокера на поле нету, считаем как обычно, но если попадаем на карту которая уже на поле - значит отложен джокер.
В условиях задачи не хватает одного ограничения. Варьируя темп и ритм нажатий, можно передать столько информации, что еще на несколько колод хватит. Особенно, если у помощника хорошо развито чувство ритма :)
ОтветитьУдалитьАлександр, выздоравливайте!
ОтветитьУдалитьУважаемый аноним, хорошо, я добавил условие о том, что помощник не знает пятую карту, поэтому вводит данные в компьютер, не стараясь как-либо подсказать :)
Без компьютера вполне можно обойтись.
ОтветитьУдалитьЗагадка здесь: http://fregimus.livejournal.com/145468.html
А отгадка здесь. Только не подглядывайте раньше срока! http://fregimus.livejournal.com/145468.html
Лектор может отправить закодированное сообщение, передав данные о картах помощнику в нужном порядке. Так как карт пять, значить всегда будет две карты одной масти. Поэтому достаточно одну из этих карт положить на стол, а вторую всегда называть первой. И всё, компютеру масть известна. Осталось угадать карту из 13 возможных вариантов.
ОтветитьУдалитьЕсли бы не было бы ограничения на порядок ввода занчений масть/достоинство было бы намного проще.
ОтветитьУдалитьfregimus Посмотрел отгадку, всё хорошо, но не понял один момент: что делать если на руках оказались карты одинакового достоинства, но разной масти?
ОтветитьУдалитьТогда надо масти по старшинству ранжировать.
Информацию спрятать очень легко. Особенно если вы играли в карточную игру "это 1, это 2, это 10, но это 0". Потопывание, цоканье языком, почесывание. Я боюсь, что использование порядка карт и порядка названия достоинства/масти окажется слишком сложным на общем фоне.
ОтветитьУдалитьfregimus, спасибо за ссылки на разборы! Теперь все желающие смогут ознакомиться с подробным обсуждением задачи.
ОтветитьУдалитьИскатель и ZW, мы исходим из того, что человек, вводящий данные в компьютер, не знает пятую карту (пусть это каждый раз будет случайный человек из аудитории). Другими словами, лектор ему сообщает только состав и порядок четырёх карт, а воспринять другую информацию он не готов. Поэтому ни цоканье языком, ни перемена порядка масти и достоинства карт не имеет смысла. Это честная математическая задачка, а не шулерство.
> не понял один момент: что делать если на руках оказались карты одинакового достоинства, но разной масти? Тогда надо масти по старшинству ранжировать.
Да, конечно, на всех 52 картах задан порядок. Можно вообще считать, что у нас не игральные карты, а таблички с числами от 1 до 52. Тогда вообще всё легко.
Проще кодировать очередностью достоинства и масти карты. Если сначала сообщили масть - 0, если сначала сообщили достоинство - 1.
ОтветитьУдалить:)
Прочитал решение, оказывается всё так просто. :-) (статью с доказательством обобщённой задачи не читал :-)).
ОтветитьУдалитьЯ первый раз прочитал эту заметку ночью и не понял, рассуждение с 4!=24 перестановками, потом читал комментарии здесь и тоже мало, что понимал. В общем, на будущее, первый шаг в решении задачи, особенно, если это подсказка в тексте самой заметки, нужно объяснить подробнее, чтобы в 2 часа ночи тоже можно было понять. :-)
Можно поступить и иначе, не читать такие заметки в 2 часа ночи. :-)
Перечитал ещё раз условие задачи, изложенное тут http://falcao.livejournal.com/180432.html Я просто не до конца понял условие задачи, в смысле, что порядком карт можно передавать информацию.
ОтветитьУдалитьZW, ещё проще было бы сразу назвать пятую карту, а не выдумывать глупости с четырьмя другими :)
ОтветитьУдалитьalexsmail, спасибо за замечание!
В сложном варианте при 53 картах. Возможны варианты с жокером и без жокера. Открытым сообщением назовем 4 карты передаваемых комьютеру.
ОтветитьУдалитьБез жокера алгоритм описан в сообщении Александра от 12.08.11 5:50.
С жокером расклады из 5 карт разделяются на две группы 1 группа с двойным и более совпадением масти
2 группа без совпадения масти
Для 1 группы отложеная карта - жокер. Такой вариант может кодироваться двойным, тройным, четверным совпадением масти в открытом сообщении. Причем расклад сообщения должен содержать ошибку с точки зрения правил кодирования. Еще раз напомню, что стоит прочитать предложение Александра от 12.08.11 5:50.
То есть, наличие ошибки в сообщении - признак жокера в отложенной карте.
Для 2 группы используется дополнительная система кодирования. Признаком перехода к которой является наличие жокера в открытом сообщении. Масть отложеной карты соответствует отсутствующей масти в открытом сообщении. Осталось построить дополнительную систему кодирования с учетом того, что можно закодировать 4!=24 значения.
По моему в соображениях chukchatel комментирует...
ОтветитьУдалитьесть ошибка.
Если есть джокер в пяти картах, то надо поступить так.
Если есть 2 карты одной масти, то масть пятой карты передается мастью карты, идущей после джокера. В остальном алгоритм как и прежде.
Если джокер шел последним, то масть пятой карты не совпадает ни с одной из "публичных" карт, а её достоинство надо выбрать таким, чтобы можно было дойти по часовой стрелке за 6 шагов начиная с первой переданной. Т.е считаем будто бы масть пятой карты совпадает с любой из четырех на выбор "публичных" и в остальном алгоритм такой же.
Меня только волнут как теперь расширить колоду до 124 карт.
PS
ОтветитьУдалитьЕсли все четыре карты одного достоинства и еще есть джокер, то такой вариант не знаю как закодировать.
Продолжение разговора (предлагаю перенести обсуждение других аспектов задачки в новое место)
ОтветитьУдалитьnik_vic ЖЖ
ОтветитьУдалитьИЛЬЯ ВЕСЕННИЙ: """"...добавим в нашу колоду джокера, тем самым расширив её до 53 карт.
Колоду можно расширять до 124 карт,далее нельзя. Последнее доказывается легко: если N>124, то C(N,5)>A(N,4).