00:45 

Тетрамино

wpoms.
Step by step ...

Тетрамино - это фигура, составленная из четырех квадратов, касающихся общими сторонами.
(i) Если не различать тетрамино, которые можно получить друг из друга вращением на плоскости, то докажите, что есть ровно семь различных тетрамино.
(ii) Докажите или опровергните утверждение: Можно сложить эти семь тетрамино в прямоугольник размером `4 xx 7` без наложений.


@темы: Комбинаторика

Комментарии
2013-05-30 в 04:21 

Adjirranirr
Только дурак нуждается в порядке — гений господствует над хаосом.
(i) Рассмотрим вот такую фигуру:

Из левой нижней клетки стандартным поиском в глубину получим 10 фигур по 4 клетки.
Из них совпадают (до поворота) ровно `4` пары, таким образом, различных среди них `6`; кроме того, этими шестью фигурами исчерпываются все варианты тетрамино, в которых одной клетки касается не более двух других. Единственный (с точностью до поворота) вариант, в котором одной клетки касаются 3 другие, это «T-образное» тетрамино. Таким образом, различных фигур ровно `7`.

(ii) Раскрасим прямоугольник в шахматную раскраску и предположим, что `7` фигурок в него уложено. Тогда все фигурки, кроме «T-образной», содержат по `2` черных и белых клетки, а «T-образная» содержит либо 3 черных, либо 3 белых. Следовательно, количества черных и белых клеток не совпадают, что невозможно.

   

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная