Головоломка Триміно

Оригінал доступний на nstarr.people.amherst.edu

Про головоломку – фізичну та віртуальну

v-21 puzzle

Базова головоломка складається з: 21 прямокутної фігури («плитки») вказаного виду, що складається з трьох квадратів, однієї додаткової одинарної квадратної плитки та площини з сіткою 8×8 квадратів, в яких такий же розмір, що і в квадратних плиток. У загальній складності плитки займають 3×21+1=63+1=64 квадрата – стільки ж, скільки на шахівниці. Надалі ми будемо називати ці кутові фрагменти Триміно, як найпростіший з декількох назв, використовуваних для них, серед яких є «L-триміно», «L-триміно» і «V-триміно».

Щоб зіграти в фізичну версію цієї головоломки – використовуючи 21 справжню плитку Триміно, одну квадратну деталь і основу, схожу на шахову дошку розміром 8×8 – для початку помістіть єдину квадратну плитку в будь-яку з 64 квадратних осередків на поле. Потім заповніть решту 63 осередків використовуючи Триміно так, щоб не вийшло перекриття або незаповненого осередку. Таке рішення головоломки називається мозаїчним облицюванням квадрата 8×8. Як варіант, почніть з послідовного розміщення триміно на полі шахівниці (кожна така плитка займає лише три квадрата сітки), а коли всі 21 розташовані, помістіть одиничну квадратну плитку в ту клітинку, яка залишилася доступною.

Ось передісторія комерційної версії цієї головоломки, проданої Kadon Enterprises. На щорічних зборах Математичної асоціації Америки в січні 2000 року Артур Бенджамін отримав премію Haimo за видатне викладання в коледжі. У своїй вдячній промові він накидав своє улюблене доказ по методу індукції. Дана аргументація гарантує, що квадрат 2n×2n клітин (тобто універсальна розграфлена дошка з квадратами в кількості 2n по кожній стороні) один зайнятий осередок завжди може бути викладений плитками триміно. Через три роки після того, як я почув коментарі Бенджаміна, я давав лекцію по індукції і згадав його улюблений доказ. На додаток до моїх підготовленим прикладів я навів цей класичний аргумент через Соломона Голомба. Порахувавши, що реально існуюча головоломка такого роду додасть справжності і зможе викликати інтерес до методу індукції, я відправив листа Kadon, провідному виробнику головоломок, щоб дізнатися, чи є у них що-небудь, що я можу купити. У них такого не було, тому я запитав, чи зроблять вони кілька згідно заданим мною характеристикам. Ряд електронних листів в листуванні з Кейт Джонс, президентом Kadon, привела до головоломки, подібної до тієї, що зображена зліва вгорі. Вона запропонувала використовувати кілька різних кольорів для плиток триміно, що зробило цю головоломку більш цікавою, ніж я припускав. Я зробив вибір на користь більш напівпрозорих плиток холодних відтінків, а не квітчастих непрозорих, і вважав за краще для триміно синій, колір морської хвилі і аметистовий. 

Кейт запитала, дозволю я Kadon додати головоломку до безлічі предметів, які вони продають, і я охоче погодився – мені потрібні були тільки кілька штук для мого особистого користування. На мій подив, вона заявила, що я буду отримувати авторські відрахування. Це ніколи не було моєю метою, і всі мої авторські відрахування пожертвувано Коледжу Амхерста і Математичній асоціації Америки

Kadon випустив головоломку під назвою «Vee-21»; див. за посиланням www.gamepuzzles.com/polycub2.htm#V21. Ця комерційна версія, в трьох яскравих, напівпрозорих акрилових кольорах, йде з брошурою на сорок сторінок, що пропонує безліч доповнень до основної загадки. Кейт внесла в головоломку деякі доповнення, кілька стратегічних ігор, розрахованих на двох чоловік і запропонувала вимоги до поділу елементів за кольором для мощення мозаїкою з першої спроби. Вона також відкрила естетичні варіанти в створенні симетричних візерунків. Кейт запросила Оріеля Максиме для вирішення деяких з його лабіринтоподібних завдань, пов’язаних з покриттям плитками триміно; також в брошуру включені різноманітні прямокутні шаблони зі стратегічно обраними лініями решіток, із затемненими осередками, для вказівки рамок, де можна розміщувати триміно.

