Thursday, February 11, 2010

Симпатичное приложение модулярной арифметики

Вариант задачки отсюда (может пригодиться для студентов).

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

Решение помещу в комменте, так что если хотите сами подумать, не раскрывайте комментов.

5 comments:

avzel said...
This comment has been removed by the author.
avzel said...

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

iizc said...

Элегантно.

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

100 мудрецов будут построены утром в колонну так, что каждый видит только впереди стоящих. У каждого на голове будет одета шляпа - белая или черная, и соответственно каждый видит шляпы впереди стоящих. Каждый мудрец должен угадать цвет своей шляпы с одной попытки. Вечером перед построением они могут договариться о стратегии. Мудрецы хотят максимизировать количество угадавших (неугадавшие будут расстреляны конечно - stakes are high)

Общий случай: N мудрецов и M цветов шляп.

iizc said...

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

avzel said...

iizc: та же идея, да. Бедный последний мудрец!:)