Степени двойки

Рассмотрим доску второго порядка. Ее можно покрыть, какую бы клетку мы ни удалили (см. рис. 2, слева). На рис. 2, справа, показано, как можно покрыть доску 4‑го порядка. Вырезанная клетка неизбежно оказывается в квадрате 2×2, в каком‑то из его четырех углов. Остальная часть доски покрывается благодаря приему, который Соломон Голомб окрестил rep‑tile («рептилия»): элемент покрытия (tile) как бы воспроизводит увеличенную копию (replica) самого себя. Левый верхний квадрат 2×2 можно поворачивать, чтобы недостающая клетка оказывалась в четырех разных местах, и весь квадрат 4‑го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.

 

 

 

_{Рис. 2. Порядки 2 и 4}

А 1953 году Голомб, «отец» полимино (он придумал для них название и первым начал изучать их), вывел индуктивное доказательство, продемонстрировав, что все доски со сторонами, отвечающими прогрессии 2, 4, 8, 16…) можно покрыть с помощью тримино, когда отсутствует произвольная клетка доски. Впервые доказательство было опубликовано в 1938 году[73]. Позже его повторил Э.Б. Эскотт (см. статью в журнале «Open Court»[74]). С тех пор математики включают это доказательство в свои книги, часто без ссылки на Голомба. Роджер Нельсен приводит Голомбово доказательство в виде единственной диаграммы, без всяких словесных пояснений[75]. Знаменитое доказательство Голомба начинается с рассмотрения квадрата 2×2 (рис. 3, слева). Этот квадрат затем помещается в угол квадрата 4–го порядка (рис. 3, в центре). А уже этот квадрат 4×4 располагается в углу квадрата 8‑го порядка (рис. 3, справа), после чего рядом с углом зачерненного квадрата 4‑го порядка укладывают одно тримино. Мы уже знаем, что зачерненный квадрат можно покрыть при отсутствии в нем любой клетки, и мы знаем, что три незачерненных области (примыкающих к нашему одиночному тримино) можно покрыть с помощью тримино, так как в каждой из них отсутствует одна клетка (угловая). Поворачивая доску[76], можно добиться того, чтобы любая клетка в зачерненном квадрате приходилась на любое место доски 8‑го порядка.

 

 

 

_{Рис. 3. Голомбово индуктивное доказательство}