Тромино или тримино — это полимино размера 3, то есть многоугольник на плоскости, состоящий из трех квадратов одинакового размера , соединенных ребром к ребру. [1]
Если не считать вращения и отражения отдельными формами, то существуют только две различные свободные тримино: «I» и «L» (форма «L» также называется «V»).
Поскольку оба свободных тримино имеют симметрию отражения , они также являются единственными двумя односторонними тримино (тримино с отражениями, считающимися различными). Когда вращения также считаются различными, существует шесть фиксированных тримино: две формы I и четыре формы L. Их можно получить, вращая указанные выше формы на 90°, 180° и 270°. [2] [3]
.gif/1280px-Geometrical_dissection_of_an_L-triomino_(rep-4).gif)
Оба типа тримино можно разбить на n 2 меньших тримино того же типа для любого целого числа n > 1. То есть, они являются rep-плитками . [4] Продолжение этого разбиения рекурсивно приводит к мозаике плоскости, которая во многих случаях является апериодической мозаикой . В этом контексте L-тромино называется стулом , а его мозаика рекурсивным подразделением на четыре меньших L-тромино называется мозаикой стула . [5]
Мотивированный проблемой изуродованной шахматной доски , Соломон В. Голомб использовал эту мозаику в качестве основы для того, что стало известно как теорема Голомба о тримино: если удалить любой квадрат с шахматной доски 2 n × 2 n , оставшуюся доску можно полностью покрыть L-тромино. Чтобы доказать это методом математической индукции , разбейте доску на четверть доски размером 2 n−1 × 2 n−1 , содержащую удаленный квадрат, и большое тримино, образованное тремя другими четвертями. Тримино можно рекурсивно разбить на единичные тримино, и разбиение четверти доски с одним удаленным квадратом следует по индукционной гипотезе. Напротив, когда с шахматной доски такого размера удален один квадрат, не всегда возможно покрыть оставшиеся квадраты I-тромино. [6]