М2010. Зв’язна клітинна фігура

Задача із журналу «Квант» (2006 рік, №4)

Умова

Для натуральних чисел $m$ і $n$ позначимо через $F(m,n)$ кількість всіх зв’язних клітинних фігур прямокутнику $m\times n$. Доведіть, що парність числа $F(m,n)$ збігається з парність числа $\frac{n(n+1)}{2}\cdot\frac{m(m+1)}{2}.$ (Зв’язна клітинна фігура – це така непорожня множина клітин, що з будь-якої клітини цієї множини можна пройти в будь-яку іншу клітину цієї множини по клітинах цієї множини, переходячи щоразу в сусідню по стороні клітину.)

А.Бадзян

Рішення

Припустимо, що $F(m,0) = 0.$ Зв’язні фігури в прямокутнику $m\times 1$ – це $m$ фігур з однієї клітини та смужки із двох або більше клітин. Кожна смужка визначається парою клітин – першою та останньою, тому $$F(m,1) = m + \frac{m(m-1)}{2} = \frac{m(m+1)}{2}.$$

Нехай у прямокутнику $m$ рядків та $n\gt 1$ стовпців. Позначимо через $l$ вертикальну вісь симетрії. Кожній зв’язній фігурі відповідає фігура, симетрична щодо $l,$ тому несиметричні щодо $l$ фігури розбиваються на пари, і парність $F(m,n)$ збігається з парністю кількості зв’язних фігур, симетричних щодо $l.$

Розглянемо деяку фігуру $T,$ симетричну щодо $l.$

Нехай $n$ непарне, $n =2k-1,$ $k\ge 2.$ Фігура $T$ містить хоча б одну клітину $k$-го стовпця, інакше з клітини фігури $T$ неможливо пройти по клітинам $T$ в симетричну відносно $l$ клітину, переходячи кожен раз в сусідню клітину. Зауважимо, що частина $T_{1}$ фігури $T,$ що розташована в $k$ найлівіших стовпцях, зв’язна. Дійсно, розглянемо дві клітини $x$ та $y$ фігури $T_{1}.$ Нехай $x’$ – клітина, що симетрична $x$ відносно $l,$ a $x’,z_{1},z_{2},\ldots,z_{t},y$ – послідовність клітин, що утворює шлях з $x’$ в $y$ по сусідніх клітинах фігури $T.$ Тоді, замінюючи в цьому шляху клітини, що лежать правіше $k$-го стовпця, на симетричні щодо $l,$ ми отримаємо шлях з $x$ в $y$ по сусідніх клітинах фігури $T_{1}$ (див. малюнок). Навпаки, якщо фігура $T_{1}$ розташована у прямокутнику, що складається з $k$ найлівіших

стовпців, зв’язна і містить хоча б одну клітину $k$-го стовпця, можна однозначно продовжити фігуру $T_{1}$ до зв’язної фігури $T,$ симетричної відносно $l$. Кількість зв’язних фігур у прямокутнику $m\times k$ дорівнює $F(m,k),$ серед них $F(m,k-1)$ фігур лежать у перших $k-1$ стовпцях (тобто не містить клітин $k$-го стовпця). Отже, кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times (2k-1)$ дорівнює $F(m,k)-F(m,k-1).$

Для парного $n = 2k,$ $k\ge 1,$ міркуючи аналогічно, встановимо взаємно однозначну відповідність між зв’язними симетричними щодо $l$ фігурами та зв’язними фігурами, що розташовані в перших $k$ стовпцях і що містять хоча б одну клітинку $k$-го стовпця. Звідси випливає, що кількість зв’язних симетричних щодо $l$ фігур у прямокутнику $m\times 2k$ дорівнює $F(m,k)-F(m,k-1).$

Отже, для $n = 2k-1$ и $n = 2k$ парність $F(m,n)$ збігається з парністю числа $F(m,k)-F(m,k-1).$

Доведемо індукцією по $n,$ що $F(m,n)$ непарно тоді і лише тоді, коли $m$ і $n$ дають залишок $1$ або $2$ при діленні на $4;$ звідси відразу випливає твердження задачі. Твердження вірне при $n = 0$ і $n = 1.$

