Головоломка с шахматной доской: как геометрия спасает информацию

Головоломка с шахматной доской: как геометрия спасает информацию

Спикер: 3Blue1Brown | Длительность: 18:42

Транскрипт

Постановка задачи (0:00)

Есть шахматная доска 8x8 (64 клетки), на каждой клетке монета (орел/решка). Два заключенных должны решить головоломку. Перед первым заключенным (вы) на доске раскладывают монеты как угодно, и показывают, где спрятан ключ (в одной из 64 клеток). Вы можете перевернуть только ОДНУ монету. Затем вы выходите, входит второй заключенный. Он видит новую раскладку монет и должен определить, где ключ. Оба могут заранее продумать стратегию, но warden (который знает стратегию) постарается помешать.

Размышления о головоломке (1:30)

Задача увлекла автора на 3 часа поездки домой. Возникли два направления для исследования:

1. Невозможность решения в некоторых вариациях: Например, если доска 6x6, или убрать одну клетку. Это ведет к доказательству, которое в конце видео будет применено к раскраске углов 4-мерного куба.
2. Связь с коррекцией ошибок (error correction): Как информация передается и хранится в компьютерах. Ошибки (перевернутые биты) могут изменить данные. Коды коррекции ошибок добавляют немного информации, чтобы можно было обнаружить и исправить ошибки. Интуиция для решения головоломки схожа с кодами Хэмминга.

Автор не будет рассказывать решение здесь, а отправляет на канал Matt Parker (Stand Up Maths), где они с Мэттом разбирают решение. Здесь же будет фокус на общих стратегиях и доказательстве невозможности в некоторых случаях.

Визуализация для 2-х монет (3:58)

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

• Простая стратегия: Вторая монета сообщает, где ключ. Решка = левая клетка, Орел = правая. Если нужно изменить монету, вы ее меняете. Если не нужно, меняете другую.
• Математическая интерпретация: Заменяем орел/решка на 1/0. Состояния (00, 01, 10, 11) можно представить как вершины квадрата.
• Движение: Переворот одной монеты = движение по ребру квадрата (изменение одной координаты).
• Стратегия в геометрии: Ассоциируем нижние вершины (y=0) с ключом в клетке 0, верхние (y=1) — с ключом в клетке 1. Задача — чтобы после одного хода (переворота монеты) вы всегда попадали в нужную область.

Визуализация для 3-х монет (5:46)

Следующий шаг: 3 монеты, 3 возможных места для ключа. Всего 8 состояний монет.

• Трехмерная интерпретация: Состояния (000-111) — это вершины куба.
• Переворот монеты: Соответствует движению по ребру куба.
• Стратегия = раскраска: Нужно раскрасить 8 вершин куба в 3 цвета (красный=клетка 0, зеленый=клетка 1, синий=клетка 2). Второй заключенный, увидев состояние (цвет вершины), должен понять, где ключ.
• Пример стратегии: Сумма первых двух монет. Если 0+0=0 (красный), 0+1=1 (зеленый), 1+0=1 (зеленый), 1+1=2 (синий). Но такая стратегия не универсальна.
• Невозможность: Пример: стратегия 0*c0 + 1*c1 + 2*c2 mod 3. Если начать с 010 (сумма = 1, зеленый), перевернув c0 (010 -> 110, сумма=2, синий), перевернув c1 (010 -> 000, сумма=0, красный), перевернув c2 (010 -> 011, сумма=3=0 mod 3, красный). Невозможно получить нужный цвет (например, синий), если он не доступен из начальной точки. Adversarial warden может выбрать ключ так, чтобы подставить заключенного.
• Визуальное доказательство: Если у вершины два соседа одного цвета, значит, есть проблема.
• Комбинаторный вопрос: Можно ли раскрасить куб так, чтобы у каждой вершины было 3 соседа разных цветов?
• Связь с кодированием: Мышление в терминах битовых строк как вершин гиперкуба — стандартный подход в теории кодирования (коррекция ошибок).

Доказательство невозможности (12:19)

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

