- 27,659
- 46
- 8 Ноя 2022
Семь тасований — это миф для обычных людей.
Математики вернулись к старой задаче о тасовании карт и получили новый ответ для более жизненной ситуации. Если игрок перед каждым рифл-шаффлом снимает случайную часть колоды, а две стопки получаются неровными, обычной колоде из 52 карт нужно примерно 14 перемешиваний. Классическая модель 1992 года давала семь, но описывала более аккуратную технику, близкую к работе фокусника, а не обычного человека за карточным столом.
Рифл-шаффл - это тасование, при котором колоду делят на две стопки, берут их в руки и большими пальцами отпускают карты так, чтобы края обеих частей вплелись друг в друга. В математической модели следующая карта падает не строго по очереди слева и справа, а случайно. Вероятность зависит от того, сколько карт ещё осталось в каждой стопке. Поэтому порядок может идти неровно: левая, правая, правая, левая, правая, левая, левая. Простое чередование создало бы предсказуемый узор, а хорошее тасование должно разрушать подобные схемы.
Результат 1992 года стал известен не только из-за удобного числа. Доказательство показало резкий переход в поведении колоды. Первые шаффлы уже разбивают исходную раскладку, но отдельные пары и участки всё ещё сохраняют следы прежнего расположения. Затем остаточная структура быстро исчезает, и порядок карт становится почти неотличимым от случайного. В математике такой переход называют эффектом отсечения.
Эффект отсечения изучают в марковских цепях. Марковская цепь описывает систему, которая случайно переходит из одного состояния в другое. Для колоды состояние означает конкретную раскладку карт, а каждый шаффл переводит её в новую раскладку. Математикам важно понять, после какого числа переходов система теряет память о начале. Похожие резкие смены поведения ищут и в более сложных моделях, например в спиновых стёклах. Так называют физические системы с множеством взаимодействующих магнитных элементов, где беспорядок сочетается с долгой памятью о прошлом состоянии.
Главное ограничение старой модели скрывалось в самом начале шаффла. Перед каждым перемешиванием колоду нужно было делить примерно на две равные стопки. За обычным столом люди часто снимают больше или меньше половины. Сдвиг на несколько карт кажется мелочью, но для доказательства меняет всю картину: часть карт получает больше шансов сохранить прежний относительный порядок.
Неровные стопки создают зоны, которые перемешиваются хуже остальных. Снаружи колода уже может казаться хаотичной, но внутри некоторых фрагментов остаётся след старого расположения. В математической работе такие зоны называют холодными пятнами. Название передаёт смысл: большая часть колоды уже перемешалась, а отдельный участок дольше удерживает внутренний порядок.
Проще всего увидеть проблему на пронумерованной колоде. Пусть карты имеют номера от 1 до 52. После нескольких шаффлов карты 16 и 17 почти наверняка разойдутся и перестанут лежать рядом. Но карта 16 всё ещё может оказываться перед картой 17 чаще, чем в полностью случайной раскладке. Если похожее смещение сохраняется у многих пар из одного исходного отрезка, например между картами с номерами от 15 до 25, внутри колоды осталось холодное пятно.
Идею с холодными пятнами пытались довести до строгого доказательства больше двух десятилетий. Логика была понятной: когда исчезают самые устойчивые зоны, вместе с ними пропадает последняя информация о начальной раскладке. Сложность заключалась в масштабе. Нужно было доказать общий результат для колоды любого размера и разных мест деления перед каждым шаффлом, а не разобрать отдельный пример.
Новое доказательство отслеживает путь каждой карты с помощью двоичных меток. После первого деления все карты из левой стопки получают 1, а карты из правой - 0. Затем колоду перемешивают, снова делят на две части и дописывают к метке ещё один знак. Карта оказалась в левой стопке - добавляется 1. Карта попала в правую - добавляется 0. После нескольких шаффлов у каждой карты появляется собственная последовательность из нулей и единиц.
По такой метке можно восстановить маршрут карты через серию перемешиваний. Например, код 0110 после четырёх шаффлов означает, что карта сначала была в правой стопке, затем дважды попадала в левую, а потом снова оказалась справа. Чем больше перемешиваний, тем подробнее метка показывает путь карты через все деления.
Совпадающие метки помогают найти пары, где порядок ещё держится. Если две соседние в начале карты получили один и тот же двоичный код, значит, во всех делениях прошли одинаковый маршрут. Их относительное положение сохранилось. Для доказательства такой случай важен: часть колоды ещё не дошла до полной случайности.
Проверять все пары карт напрямую слишком тяжело, особенно в большой колоде. Холодные пятна дают обходной путь. Прежний порядок дольше всего держится именно в этих зонах, поэтому достаточно следить за наиболее устойчивыми фрагментами, а не сравнивать всю колоду целиком.
На следующем шаге доказательство переводит задачу на язык графов. Каждую карту из холодного пятна изображают точкой. Две точки соединяют линией, если у соответствующих карт совпадает двоичная метка. Линия означает, что пара всё ещё сохранила связь с прежним порядком. Затем такую же схему строят для второй колоды из n карт и сравнивают две конструкции.
Пересечения двух графов показывают, как долго холодные пятна в разных колодах продолжают сопротивляться перемешиванию. Доказательство установило: после нужного числа шаффлов эти пересечения исчезают с экспоненциальной скоростью. Последние следы порядка не тают равномерно. После определённого порога вероятность найти устойчивую связь между картами быстро падает.
Полностью бытовой вариант задачи пока остаётся открытым. Новая работа, как и классическая модель, предполагает, что карты при рифл-шаффле падают по одной. В реальной игре несколько карт часто слипаются и проходят через перемешивание небольшими группами. Для такой комковатой версии строгого ответа пока нет. Следующая задача - понять, сколько шаффлов нужно колоде, которую тасует не фокусник с точной техникой, а обычный игрок за столом.
Математики вернулись к старой задаче о тасовании карт и получили новый ответ для более жизненной ситуации. Если игрок перед каждым рифл-шаффлом снимает случайную часть колоды, а две стопки получаются неровными, обычной колоде из 52 карт нужно примерно 14 перемешиваний. Классическая модель 1992 года давала семь, но описывала более аккуратную технику, близкую к работе фокусника, а не обычного человека за карточным столом.
Рифл-шаффл - это тасование, при котором колоду делят на две стопки, берут их в руки и большими пальцами отпускают карты так, чтобы края обеих частей вплелись друг в друга. В математической модели следующая карта падает не строго по очереди слева и справа, а случайно. Вероятность зависит от того, сколько карт ещё осталось в каждой стопке. Поэтому порядок может идти неровно: левая, правая, правая, левая, правая, левая, левая. Простое чередование создало бы предсказуемый узор, а хорошее тасование должно разрушать подобные схемы.
Результат 1992 года стал известен не только из-за удобного числа. Доказательство показало резкий переход в поведении колоды. Первые шаффлы уже разбивают исходную раскладку, но отдельные пары и участки всё ещё сохраняют следы прежнего расположения. Затем остаточная структура быстро исчезает, и порядок карт становится почти неотличимым от случайного. В математике такой переход называют эффектом отсечения.
Эффект отсечения изучают в марковских цепях. Марковская цепь описывает систему, которая случайно переходит из одного состояния в другое. Для колоды состояние означает конкретную раскладку карт, а каждый шаффл переводит её в новую раскладку. Математикам важно понять, после какого числа переходов система теряет память о начале. Похожие резкие смены поведения ищут и в более сложных моделях, например в спиновых стёклах. Так называют физические системы с множеством взаимодействующих магнитных элементов, где беспорядок сочетается с долгой памятью о прошлом состоянии.
Главное ограничение старой модели скрывалось в самом начале шаффла. Перед каждым перемешиванием колоду нужно было делить примерно на две равные стопки. За обычным столом люди часто снимают больше или меньше половины. Сдвиг на несколько карт кажется мелочью, но для доказательства меняет всю картину: часть карт получает больше шансов сохранить прежний относительный порядок.
Неровные стопки создают зоны, которые перемешиваются хуже остальных. Снаружи колода уже может казаться хаотичной, но внутри некоторых фрагментов остаётся след старого расположения. В математической работе такие зоны называют холодными пятнами. Название передаёт смысл: большая часть колоды уже перемешалась, а отдельный участок дольше удерживает внутренний порядок.
Проще всего увидеть проблему на пронумерованной колоде. Пусть карты имеют номера от 1 до 52. После нескольких шаффлов карты 16 и 17 почти наверняка разойдутся и перестанут лежать рядом. Но карта 16 всё ещё может оказываться перед картой 17 чаще, чем в полностью случайной раскладке. Если похожее смещение сохраняется у многих пар из одного исходного отрезка, например между картами с номерами от 15 до 25, внутри колоды осталось холодное пятно.
Идею с холодными пятнами пытались довести до строгого доказательства больше двух десятилетий. Логика была понятной: когда исчезают самые устойчивые зоны, вместе с ними пропадает последняя информация о начальной раскладке. Сложность заключалась в масштабе. Нужно было доказать общий результат для колоды любого размера и разных мест деления перед каждым шаффлом, а не разобрать отдельный пример.
Новое доказательство отслеживает путь каждой карты с помощью двоичных меток. После первого деления все карты из левой стопки получают 1, а карты из правой - 0. Затем колоду перемешивают, снова делят на две части и дописывают к метке ещё один знак. Карта оказалась в левой стопке - добавляется 1. Карта попала в правую - добавляется 0. После нескольких шаффлов у каждой карты появляется собственная последовательность из нулей и единиц.
По такой метке можно восстановить маршрут карты через серию перемешиваний. Например, код 0110 после четырёх шаффлов означает, что карта сначала была в правой стопке, затем дважды попадала в левую, а потом снова оказалась справа. Чем больше перемешиваний, тем подробнее метка показывает путь карты через все деления.
Совпадающие метки помогают найти пары, где порядок ещё держится. Если две соседние в начале карты получили один и тот же двоичный код, значит, во всех делениях прошли одинаковый маршрут. Их относительное положение сохранилось. Для доказательства такой случай важен: часть колоды ещё не дошла до полной случайности.
Проверять все пары карт напрямую слишком тяжело, особенно в большой колоде. Холодные пятна дают обходной путь. Прежний порядок дольше всего держится именно в этих зонах, поэтому достаточно следить за наиболее устойчивыми фрагментами, а не сравнивать всю колоду целиком.
На следующем шаге доказательство переводит задачу на язык графов. Каждую карту из холодного пятна изображают точкой. Две точки соединяют линией, если у соответствующих карт совпадает двоичная метка. Линия означает, что пара всё ещё сохранила связь с прежним порядком. Затем такую же схему строят для второй колоды из n карт и сравнивают две конструкции.
Пересечения двух графов показывают, как долго холодные пятна в разных колодах продолжают сопротивляться перемешиванию. Доказательство установило: после нужного числа шаффлов эти пересечения исчезают с экспоненциальной скоростью. Последние следы порядка не тают равномерно. После определённого порога вероятность найти устойчивую связь между картами быстро падает.
Полностью бытовой вариант задачи пока остаётся открытым. Новая работа, как и классическая модель, предполагает, что карты при рифл-шаффле падают по одной. В реальной игре несколько карт часто слипаются и проходят через перемешивание небольшими группами. Для такой комковатой версии строгого ответа пока нет. Следующая задача - понять, сколько шаффлов нужно колоде, которую тасует не фокусник с точной техникой, а обычный игрок за столом.
- Источник новости
- www.securitylab.ru
