Разрезание шахматной доски

[M1ham]

Наткнулся на интересную (на мой взгляд) задачу со вступительных экзаменов в ШАД, предлагавшуюся в 2015 году.
Имеется шахматная доска размеров $M\times N$ причем левый верхний угол есть белая клетка.
Справшивается: сколькими способами можно вырезать фигуру в которой не более 4 черных клеток. Разрезать можно только по границам клеток.
Задачу необходимо решить для
$ \begin{array}{l} N=M=8;\\ M=99, N=101;\\ M,N - \mbox{произвольные натуральные числа}. \end{array} $
Какие идеи, господа?

[worm2]

Идея номер 1: сначала рассмотреть задачу "сколькими способами можно вообще вырезать какую-нибудь фигуру из доски?", а потом попытаться наложить ограничение.

Был у нас участник Zealint (дай ему бог здоровья, почему пишу "был", потому что последнее посещение форума у него в 2014 г.), который на похожих задачах собаку съел. Он бы, наверное, сказал, подъёмная это задача или нет. А я пока не вижу, с какого боку к ней подойти.

Вывод: идея не работает (или я не умею её готовить).

-- Ср май 10, 2017 12:45:42 --

Идея номер 2: фигура, вырезанная из доски, наверное, должна быть связной в том смысле, что из любой её клетки в любую другую может попасть ладья, двигаясь только по клеткам этой фигуры. То есть мы не можем взять две чёрные клетки в разных углах доски и сказать: я портной, я так вижу фигуру. И пара чёрных клеток, располагающихся рядом по диагонали (имеющие лишь одну общую точку) — это тоже плохая, негодная фигура.

-- Ср май 10, 2017 12:54:49 --

Ага! Значит, фигура, имеющая не более 4 чёрных клеток, не может быть слишком большой! Фактически, мы можем выбрать 4 (или меньше) чёрные клетки, находящиеся "не слишком далеко" друг от друга, а потом наращивать на каждую такую конфигурацию белые клетки до посинения. Наверное, это всё можно вручную перебрать (нет ли желающих? ). А потом, когда мы перебрали все такие фигуры, дело в шляпе: каждая такая фигура обрамляется в минимальный прямоугольник $X \times Y$, и число вариантов для неё будет равно $\begin{xy}*{(M-X+1) \times (N-Y+1)}@+;p+LD;+UR**h@{-};s0+RD;s0+UL**h@{-}\end{xy}$ (или ноль, если какой-то из сомножителей не больше нуля). Нет. Здесь будет более сложная формула, связанная с тем, что фигуру нельзя двигать на произвольное число клеток, т.к. в половине случаев чёрные клетки заменяются на белые и наоборот. Но принципиальных проблем с её вычислением я, тем не менее, не вижу.

-- Ср май 10, 2017 12:58:11 --

Или цимес этой задачи как раз в том и состоит, чтобы перебрать возможные фигуры на компьютере?

-- Ср май 10, 2017 13:21:31 --

Идея номер 3: для минимального обрамляющего прямоугольника $X \times Y$, включающего только чёрные клетки искомой фигуры, должно выполняться: $X+Y \leqslant 8$ (было 4, исправил). Нужно перебрать все такие прямоугольники (добавление: по два раза, с учётом разных расцветок), и для каждого внутри перебрать всевозможные подмножества чёрных клеток количеством не более четырёх, для которых этот прямоугольник действительно является минимальным обрамляющим. Потом для каждого такого подмножества можно перебрать всевозможные подмножества белых клеток (любой мощности) внутри прямоугольника, проверяя для каждого такого подмножества, даёт ли оно в объединении с уже выбранным множеством чёрных клеток допустимую фигуру. Потом нужно не забыть, что каждую найденную таким образом фигуру можно ещё расширить на любое множество белых клеток снаружи прямоугольника $X \times Y$, смежных с выбранной внутри него чёрной клеткой (вроде бы, здесь можно хорошо оптимизировать, учитывая, что нас интересует только количество фигур, влезающих в определённый прямоугольник). Да, похоже, это под силу только компьютеру.

