[это] ...обобщение второй [задачи, части] на n выбираемых карт, а именно, каков максимальный размер колоды, при котором помощник передает фокуснику n−1 карт, однозначно указывая на оставшуюся.
Это довольно сложная постановка проблемы, поэтому найдите ходя бы верхнюю границу числа карт в такой колоде. Ниже, будет приведена эта самая верхняя граница и будет дана ссылка для продолжения исследования заинтересованных читателей.
Ниже есть продолжение.
Это решение подробно рассматривает М. Клебер[1]. В общих чертах, как верно заметил dimmik в одном из комментариев, легко найти верхнюю границу числа карт в такой колоде. Всего возможных вариантов выбора n (неупорядоченных) карт из колоды в N
Фокуснику передается n−1 упорядоченных карт, и всего возможных вариантов таких наборов в колоде
Сравнивая знаменатели, видим, что количества переданной и полученной информации сравниваются при условии
и, таким образом,
Например, для n=5 карт получаем уже знакомый нам максимальный размер колоды N=124. Однако, это лишь верхняя граница: с 5 картами фокус с колодой из более чем 124 карт точно не удастся. Но то, что найдется алгоритм кодирования информации для 124 карт (или какого-то меньшего числа) — это из нашего рассуждения никак не следует.
М. Клебер в своей статье доказывает, что верхняя граница всегда достижима при любом заданном n, то есть, существует алгоритм, позволяющий осуществить фокус при нашем максимальном вычисленном объеме колоды. Доказательство я здесь повторять не буду, потому что оно приводится в статье; упомяну лишь, что в нем используется теорема Бирхофа — фон Неймана о выпуклой оболочке множества матриц перестановок и теорема Холла о свадьбах. Желающим докопаться до самых глубин рекомендую прочитать саму статью.
_________________________
1. Michael Kleber. The Best Card Trick. Mathematical Intelligencer 24 No. 1 (Winter 2002).
http://my-tribune.blogspot.com/2011/08/blog-post_12.html
http://falcao.livejournal.com/180432.html
http://fregimus.livejournal.com/145468.html
No comments:
Post a Comment