• Идея: Симметрия задачи подразумевает равное количество вершин каждого цвета. В 3D (8 вершин, 3 цвета) это дало бы 8/3 вершин каждого цвета, что невозможно.
• Метод подсчета: Пройдемся по каждой вершине и посчитаем, сколько у нее красных соседей. Суммируем эти подсчеты. Если бы у каждой вершины был ровно 1 красный сосед (для 3-цветной раскраски), общая сумма была бы равна количеству вершин (2^n).
• Альтернативный подсчет: С другой стороны, каждая красная вершина была посчитана своим соседом 3 раза (в 3D). Значит, общая сумма равна 3 * (количество красных вершин).
• Противоречие: 2^n = 3 * (количество красных вершин). Для n=3, 8 = 3 * (количество красных вершин). Количество красных вершин = 8/3. Невозможно.
• Обобщение на n измерений: У каждой вершины n соседей. Общая сумма = n * (количество красных вершин). Для возможности решения (равное количество вершин каждого цвета, т.е. 2^n / k, где k - число цветов) нужно, чтобы 2^n = n * (2^n / k), что упрощается до n=k.
• Условие решаемости: В нашем случае, число цветов (k) равно числу клеток (N). Для N-мерного куба, количество вершин 2^N. Если мы хотим раскрасить вершины в N цветов так, чтобы каждый цвет был представлен одинаково, то 2^N должно делиться на N. Но из доказательства мы видим, что чтобы избежать противоречия, N должно быть степенью двойки. Если N не степень двойки, то n * (количество красных вершин) не может быть равно 2^n.
• Вывод: Для головоломки с N клетками, N должно быть степенью двойки. Если N=64 (8x8 доска), то N=2^6. Здесь нет такого ограничения, и решение возможно. Но если убрать клетку, N станет 63 (не степень двойки), и головоломка станет нерешаемой.

Явная раскраска 4-мерного куба (16:22)

• Демонстрируется, как выглядит раскраска 4-мерного куба (16 вершин, 4 цвета), где каждая вершина имеет 4 соседа всех 4 цветов. Это пример решаемой ситуации (N=4, степень двойки).
• Автор снова отсылает на Stand Up Maths для полного объяснения решения.
• Упоминается связь с надежной передачей данных как более «сексуальная» мотивация, чем абстрактная математика.

Практические задания

Задание 1: Построить схему для 2-х монет

• Цель: Визуализировать задачу для 2 монет, понять, как изменение одного состояния влияет на другие.
• Инструкция: Нарисуйте квадрат. Назовите его вершины состояниями монет: 00 (оба решка), 01 (первая решка, вторая орел), 10 (первая орел, вторая решка), 11 (обе орел). Нарисуйте линии (ребра) между состояниями, которые отличаются переворотом одной монеты (например, 00 <-> 10, 00 <-> 01). Теперь представьте, что у вас 2 клетки для ключа (например, цвет 1 и цвет 2). Попробуйте раскрасить вершины так, чтобы у каждой вершины было два соседа разных цветов. Отметьте, насколько легко или сложно это сделать.

Задание 2: Проанализировать 3-х монетную задачу

• Цель: Понять, почему простое суммирование битов может не работать как стратегия.
• Инструкция: Нарисуйте куб. Обозначьте вершины состояниями 000, 001, ..., 111. Теперь представьте, что у вас 3 клетки для ключа (цвет 0, 1, 2). Попробуйте раскрасить вершины куба (8 вершин) в 3 цвета так, чтобы у каждой вершины было 3 соседа всех остальных цветов. Заметьте, какие вершины остаются «проблемными» — где невозможно подобрать правильный цвет для соседей, или где два соседа имеют одинаковый цвет. Запишите, какие комбинации состояний (например, 010) вызывают трудности.

Задание 3: Исследовать связь с четностью

• Цель: Найти интуитивное понимание связи между состоянием монет и местоположением ключа.
• Инструкция: Для 3-х монет, рассчитайте «сумму» битов для каждого из 8 состояний (000, 001, 010, 011, 100, 101, 110, 111). Например, для 011 сумма = 0+1+1=2. Попробуйте ассоциировать эту сумму (или ее остаток от деления на 3) с цветом (местом ключа). Проверьте, работает ли эта стратегия. Изменится ли сумма, если перевернуть одну монету? Как это связано с тем, что вы можете или не можете достичь нужного цвета?

Лучшие цитаты

«In this case, what they've done is carefully turned over each of the coins to be heads or tails according to whatever pattern they want it to be, and then they show you a key.» — 3Blue1Brown

«First things first, let's stop thinking about these as heads and tails and start thinking of them as ones and zeros. That's much easier to do math with.» — 3Blue1Brown

«Every time you flip a coin, you're walking along the edge of a cube.» — 3Blue1Brown

«The idea is that the symmetry in the property that we're looking at will end up implying that there have to be an equal number of red, green, and blue vertices.» — 3Blue1Brown

«So for example, if we were in 4 dimensions, or 64 dimensions, there is no contradiction. It's at the very least possible to evenly divide the vertices among the different colors.» — 3Blue1Brown

Ключевые выводы (Takeaways)

• Головоломка с монетами — это про передачу информации, а не про случайность.
• Геометрия кубов помогает понять структуру сложных задач с битами.
• Невозможность решения зависит от количества состояний (размера доски), если оно не степень двойки.
• Визуализация через раскраску куба — мощный инструмент для доказательства ограничений.