Нехай $m$ дає залишок $0$ або $3$ при діленні на $4.$ Припустимо, що це твердження вірне для $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто ці числа парні. Якщо $n = 2k-1,$ $k\ge 2,$ або $n = 2k,$ $k\ge 1,$ то $n\gt k,$ тому $F(m,n)$ парне, так як $F(m,k)-F(m,k-1)$ парне. Нехай $m$ дає залишок $1$ або $2$ при діленні на $4.$ Припустимо, що твердження вірно для чисел $F(m,0),F(m,1),\ldots,F(m,n-1),$ тобто $F(m,s)$ непарне тоді і лише тоді, коли $s$ дає залишок від ділення $1$ або $2$ при діленні на $4.$ Тоді $F(m,s)-F(m,s-1)$ непарне тоді і лише тоді, коли $s$ непарне. Звідси випливає, що $F(m,n)$ непарне тоді і тільки тоді, коли $n = 2(2l + 1)-1 = 4l + 1$ або $n = 2(2l + 1) = 4l + 2.$

А.Бадзян

Задача из журнала «Квант» (2000 год, 3 выпуск) М1707*

Условие

Квадрат клетчатой бумаги, состоящий из $n\times n$ клеток, разрезан на $2n$ прямоугольников. При этом каждый прямоугольник расположен либо целиком ниже, либо выше ступенчатой ломаной, разделяющей квадрат (рис.1). Докажите, что найдется клетка клетчатой бумаги, являющаяся одним из названных прямоугольников.

Рис. 1

Решение

Ступенчатая ломанная разрезает квадрат на два ступенчатых треугольника $T_1$ и $T_2$, при этом основание $T_1$ состоит из $n$ клеток, а основание $T_2$ – из $n – 1$ клетки. В силу условия задачи, один из них разрезан на $m$, а другой – на $k$ прямоугольников, причем $m + k = 2n$. Пока что фиксируем внимание на отдельно взятом ступенчатом треугольнике $T$, в основании которого $s$ клеток (рис.2). Так как при разрезании $T$ на прямоугольники любые две точки из набора $A_1, A_2, \ldots, A_s$ должны принадлежать разным прямоугольникам, можно заключить, что $T$ нельзя разрезать на менее чем $s$ прямоугольников.

Рис. 2

Разберем далее тот случай, когда $T$ разрезан в точности на s прямоугольников; тогда каждая из точек $A_1, A_2 , \ldots, A_s$ принадлежит только одному из них и, более того, каждая из $s$ закрашенных клеток принадлежит целиком только одному из $s$ прямоугольников. Не закрашенных клеток, примыкающих по сторонам к закрашенным, на единицу меньше, чем закрашенных, поэтому хотя бы один из $s$ прямоугольников не выйдет за пределы своей заштрихованной клетки, т.е. будет с ней совпадать. Возвращаясь к ступенчатым треугольникам $T_1$ и $T_2$, можно сказать, что $m \geq n$, а $k \geq n-1$. Но так как $m + k = 2n$, то либо $m = n$, либо $k = n – 1$. Значит, либо в $T_1$, либо в $T_2$ найдется прямоугольник, совпадающий с клеткой клетчатой бумаги.

В.Произволов

М1716. Тетрадь в клетку

Задача из журнала «Квант» (2000 год, 1 выпуск)

Условие

В квадрате клетчатой бумаги размером $n\times n$ клеток отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или не отмеченная) имеет хотя бы одну отмеченную соседнюю клетку. Определите наименьшее возможное значение $N$, если соседними считать клетки, имеющие общую сторону.

Решение

Рассмотрим случай четного $n$.

Сначала раскрасим доску в черный и белый цвета в шахматном порядке. Пусть $f\left(n\right)$ — это искомое число, а $f_{\omega}\left(n\right)$ — минимальное число белых клеток, которые должны быть отмечены таким образом, чтобы каждая черная клетка имела соседнюю отмеченную белую. Определим подобным образом $f_{b}\left(n\right).$ Благодаря симметричности шахматной доски $\left(n = 2k\right)$, мы имеем $f_{\omega}\left(n\right) = f_{b}\left(n\right)$; кроме этого, $f\left(n\right) = f_{\omega}\left(n\right) + f_{b}\left(n\right)$.

