Вырезание прямых тримино

[Pythagoras]

Задача: из клетчатого квадрата 20х20 вырезали 48 прямоугольников 1х3. Доказать, что можно вырезать ещё хотя бы один.

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

Ещё большой квадрат можно разрезать на 100 квадратиков 2х2. Из них хотя бы 4 (100-2*48) не пересекаются ни с одним из вырезанных прямоугольнико 1х3. Но этого недостаточно.

Если рассмотреть вырезание максимального числа прямоугольников 1х3, то их получается сильно меньше, чем 48*3+1.

Подскажите, какая конструкция тут поможет.

[mihaild]

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

[Gagarin1968]

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

[TOTAL]

Pythagoras в сообщении #1719124 писал(а):

Задача: из клетчатого квадрата 20х20 вырезали 48 прямоугольников 1х3. Доказать, что можно вырезать ещё хотя бы один.

После того как вырезали $49$-й прямоугольник, можно ли вырезать ещё хотя бы один?

[waxtep]

TOTAL в сообщении #1719148 писал(а):

После того как вырезали $49$-й прямоугольник, можно ли вырезать ещё хотя бы один?

Вроде даже два, если воспользоваться рецептом

mihaild в сообщении #1719126 писал(а):

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

то всего разных прямоугольников $720$ (какие-то из них, конечно, пересекаются друг с другом), а каждый вырезанный портит не более $13=4+3\times3$ из оставшихся, и $\lfloor720/14\rfloor=51$. Интересно, можно ли еще больше, при наихудшем расположении предыдущих вырезок

-- 28.02.2026, 20:44 --

Ну то есть, даже ещё три: после вырезания $51$-го останется ещё минимум $6$ неиспорченных полосок

[waxtep]

Почти наверняка нужно вырезать больше, чем $52$ полоски, чтобы испортить квадрат $20\times20$. Ведь $13$ соседей портит только вырезание полоски далеко от границы квадрата, а и исходно есть границы, и по мере вырезания будут появляться новые. Очевидная оценка сверху, - $80$ полосок, ведь квадрат $5\times5$ можно испортить пятью полосками, и протиражировать его $16$ раз:
XXXOO
OOXXX
XXXOO
OOXXX
XXXOO
Интересно найти точный минимум

[mihaild]

waxtep в сообщении #1719166 писал(а):

Интересно найти точный минимум

Попробовал запустить ortools https://github.com/mihaild/dxdy/blob/ma ... ge/main.py (код сгенерирован gemini, вроде правильный), за 10 часов ничего меньше 80 не нашлось.

[Pythagoras]

Решение, которое предложили mihaild и waxtep, я понял, спасибо!

Gagarin1968, ваше предложение не понял. Да, про такую раскраску я тоже думал. Там одного цвета остаётся 86 и двух других цветов по 85. И что?

[TOTAL]

Pythagoras в сообщении #1719124 писал(а):

Ещё большой квадрат можно разрезать на 100 квадратиков 2х2.

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