Семиклеточные «корытца»

[Ktina]

(по мотивам задачи Л. Емельянова)

Клетчатый прямоугольник разрезали по линиям сетки на семиклеточные «корытца» и нечётное число клеточек (хотя бы одно «корытце» присутствует).
Какое наименьшее число отдельных клеточек могло при этом оказаться?
(Семиклеточное «корытце» выглядит так:
, его можно поворачивать).

[Sirion]

Требуется найти минимум для каждого прямоугольника или среди всех прямоугольников?

[Sirion]

Судя по всему, второе. В таком случае условие нечётности излишне, ответ в любом случае 3. Докажем это.

Пусть у нас есть прямоугольник, разрезанный на какое-то количество "корытец". Предположим для начала, что длина и ширина прямоугольника больше двух. Отметим на нём "выпуклости" и "впуклости". Что это за звери?

Выпуклости - это прямоугольники 2х1, образующие борта корытца. На иллюстрации ниже большими "О" обозначены две выпуклости корытца, маленькими "о" - остальные клетки того же корытца.

O...O
OoooO

Впуклости - это:

а)Клетки, расположенные относительно некоторого корытца так, как показано на иллюстрации (впуклости обозначены иксами).

ox.xo
ooooo

б) Угловые клетки прямоугольника.

Каждому корытцу соответствует две уникальных выпуклости и две впуклости (вообще говоря, неуникальных, см. ниже). Ещё четыре впуклости даёт пункт б).
Очевидно, впуклости на карте соответствует либо отдельная клетка разрезания, либо выпуклость некоторого корытца. Можно сделать это утверждение ещё более очевидным, доказав его. Центральные клетки корытца (обозначенные малыми "о" на первой иллюстрации) с двух противоположных сторон граничат с клетками того же корытца. С другой стороны, впуклость и по вертикали, и по горизонтали граничит, в случае а), с клеткой своего корытца, а в случае б) - с клетками вне прямоугольника. Соответственно, при попытке покрыть впуклость одной из своих центральных клеток корытце а) пересечётся с другим, б) выйдет за границы прямоугольника.

Две впуклости, принадлежащие разным корытцам, могут совпадать (см. иллюстрацию ниже). Однако при этом две соседствующие с ними выпуклости тех же корытец уже не могут покрыть никакой впуклости.

aaaaa..
a.b.a.b
..bbbbb

Две выпуклости различных корытец могут находиться в соседних клетках в следующих случаях:

1)
aaaaa.
ab..ab
.bbbbb
2)
aaaaa...
a..ba..b
...bbbbb
3)
aaaaa
a...a
b...b
bbbbb
4)
aaaaa..
a...a..
..b...b
..bbbbb

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

#ooooo
#o...o
######

Впуклости, не находящиеся в соседних клетках, не могут быть покрыты одной и той же выпуклостью по очевидным причинам. Итак, резюмируем: на N корытец у нас есть 2N выпуклостей и 2N+4 (с учётом кратности) впуклостей. Каждая впуклость либо покрыта соответствующей только ей выпуклостью, либо совпадает с другой впуклостью, но при этом две выпуклости выбывают из игры, либо, наконец, не покрыта ничем. Отсюда следует, что при разрезании прямоугольника, чьи длина и ширина больше двух, получится не менее четырёх отдельных клеток.

В случае, если одна из сторон прямоугольника равна двум, а вторая равняется a, количество корытец, которые могут в нём поместиться, равняется [a/5], а минимальное количество отдельных клеток - 2a - 7[a/5]. Очевидно, победителем в этой номинации является прямоугольник 2х5 с тремя отдельными клетками.

[rockclimber]

Честно говоря, не понял условия задачи. Взяли прямоугольник 2 х 5, вырезали корыто и остался кусок 1 х 3. Эти три клеточки на части уже не режутся и одиночными квадратами не считаются. Так? И резать надо так, чтобы после вырезания "корыт" оставались только обрезки единичного размера? Или любые обрезки можно, лишь бы единичных было нечетное количество?

[Ktina]

Sirion в сообщении #1103739 писал(а):

Требуется найти минимум для каждого прямоугольника или среди всех прямоугольников?

Среди всех, разумеется.
Условие почти полностью повторяет ту задачу, по мотивам которой создано, с той лишь разницей, что там корытце шестиклеточное было, что делало задачу несложной.

[Sirion]

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

А какое у вас решение, если не секрет?

[Ktina]

Sirion
Не секрет, мне только для шестиклеточных удалось найти

[Sirion]

Забавно. Моё решение, кажется, работает для корытец любого размера $\geqslant 7$, а вот для 6 не сработает.