[EUgeneUS]

M1ham в сообщении #1215321 писал(а):

сколькими способами можно вырезать фигуру в которой не более 4 черных клеток.

Белая клетка вырезанная в разных местах доски - это разные "способы вырезания" или один и тот же?

[worm2]

Я так понял, что разные. Иначе не было бы смысла рассматривать большие доски (8x8 хватило бы на все случаи).

[EUgeneUS]

worm2 в сообщении #1215441 писал(а):

(8x8 хватило бы на все случаи)

FGJ - не на все.

[slavav]

Предполагается что фигура связная? В условиях задачи это явно не упоминается.

[SVD-d]

Да, наверное фигуры со сдвигом и поворотом суть разные, потому что иначе увеличение доски более чем 9х9 было бы бессмсленным делом. И, наверное, фигуры должны быть связными, потому что иначе количество вариантов на доске 8x8 точно равняется $\frac {32!}{(32-n_{black})!} \cdot 2^{32}$.

Будем думать.

Наверное, стоит пойти по нарастающей. Например, фигура на 0 чёрных клеток может выглядеть всего одним образом, и вырезать её из доски 8х8 можно тридцатью двумя различными способами.

Фигур с одной чёрной клеткой может быть одна минимальная, плюс её могут окружать или не окружать четыре белые, итого шестнадцать комбинаций. В глубине поля 8х8 набирается 18 чёрных клеток, итого 288 способов. Если уж учесть 12 чёрных находящихся по краям (3 белых вокруг, 8 комбинаций, 96 способов) и 2 по углам (2 белых вокруг, 4 комбинации, 8 способов), получается в сумме 392 способа. Для "не более", соответственно, 424.

Сразу можно расширить до доски $M \times N$. Если N и M оба нечётные, то в глубине доски содержится $(N-1)/2 \cdot (M-3)/2 + (N-3)/2 \cdot (M-1)/2$ чёрных клеток, на границах, соответственно, $(N-1) + (M-1)$, все с соответствующими множителями. в углах все белые. Если N чётно, а M - нет, то в глубине $(N-2)/2 \cdot (M-1)/2 + (N-2)/2 \cdot (M-3)/2$, на границах - $(N-2) + (M-2)$, а также два по углам. Если и N и M чётно, то мне внезапно стало лень считать. Плохой вариант.

Если мы берём две чёрных, то возьмёмся за предыдущий случай. Если мы брали чёрную с одной добавочной белой (таких всего четыре), то появляется три варианта, где вокруг белой эта чёрная может находиться. Для трёх белых (всего 3 комбинации) таких чёрных уже семь. Для двух белых (их всего шесть) либо 5 либо 6, в зависимости от того, какая комбинация была (4 или 2 комбинации соответственно). Комбинация с четырьмя белыми может быть дополнена восемью случаями, а чёрная без белых дополнена быть не может. В сумме 73 минимальных комбинации. Вокруг них можно включать и выключать белые, и я сейчас запутаюсь, настолько много этих белых стало. Плохой вариант.

Пойдём с другого конца. Две чёрных клетки, между которыми нет больше ни одной чёрной, могут находиться друг рядом с другом только в двух позициях: на прямой и на диагонали. Прямую в глубине доски окружают шесть белых клеток (седьмая внутри должна быть обязательно), итого 64 комбинации. Диагональ - четыре (и между ними может находиться одна или две), всего 48 вариантов. В глубине доски 8х8 прямых комбинаций может быть 24, диагональных 25. Рядом с границами прямых без боковушки 8, для каждой по 16 вариантов, прямых без верхушки 12, для каждой по 32 варианта, без того и другого - 4, для каждой 8 вариантов. Диагональных с откушенным углом 20, для каждой 24 варианта, по углам ещё четыре диагонали, для каждой из которых 12 вариантов, в сумме $24 \cdot 64 + 25 \cdot 48 + 8 \cdot 16 + 12 \cdot 32 + 4 \cdot 8 + 20 \cdot 24 + 4 \cdot 12 = 3368$. Если считать "не более", то 3792... Что-то тоже слишком сложно.

Может, имеет смысл прогонять часть доски $(M/2) \times (N/2)$?

Сейчас приеду домой, включу компьютер.

[M1ham]

slavav в сообщении #1215500 писал(а):

Предполагается что фигура связная? В условиях задачи это явно не упоминается.

Да, как я понял, фигура связная.

-- 10.05.2017, 21:31 --

worm2 в сообщении #1215380 писал(а):

Или цимес этой задачи как раз в том и состоит, чтобы перебрать возможные фигуры на компьютере?

На вступительном экзамене использование компьютера не предполагается....к сожалению.

-- 10.05.2017, 21:35 --

SVD-d в сообщении #1215505 писал(а):

Фигур с одной чёрной клеткой может быть одна минимальная, плюс её могут окружать или не окружать четыре белые, итого шестнадцать комбинаций. В глубине поля 8х8 набирается 18 чёрных клеток, итого 288 способов. Если уж учесть 12 чёрных находящихся по краям (3 белых вокруг, 8 комбинаций, 96 способов) и 2 по углам (2 белых вокруг, 4 комбинации, 8 способов), получается в сумме 392 способа. Для "не более", соответственно, 424.

Тоже рассуждал также, но потом подумал, что вариантов для ровно трех клеток и ровно четырех уж очень много, после чего и решил предложить эту задачку.


P.S Как правило задачки на вступительном решаются каким-то изящным методом...просто его нужно увидеть.

[svv]

Вы могли бы дать ссылку на задачу? Я её не нашёл среди задач 2015 года, возможно, не там искал.

[M1ham]

svv в сообщении #1215531 писал(а):

Вы могли бы дать ссылку на задачу? Я её не нашёл среди задач 2015 года, возможно, не там искал.

Вот нашел:

[SVD-d]

Можно попробовать рассмотреть "прямоугольный" треугольник с "гипотенузой" в девять клеток. Найти все варианты внутри него и предположить, что все остальные получаются из него поворотом и параллельным переносом.

[svv]

M1ham, спасибо.
А как понимать замечание на полях «вырезать можно только прямоугольники»?

[EUgeneUS]

svv
Вот только что подумал, что слово "участок" не является словом "фигура", и похоже, обозначает именно прямоугольник.

Тогда различных типов участков - 46. Не так много. Каждый из типов может сдвигаться на две клетки, пока не упрется в противоположную стенку.

UPD: 43. Еще три исключения не заметил :(

[svv]

Да, это здорово упростило бы задачу. Остаётся только уговорить на такой вариант автора темы.

[EUgeneUS]

svv
Угу, там нужно-то только учесть:

1. Повороты на 90 градусов участков 1х1, 2х2 и 3х3 не дает нового участка.
2. Участок 1х9 можно двигать вдоль длинной стороны только на четное число клеток, а вдоль короткой - на одну, но с одновременным сдвигом на одну вдоль длинной стороны.
3. Участок 3х3 можно двигать только четное число клеток по обеим координатам.

Еще более просто:

1. Для случаев $(8 \times 1) ... (1 \times 1) ... (1 \times 8), (2\times2), (2 \times 3), (3 \times 2)$ количество вариантов будет $(M-m+1)(N-n+1)$, где $m$ и $n$ - размер участка по соответствующей координате.

2. Для случая $(9 \times 1)$ количество вариантов будет числом белых клеток в прямоугольнике $(M-8 \times N)$
3. Для случая $(1 \times 8)$ количество вариантов будет числом белых клеток в прямоугольнике $(M \times N-8)$
4. Для случая $(3 \times 3)$ количество вариантов будет числом белых клеток в прямоугольнике $(M-2 \times N-2)$

случаи 2, 3 и 4 и составляют "подвох" задачи.