Тримин является Полимином порядка 3, то есть многоугольник в плоскости состоит из трех одинаковых по размеру квадратов , соединенных от края до края. [1]
Симметрия и перечисление
Когда вращения и отражения не считаются отдельными формами, есть только два разных свободных тримино: «I» и «L» (форма «L» также называется «V»).
Поскольку оба свободных тромино обладают симметрией отражения , они также являются единственными двумя односторонними тромино (тромино, отражения которого считаются различными). Когда вращения также считаются отдельными, существует шесть фиксированных тримино: два I и четыре L-образных формы. Их можно получить, повернув указанные выше формы на 90 °, 180 ° и 270 °. [2] [3]
Rep-tiling и теорема тромино Голомба
Оба типа тромино можно разделить на n 2 меньших тромино одного и того же типа для любого целого n > 1. То есть они являются повторяющимися плитками . [4] Продолжение этого разреза рекурсивно приводит к замощению плоскости, которое во многих случаях является апериодическим замощением . В этом контексте L-тримино называется стулом , а его мозаика путем рекурсивного деления на четыре меньших L-тримино называется мозаикой кресла . [5]
Мотивированный проблемой изуродованной шахматной доски , Соломон В. Голомб использовал эту мозаику в качестве основы для того, что стало известно как теорема Голомба о тромино: если с шахматной доски 2 n × 2 n удалить любую клетку , оставшаяся доска может быть полностью покрыта L -тромино. Чтобы доказать это с помощью математической индукции , разделите доску на четвертную доску размером 2 n − 1 × 2 n − 1 , содержащую удаленный квадрат, и большое тромино, образованное другими тремя четвертными досками. Тромино можно рекурсивно разрезать на единичные тромино, и по гипотезе индукции следует разрезание квотборда с удалением одного квадрата. Напротив, когда на шахматной доске такого размера удален один квадрат, не всегда возможно покрыть оставшиеся клетки I-тромино. [6]
Смотрите также
Предыдущие и следующие заказы
Рекомендации
- ^ Голомб, Соломон В. (1994). Полимино (2-е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 0-691-02444-8.
- ^ Вайсштейн, Эрик В. «Триомино» . MathWorld .
- ^ Редельмайер, Д. Хью (1981). «Подсчет полимино: еще одна атака». Дискретная математика . 36 : 191–203. DOI : 10.1016 / 0012-365X (81) 90237-5 .
- ^ Nițică, Виорел (2003), «Повторный визит к репликам», MASS selecta , Провиденс, Род-Айленд: Американское математическое общество, стр. 205–217, MR 2027179.
- ^ Робинсон, Э. Артур младший (1999). «На столе и на стуле» . Indagationes Mathematicae . 10 (4): 581–599. DOI : 10.1016 / S0019-3577 (00) 87911-2 . Руководство по ремонту 1820555 ..
- ^ Голомб, SW (1954). «Шашечные доски и полимино». Американский математический ежемесячник . 61 : 675–682. DOI : 10.2307 / 2307321 . Руководство по ремонту 0067055 ..
Внешние ссылки
- Индуктивное доказательство Голомбы теоремы в триминой на вырез в-узле
- Головоломка Тромино на пороге
- Интерактивная головоломка Тромино в колледже Амхерст