Было бы более удобно посмотреть на доску, развернув ее таким образом, чтобы главная черная диагональ (самая длинная) располагалась горизонтально. Тогда длины остальных черных диагоналей были бы $2, 4, \ldots, 2k, \ldots, 4, 2.$

Зачеркнем «нечетные» клетки белых диагоналей, расположенных под черными диагоналями длины $4i — 2$ в первом случае и под черными диагоналями длины $4i + 2$ во втором случае (см. рисунок).

m1716

В первом случае зачеркнутыми окажутся $2i$ белых клеток, а во втором случае $2i + 1$ белых клеток. Таким образом, всего мы зачеркнем
$$2 + 4 + \ldots + k + \ldots + 3 + 1 = \frac{k\left(k+1\right)}{2}$$
белых клеток. Легко видеть, что каждая черная клетка имеет белую зачеркнутую соседнюю клетку. Из этого следует, что
$$f_{\omega}\left(n\right) \leqslant \frac{k\left(k+1\right)}{2}.$$

Рассмотрим $\displaystyle\frac{k\left(k+1\right)}{2}$ зачеркнутых белых клеток: у них нет общих черных соседних клеток, следовательно, нам нужно по крайней мере $\displaystyle\frac{k\left(k+1\right)}{2}$ черных отмеченных клеток с тем, чтобы «охватить» все эти белые клетки. Поэтому
$$f_{b}\left(n\right) \geqslant \frac{k\left(k+1\right)}{2}.$$
Отсюда мы имеем
$$f_{\omega}\left(n\right) = f_{b}\left(n\right) = \frac{k\left(k+1\right)}{2},$$
$$f\left(n\right) = k\left(k+1\right).$$

Аналогично доказывается, что
\begin{equation*}
f\left(n\right) =
\begin{cases}
4k^2 — 1 &\text{при $n = 4k — 1$,}\\
\left(2k + 1\right)^2 &\text{при $n = 4k + 1$.}
\end{cases}
\end{equation*}

Е. Баранов, И. Воронович

M1489

Для каких прямоугольников $latex m\times n $ на клетчатой бумаге, в клетках которых расставлены нули и единицы, можно получить из любой расстановки любую другую, если разрешается изменять числа одновременно в каждой строке, каждом столбце и на каждой прямой, параллельной диагоналями клеток (в частности, в угловых клетках)?

Решение: это всегда возможно для прямоугольников $latex m\times n $, лишь если $latex m $ и $latex n $ не больше 3. поскольку операцию можно выполнять в обратном порядке, достаточно выяснить, для каких таблиц $latex m\times n $ из любой расстановки можно получить таблицу из одних едениц.

Легко видеть, что для прямоугольников $latex 1\times n $, $latex 2\times n $ и $latex 3\times n $ заменами знаков можно получить таблицу из одних единиц: на рисунке 1 указан порядок, в котором нули, стоящие в некоторых клетках, можно заменить на единицы(цветные линии показывают какой именно — вертикальный или диагональный — «ход» следует делать).

С другой сторны, в прямоугольнике $latex m\times n $, где m и n не меньше 4, можно выделить фигуру из восьми клеток, показанных на рисунке 2 штриховкой; четность количества единиц не меняется в этих клетках при всех разрешенных преобразованиях — является, как говорят, инвариантом. Таким образом, если в одной из таких фигур стоит нечетное число единиц, то прийти к таблице заполненной единицами, невозможно.

Представляем читателям выяснить, образуют ли такие таблицы из 8 клеток полную систему инвариантов, также следует ли из четности количества единиц в каждой из них возможность преобразовать таблицу в состояние «все единицы», а заодно выяснить, сколько существует классов (неэквивалентных друг другу) таблиц относительно разрешенных в условии преобразований.

А.Галочкин