Тут представлені дві інтерактивні комп’ютерні головоломки. Головоломка 8 на 8 була розроблена двома моїми студентами, в той час як колега по кафедрі розробив головоломку M-by-N. Головоломка M-by-N (відтворюється в більшості систем, але може повільно завантажуватися) трохи більш гнучка, що дозволяє вибирати будь-яку кількість рядків і стовпців від 2 до 32 включно. У головоломки 8 на 8 (найкраще працює на ПК з Internet Explorer) є інша дія миші, а також вона ефективно обмежена трьома кольорами триміно. Напрямки дані з кожним. І онлайн-версії, і версії Kadon володіють надзвичайним ступенем привабливості і інтригують як чотирьохліток, так і маститих любителів головоломок.

Історія

Доказ того, що при будь-якому натуральному числі n квадрат 2n×2n з одного зайнятого осередку («некомплектним» квадратом) завжди може бути викладений плитками триміно, належить Соломону Голомбу. Він опублікував його в своїй статті 1954 року [9] в American Mathematical Monthly. Як зазначалося вище, головоломка була створена для наочної ілюстрації аргументу Голомба про некомплектний квадрат, яким була укомплектована головоломка 2n×2n. Та ж його стаття ввела в обіг термін триміно і його узагальнений варіант – поліоміно. Поліоміно – це зв’язкова структура з ідентичних квадратів, що володіє такою властивістю, що будь-які два квадрата або не торкаються один одного, або стикаються по всій довжині загального ребра. Єдино можливі дві форми триміно – це три квадрата поспіль і L-образна форма даної головоломки, і тут мається на увазі виключно друга форма «триміно». 

Доказ Голомба є першокласним прикладом математичної індукції. Крім очевидної простоти аргументації, це рідкісний випадок нечислового застосування методу. Він відрізняється від прикладів і вправ, що часто зустрічаються в інтерпретаціях індукції (наведених в підручниках), які зазвичай складаються з безлічі формул для кінцевих сум, нерівностей тощо. Перша поява доказу в масовому виданні – це Recreational Mathematics Magazine (RMM) Джозефа Мадачі, де Голомб включив його в першу з чотирьох статей про поліоміно, опублікованих в RMM [10]. У доленосній статті Мартіна Гарднера, опублікованій в травні 1957 року в журналі Scientific American, в якій поліоміно були представлені для широкої публіки, він зазначив, що «дошка з одним квадратом, пропущеним в будь-якій точці, може бути покрита 21 правильними триміно» [6, с. 154]. У своїй першій книзі, що складається з колонок, опублікованих в Mathematical Games, Гарднер пояснив, що «геніальна аргументація індукції демонструє, що 21 правильне триміно і одне мономіно покриють дошку 8 на 8 незалежно від того, де розміщено мономіно» [8, с. 126]. 

Аргументація викладання для некомплектних шахових дощок за допомогою триміно, а також загальна теорема 2n×2n після статей в Monthly і RMM з’явилися в ряді книг. Це було пояснено в класичних «Поліоміно» Голомба [11, 1965, с. 21-22] і в другому виданні даної книги [11, 1994, с. 5]. Друге видання містить багату історію і великий огляд цієї інтригуючої теми, і наповнене ілюстраціями і головоломками. Його 22 сторінки з посиланнями на книги і статті є додатковим бонусом. Іменний покажчик включає 81 людину, чимало з яких згадані в тексті книги більш ніж один раз. Багато з них будуть розкриті палкими шанувальниками ігр та математиками-любителями, а також професіоналами в будь-якій області. Опис книги дано в огляді [17] Джорджа Мартіна. У 1976 році Росс Хонсбергер дав зрозуміле і докладне застосування аргументації Голомба для шахової дошки в своїх «Математичних скарбах II» [13, с. 61]. Основна ідея доказу згадується також в книзі Джорджа Е. Мартіна, присвяченій мозаїкам поліоміно [16, с. 27-28]. Рецензія Девіда Сінгмастера [22] на цю останню книгу особливо цікава, тому що вона дає чудовий нарис предмета і його історії. 

