Плитки і числа Хееша

Навчання 26 серпня 2022 Перегляди: 57

Перед вами декілька замощень площини однаковими плитками (рис. 1). У кожному з них всі плитки — копії одного і того ж багатокутника. Викласти замощення можна, наприклад, так: почати з однієї плитки і поступово обкладати її з усіх боків іншими, шар за шаром, без зазорів і накладань. Так ми доберемося до кожної ділянки площини.

Ріс. 1

Звичайно, тут не будь-яка плитка годиться — наприклад, копіями правильного п’ятикутника не викласти навіть перший шар (рис. 2).

Ріс. 2

А чи буває, що кілька шарів викладаються, а далі не виходить? Навіть якщо перекладати вже викладені шари всіма можливими способами, перебираючи всі варіанти?

Так ми приходимо до чудового визначення: числом Хееша плитки називається максимальне число шарів, яке можливо викласти навколо неї копіями цієї плитки (при цьому копії дозволяється перевертати).

У правильного трикутника, квадрата і правильного шестикутника число Хееша дорівнює нескінченності. А у всіх інших правильних багатокутників число Хееша дорівнює нулю — навіть перший шар викласти не можна. Виявляється, у навмання обраної плитки число Хееша теж зазвичай або 0, або нескінченність.

Але чи існують багатокутники з числом Хееша 1, 2, 3,…? До того як Генріх Хееш сформулював це завдання в 1968 році, була відома лише одна плитка з числом Хееша, відмінним від 0 і нескінченності (рис. 3). Плитка ця навіть не багатокутник і вперше з’явилася в книзі Вальтера Літцмана «Кумедні і дивні числа і форми» в 1922 році.

Рис. 3

Сам Хееш знайшов іншу плитку з числом Хееша, рівним 1: це 5-вугільник, складений з квадрата, правильного трикутника і половинки такого ж трикутника (рис. 4).

Рис. 4

Перший приклад плитки з числом Хееша, рівним 2, навела в 1991 році Енн Фонтен і навіть побудувала нескінченно багато таких плиток. Всі вони складені з однакових квадратиків, тобто це фігурки поліміно (рис. 5).

Рис. 5

Того ж року Роберт Амманн додав до правильного шестикутника два виступи, вирізав три таких же паза і отримав фігуру з числом Хееша, рівним 3 (рис. 6). Ідея Амманна проста і витончена — треба шукати плитку, у якої є виступи і такі ж пази, але їх різна кількість.

Рис. 6

Рис. 7

Покажемо, як працює ця ідея, на прикладі плитки, знайденої Кейсі Манном у 2001 році. Вона має вигляд чотириклітинного прямокутника з чотирма виступами і п’ятьма пазами (рис. 7). Пояснимо, чому число Хееша такої плитки не може бути занадто великим. Розгляньмо квадрат S, повністю покритий копіями нашої плитки. Оскільки кожен паз може бути закритий тільки таким же виступом, число пазів і виступів, що потрапили всередину квадрата S, одне і те ж. З іншого боку, число виступів всередині квадрата приблизно дорівнює його площі (в клітинах) — так як у кожної клітини в плитці рівно один ^, а число пазів приблизно дорівнює 5/4 його площі — так як в плитці на кожні 4 виступи припадає 5 пазів. Але при великому розмірі квадрата ці числа не можуть бути рівні.

Ріс. 8

Ось суворе міркування (його можна пропустити, якщо «і так все зрозуміло»). Нехай квадрат S розміру 2n ст.12n повністю покритий плитками. Для цього потрібно принаймні 2 n· 2 n 4 = n 2 плиток. Всього у них 5n2 пазів, вони всі повинні бути заповнені.

З іншого боку, ці пази знаходяться всередині квадрата S ­ розміру 2 (n + 4) ст.12 (n + 4) (рис. 8). Тому їх заповнюють виступи від не більше ніж 2 (n + 5)· 2 (n + 5) клітин (ми врахували, що тут можуть знадобитися виступи і від клітин, що примикають до квадрату S ­). Тим самим, виступів максимум 2 (n + 5)· 2 (n + 5⁾ = 4n2 + 40n + 100. А при n > 100 завідомо виконано нерівність n2 > 40n + 100, звідки 5n2 > 4n2 + 40n + 100, тобто пазів більше, ніж виступів. Протиріччя — всі пази не можуть бути заповнені.

Значить, число Хееша цієї плитки звичайно. Насправді, воно дорівнює 3 (рис. 9), але довести це виходить поки тільки комп’ютерним перебором.

Рис. 9

Найбільш прості для дослідження фігурки поліміно, а також поліамонди і полігекси. Вони теж складені з однакових «клітинок», що примикають один до одного сторонами, тільки в поліамондах клітина — це правильний трикутник, а в полігексах — правильний шестикутник. Будуючи замощення з поліміно, поліамондів або полігексів, ми ніби викладаємо їх на свій «картатий» папір (рис. 1). На такому папері легко організувати комп’ютерний перебір. Так Кейсі Манн знайшов поліамонд з числом Хееша, рівним 3 (рис. 10).

Рис. 10

Також Кейсі Манну вдалося отримати кілька нових серій поліміно і полігексів з виступами і пазами, у яких число Хееша звичайно, але не дорівнює нулю. А рекордсменом є полігекс Кейсі Манна, складений з п’яти шестикутників (з виступами і пазами) — його число Хееша дорівнює п’яти (рис. 11). На сьогоднішній день це плитка з найбільшим відомим людству кінцевим числом Хееша.

Ріс. 11

Художник Олексій Вайнер