Домино

[wpoms.]

Домино представляет собой прямоугольник `1 times 2` или `2 times 1`. Диего хочет полностью покрыть доску `6 times 6` с помощью 18 домино. Определить наименьшее целое положительное число `k`, для которого Диего может разместить `k` домино на доске (без перекрытия) так, что остальная часть доски может быть покрыта оставшимися домино единственным способом.

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

Comments

[Груша Вильямс]

Хотя нет, тут два способа покрытия. Тогда, думаю, k=6.

[Груша Вильямс]

Руководствовался такими соображениями:
Для того, чтобы оставшуюся часть доски замостить единственным образом надо избавиться от квадратов `2 times 2`. Избавиться от них надо используя минимальное число доминошек.

[Ak-sakal]

Груша Вильямс,
Для шести хотя бы так
Но ведь надо ещё доказать, что пяти "домино" недостаточно.

[Гость]

Ak-sakal, да, для шести знаю как, много вариантов. А вот минимальность шести доказать трудно.
Хотя вот придумал доказательство, но оно странное.
1) Избавляемся от квадратов 2x2, причем избавляться от них логично "от края", т.е. чтоб домино не стояли на краевых линиях.

Таким образом, мы расставили 5 штук, видим, что их недостаточно.
2) Док-во:
Всего у нас 36 клеток, домино занимают 10 клеток, 6*4-4 клеток по периметру, они на минимальность не влияют, поэтому вычтем их, итого у нас 36-(10+20)=6 клеток, больше, чем клеток квадрата 2x2, поэтому необходима ещё одно домино.
В общем виде для доски `l times l`, где l - чётное получается так:
если `l^2 - ( 2lceil (l^2/4)/2 rceil + 4(l-1) ) > 4`, то `k=l^2/4+2`.

[Груша Вильямс]

забыл страницу обновить,
точнее
Ak-sakal, да, для шести знаю как, много вариантов. А вот минимальность шести доказать трудно.
Хотя вот придумал доказательство, но оно странное.
1) Избавляемся от квадратов 2x2, причем избавляться от них логично "от края", т.е. чтоб домино не стояли на краевых линиях.

Таким образом, мы расставили 5 штук, видим, что их недостаточно.
2) Док-во:
Всего у нас 36 клеток, домино занимают 10 клеток, 6*4-4 клеток по периметру, они на минимальность не влияют, поэтому вычтем их, итого у нас 36-(10+20)=6 клеток, больше, чем клеток квадрата 2x2, поэтому необходима ещё одно домино.

В общем виде для доски `l times l`, где `l` - чётное получается так:
если `l^2 - ( 2lceil l^2/2 rceil + 4(l-1) ) > 4`, то `k=lceil l^2/8+l^2 - ( 2lceil l^2/2 rceil + 4(l-1) ) rceil`.

[All_ex]

Груша Вильямс, 6*4-4 клеток по периметру, они на минимальность не влияют, - так периметр тоже неоднозначно выкладывается...
То есть надо избавляться не только от квадратов 2х2, но и от циклических контуров (типа периметра)...

[Груша Вильямс]

All_ex, да, точно, цикл. Вот от него я избавляюсь по такому алгоритму: беру определнный цикл, пусть он содержит `n` клеток, вычитаю цикл "периметр" (его всегда можно построить), то есть получаю `n-4(l-1)` клеток и сравниваю их с клетками квадрата 2x2, если `n-4(l-1)` клеток больше числа клеток `m`квадратов 2x2, то добавив `m` домино мы избавимся от цикла.
Странная конечно часть доказательства...

[Груша Вильямс]

То есть я думаю если сдвинуть домино на последнем рисунке вот так

(черные клетки, это клетки которых нет, то есть доска их как бы не содержит)
и решив для доски 3x2 исходную задачу, мы избавимся от цикла. Думаю, что верно, но четкого понимания нет.

p.s. хотя если на рисунок смотреть, то кажется, что добавив одну от цикла или квадрата 2x2 не избавиться...

[Adjirranirr]

В каждой цветной фигуре должно быть занято по меньшей мере по 2 клетки. Если в двух из них занято по одной, то они расположены по соседству, и либо возникает 2 квадрата 2х2, либо замкнутый контур 3х4 с закрашенным центром.