Ця тема також стає все більш звичайною частиною в підручниках і задачниках. Наприклад, вона з’являється в підручниках з дискретної математики Сюзанни Епп [5, с. 234], Річарда Джонсонбо (який згадує тримінові прямокутники як такі, що з’являються в VLSI моделях) [14, с. 58-59] і Кеннет Розен [20, с. 247-8]. Створення мозаїк за допомогою Триміно розглядається також в книзі Деніела Веллемана про побудову доказів [26, с. 271-275] і задачниках Джона П. Д’Анджело і Дугласа Б. Веста [1, с. 75], а також Іржі Германа, Радана Кучери і Яромера Жімжі [12, с. 271]. Найбільш яскравою ілюстрацією аргументації Голомба є додатковий «доказ без слів» Роджера Нельсена, наведений у другій частині книги з такою ж назвою [19, с. 123]. 

Дана область розважальної математики отримала вигоду від безперервного потоку досліджень і запропонованих проблем. У 1985 і 1986 роках І-Пінг Чу і Річард Джонсонбо вивчали питання про викладанні мозаїкою некомплектних n×n полів (де n більше не повинно бути в другому ступені) і, в більш широкому сенсі, про некомплектні і комплектні прямокутні поля [3, 4 ]. Книга Джорджа Мартіна включала в себе цілий розділ, присвячений викладання мозаїки за допомогою триміно [16, с. 23-37]. Питання колористики щодо плиток триміно розглядаються Ілварсом Мізніксом, який визнає, що сторінка Kadon з вибором кольору для Vee-21 надихнула його на дослідження [18]. Стаття Дж. Маршалла Еша і Соломона Голомба про мощення триміно некомплектних прямокутників, опублікована в 2004 році, містить кілька нових і базових результатів, один з яких відповідає на давнє питання Чу і Джонсонбо. Еш і Голомб завершують статтю відкритим питанням щодо 2-некомплектних прямокутників (прямокутників, де вилучені дві клітини).

Інтернет – хороше джерело в плані демонстрації та інформації про створення мозаїк. Наприклад, пошук по «tromino» і «tiling» призводить до появи аплетів, таких як аплети Олександра Богомольного https://www.cut-the-knot.org/Curriculum/Games/TrominoPuzzle.shtml і Крістофера Мавата http://www.utc.edu/Faculty/Christopher-Mawata/trominos/, що демонструють пазли Троміно декількох розмірів. 

Варіації

Ось деякі розширення головоломки триміно, які читачі можуть розглянути. Перше було запропоновано моїм братом Раймондом (Пітом), який запитав, як можна розташувати триміно в сітці 8×8 таким чином, щоб максимізувати число вільних квадратів. Це може бути розглянуто більш докладно: один спосіб передбачає, що плитки і сітка розташовані таким чином, щоб залишатися на місці, а альтернативний спосіб може дозволити плиткам ковзати так, щоб дозволити втиснути якомога більше плиток (завжди в межах ліній сітки). Піт був не в курсі, що версія з фіксованим розташуванням є варіацією головоломки з розміщенням пентаміно, яка належить Голомбу і описана Гарднером [7, с. 128], [8, с. 133]. Голомб застосував цю головоломку для гри пентаміно, розраховану на двох осіб [7, с. 128] і [8, с. 133-135], правила якої можуть бути застосовані і до головоломки триміно. Девід Кларнер розповів про гру пентаміно для двох – Pan-Kāi (розробленої Алексом Рендольфом і опублікованої в 1961 році силами Phillips Publishers), – яка містила наступне обмеження: «Найважливіше правило полягає в тому, що заборонено розміщувати плитку всередині закритої області дошки, якщо незайнятими залишаються менше 5 осередків, за винятком того випадку, коли в результаті ходу ділянка повністю закривається [15, с. 8] (для більш додаткової інформації про Рендолфа і Pan-Kāi см. [21, стр. 75]). 

Ще один напрямок – тривимірний. Розглянемо куб з довжиною сторони 2n, що містить 23n елементарних осередків, одна з яких зайнята (одинична дірка). Чи можуть інші осередки бути заповнені тривимірними триміно (три куба в формі букви L, два з яких зустрічаються з третім на двох суміжних гранях останнього)? Необхідна умова 2n = 3k + 1 виявляється достатнім в тій же мірі [23, Глава 6: Тривимірна мозаїка Триміно Нортона Старра], [24, с. 72-87], [25]. У випадку з кубом 4×4×4 виникають деякі незначні труднощі, які можуть розважити юних любителів головоломок.

Простіші завдання цілком очевидні і були розглянуті багатьма іншими. Наприклад, чи можна викласти триміно квадратні масиви 3×3 та 6×6? Чи можна викласти триміно некомплектне поле в 5×5 або 7×7 квадратів? Ці останні дві головоломки є більш складними, ніж випадки з повними 3×3, 6×6 і некомплектним 8×8. Далі читачі можуть розглянути створення мозаїки з різних прямокутних масивів – див. посилання, зазначені нижче. При використанні версії з більш ніж одним кольором триміно, такий, як Vee-21 від Kadon, враховуйте різні колірні обмеження. Наприклад, спробуйте розташувати плитки так, щоб дві плитки одного кольору ніколи не мали загальну грань. І навпаки, спробуйте згрупувати як можна більше плиток одного кольору. При створенні патернів обох зазначених типів розміщення спробуйте зробити так, щоб мозаїка виглядала симетрично щодо діагоналі або ж відносно горизонтальної або вертикальної лінії. Існує безліч можливостей для веселощів і відкриттів. Прямокутники різних розмірів можна вивчити, клікнувши на головоломку M-by-N. Для експериментів з кольоровими схемами найкраще підійде головоломка Kadon.

Посилання:

1. Дж. П. Д’Анджело і Д. Б. Уест, Математичне мислення: Рішення задач і докази, друге видання, Prentice Hall, Аппер-сідло-Рівер, Нью-Джерсі, 2000.

2. Дж. М. Еш і С. В. Голомб, Черепиця дефектних прямокутників з триміно, Math. Mag., 77 (2004), ст. 46-55. (Доступно тут – math.depaul.edu/~mash/TileRec3b.pdf)

3. І. П. Чу і Р. Джонсонбо, Викладання некомплектних полів за допомогою триміно, Math. Mag, 59 (1986), ст. 34-40.

4. І. П. Чу і Р. Джонсонбо, Викладання полів за допомогою Триміно, J. Recreational Math., 18 (1985-86), ст. 188-193.

5. С. С. Епп, Дискретна математика з додатками, Третє видання, Томсон, Белмонт, Каліфорнія, 2004.

6. М. Гарднер, Про вражаючу схожість між Ікосіаном і Ханойською вежою, Scientific American, 196, (травень 1957), ст. 150-156. Ця колонка була спочатку присвячена схемам Гамільтона, але закінчується розділом про проблеми при викладанні мозаїкою шахівниці: Гарднер заявляє, що проблема шахівниці/доміно в лютневій колонці «спонукала Октава Левеншпіля з Бакнельского університету звернути мою увагу на чудову статтю С. В. Голомба в American Mathematical Monthly за грудень 1954 року».

7. М. Гарднер, «Більше про складні доміно плюс відповіді на головоломки минулого місяця», Scientific American, 197 (грудень 1957), ст. 126-140. Ця колонка «Математичних ігор» починається з повідомлення про вибуховий вплив короткого звіту травневої колонки про роботу Голомба [6]: «За рік, що минув після відкриття цієї кафедри, він отримав більше листів про одне з математичних відтворень, ніж будь-яке інше … завдання “пентаміно” … Сотні кореспондентів прислали найрізноманітніші рішення. Багато засвідчили про дивне захоплення цим завданням».

