ПОЛНЫЙ И УНИВЕРСАЛЬНЫЙ РЕЗУЛЬТАТ

Занимаясь разбиением этих фигур, я подобрался (но пока недостаточно близко) к тому, чтобы вывести индуктивное доказательство того, что все дефицитные квадраты покрываемы, за исключением квадрата 5‑го порядка. Это доказательство в конце концов получили И. Пинг Чу и Ричард Джонсонбау[77]. Чу и Джонсонбау позаботились не только обо всех дефицитных квадратах, но и обо всех дефицитных прямоугольниках! Их индуктивное доказательство – слишком специальное, чтобы его здесь приводить. Коротко говоря, они продемонстрировали покрываемость для всех прямоугольников m×n (включая и квадраты – случай, когда m=n) с числом клеток, кратным 3 после удаления одного поля. Подобные доски покрываемы, если выполняются все четыре необходимых и достаточных условия:

1) m ≥ 2,

2) n ≥ m,

3) если m=2, n должно тоже равняться 2,

4) m ≠ 5.

Прямоугольник 4×7 – самый маленький дефицитный прямоугольник (не квадрат), который можно покрыть с помощью L‑тримино. Вот еще одно упражнение: много ли у вас уйдет времени на то, чтобы покрыть такую фигуру с помощью тримино и двух элементов 2×3, если недостающая клетка у этой фигуры располагается в углу?

Кристофер Йенсен показал в своей неопубликованной статье, что если в углу любой доски убрать две клетки, как показано на рис. 9. получившуюся доску нельзя будет покрыть с помощью тримино. Однако, если исключить приведенные пять случаев, доску с длинами сторон 3m–1 и 3n+1 и с любыми двумя недостающими клетками окажется возможным покрыть при следующем необходимом и достаточном условии: либо если n=1, либо если m ≥ 3 и n ≥ 3.

 

 

_{Рис. 9. Невозможность покрытия при отсутствии двух клеток в углу}