8. М. Гарднер, Американська наукова книга математичних головоломок і веселощів, Simon and Schuster, Нью-Йорк, 1959. (Передруковано і оновлено як Гексафлексагон та інші математичні розваги, University of Chicago Press, 1988) [Розділ 13 цього першого збірника подібного роду об’єднує матеріал по створенню мозаїки [6] і [7] і називається «Поліоміно»].

9. С. В. Голомб, «Шахові дошки і поліоміно», Amer. Math. Monthly, 61 (1954), ст. 675-682.

10. С. В. Голомб, «Загальна теорія поліоміно. Частина I – Доміно, пентаміно і шахівниця », Recreational Math. Mag., Випуск № 4 (серпень 1961 року) ст. 3-12.

11. С. В. Голомб, Поліміно, Scribner’s, Нью-Йорк, 1965. (Друге видання: Поліоміно, головоломки, схеми, питання і укладання, Princeton University Press, Прінстон, 1994).

12. І. Герман, Р. Кучера і Я. Жимжа. Підрахунки і конфігурації: проблеми комбінаторики, арифметики і геометрії (Карл Ділчер, перекладач), Springer-Verlag, Нью-Йорк, 2003.

13. Р. Хонсбергер, Математичні скарби II, Математична асоціація Америки, Вашингтон, округ Колумбія, 1976.

14. Р. Джонсонбо, Дискретна математика, шосте видання, Pearson Prentice Hall, Аппер-Седл-Рівер, Нью-Джерсі, 2005.

15. Д. Кларнер, Головоломка зі збиранням коробки. Численні замітки, Університет Ватерлоо, Онтаріо, 1973-74; 42 сторінки + титульний лист (частково вони підсумовані у Хонсбергера в 8 Розділі [13]).

16. Дж. Е. Мартін, Поліоміно, Керівництво по головоломкам і питанням по збірці, Математична асоціація Америки, Вашингтон, округ Колумбія, 1991.

17. Дж. Е. Мартін, огляд Поліоміно С. Голомба (видання 1994 року) Mathematical Reviews, MR1291821 (95k: 00006), 1995.

18. І. Мізнікс, Комп’ютерний аналіз триколірного завдання для V-подібних форм», Acta Societatis Mathematicae Latviensis, Тези 5-ї Латвійської математичної конференції, 6-7 квітня 2004 року, Даугавпілс, Латвія. (Доступно за посиланням http://www.de.dau.lv/matematika/lmb5/tezes/Mizniks.pdf)

19. Р. Б. Нельсен, Докази без слів II, Більше вправ в візуальному мисленні,  Математична асоціація Америки, Вашингтон, округ Колумбія, 2000.

20. К. Х. Розен, Дискретна математика та її застосування, видання п’яте, McGraw-Hill, Нью-Йорк, 2003. (З’явиться як приклад №13, в розділі 4.1, в шостому виданні, 2007 р.)

21. Дж. М. Сільва (ред.) Колоквіум I по цікавій математиці (Праці конференцій, 29 квітня – 2 травня 2009 року, Університет Евора), Associação Ludus, Лісабон, 2010.

22. Д. Сінгмастер, Огляд Поліоміно Г. Е. Мартіна, Mathematical Reviews, MR1140005 (93d: 00006), 1993.

23. А. Сойфер, Геометричні етюди в комбінаторній математиці, видання друге, Springer, Нью-Йорк, 2010.

24. Н. Старр, Збірка некомплектних кубів з довжиною сторони 2n за допомогою триміно, Geombinatorics XVIII (2) (2008), ст. 72-87.

25. Н. Старр, Збірка некомплектних кубів з довжиною сторони будь-якого розміру за допомогою триміно, http://arxiv.org/abs/0806.0524, 3 червня 2008 року.

26. Д. Дж. Веллеман, Як це довести: структурований підхід, видання друге, Cambridge University Press, Нью-Йорк, 2006.