Клетчатый бумажный квадрат (по мотивам ленинградской олимп.)

[Ktina]

Можно ли клетчатый бумажный квадрат $17\times 17$ клеток разрезать «по клеточкам» на несколько прямоугольников, каждый из которых имеет размеры $3\times 4$ или $5\times 5$ клеток?

[iou]

То ли лыжи не едут, то ли задача какая-то простая..
Для возможности разрезания уравнение $12n+25m=289, m, n\in \mathbb{N}$ должно иметь решения.
Заметим, что $m$ нечётно, тогда $m=2k+1 => 12n+50k=264$
Также заметим, что $k\leqslant 5$, подставляя различные значения $k$ убедимся, что уравнение не имеет решений, поэтому ответ: нет.

[Iam]

$12m+25n=289, 6m+13n=145 $. Второе уравнение получается из подсчета белых клеток, соответствующих цвету центральной клетки (вариант $6m+12n=145$ отпадает).
Отсюда $m=22, n=1$.
В каждой горизонтальной строке, свободной от квадрата может находиться ровно 2 горизонтально расположенных прямоугольника и 3 вертикально расположенных – всего 5. В каждой горизонтальной строке, в которой занимает некоторые клетки квадрат, находится либо 3, либо 4 прямоугольника.
При сканировании всех строк мы пересечем вертикальные границы прямоугольников $10\cdot 12+6\cdot 5=150$ или $10\cdot 12+8\cdot 5=160$ раз. Аналогично при сканировании столбцов.
Таким образом, мы всего пересечем границы всех прямоугольников либо $300$, либо $310$, либо $320$ раз. С другой стороны, у каждого прямоугольника мы пересекли границу каждой клетки, а это $22\cdot 14=308 $ раз. Что-то не сходится.

[Ktina]

iou в сообщении #1111993 писал(а):

То ли лыжи не едут, то ли задача какая-то простая..
Для возможности разрезания уравнение $12n+25m=289, m, n\in \mathbb{N}$ должно иметь решения.

А $12\cdot 22+25\cdot 1$ разве не $=289$?

[iou]

Ktina в сообщении #1112014 писал(а):

А $12\cdot 22+25\cdot 1$ разве не $=289$?

Да, решать задачи ночью идея не очень.. Ведь $k$ может быть нулём, а я отталкивался от $k\geqslant1$

[Andrey A]

Можно построить квадраты $11\times 11, 13\times 13, 19\times 19$ - всё это центрально симметричные фигуры с квадратом $5\times 5$ в центре. Квадрат из условия так не построить: $(17^2-5^2)/4=66$ - не кратно $12$-ти. Если только какая-то "диагональная симметрия"...

[DeBill]

Iam в сообщении #1111996 писал(а):

мы пересечем вертикальные границы прямоугольников $10\cdot 12+6\cdot 5=150$ или $10\cdot 12+8\cdot 5=160$ раз.

Но, увы, возиожны и промежуточные варианты....

-- 04.04.2016, 13:52 --

А впрочем, нет. Но - не сразу.
Введем систему координат (центральная клетка - начало координат). Сумма координат точек из любого прямоугольника равна 0 по модулю 12 (а для квадрата - равна координате его центра). Значит, центр квадрата - на прямой $x+y = 0 (\mod 12)$. Из соображений симметрии - и на прямой $ x-y = 0 (\mod 12) $. Таких точек - 9 (центр, и точки, полученные сдвигами на 6). Для углового положения: так как $12 = 3\cdot 4$ либо $4\cdot 3$, то прямоугольнички, идущие направо, вылазят вверх, и получается незамомойстная (?) полоска длины 5. Аналогично для "бокового" расположения. А вот для центрального получается, что со всех сторон остаются промежутки ширины 6, и тогда подсчет, проведенный Iam
, приводит, наконец, к цели.....

[grizzly]

iou в сообщении #1112028 писал(а):

Ведь $k$ может быть нулём

Но тогда квадратов только 1. Разукрашками по диагоналям в два / в три цвета можно ограничить положение этого квадрата с дискретностью в 6 клеток (в углах или по центральной горизонтали / вертикали). Все положения, кроме центрального, с очевидностью отбраковываются. Центральное тоже легко отбраковывается, но чуть дольше.

-- 04.04.2016, 13:10 --

Кто ж знал, что выше уже тоже самое не по-детски расписано...

[Iam]

Iam в сообщении #1111996 писал(а):

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

Не думал, что это нужно еще как-то детализировать, а оказалось, что нужно.
Сейчас поправлю.

[DeBill]

Iam

Я имел в виду, что

Iam в сообщении #1111996 писал(а):

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

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

[Iam]

DeBill,
Ваш намек

DeBill в сообщении #1112038 писал(а):

Но, увы, возможны и промежуточные варианты....

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

[DeBill]

Iam в сообщении #1112117 писал(а):

должен быть какой-то очень простой ход.

Вот точно. Конечно, решение мы общими усилиями получили.
Но как то громоздко оно выглядит....

[Iam]

Обозначу ход полученного общими усилиями решения задачи.
1. Устанавливается что квадрат лишь один. Для этого достаточно рассмотреть лишь одно уравнение для общего числа клеток. Второе уравнение (для клеток одного цвета) тоже не вредно.
2. Позиционирование квадрата. Замечательная идея для этого предложена by DeBill, из которой получается, что квадрат $5 \times 5$ должен находиться в центре поля $17 \times 17$.
3. При таком расположении квадрата мы можем подсчитать в каждой строке (столбце) число клеток, входящих как в горизонтальные,так и вертикальные прямоугольники. При этом из уравнения $4N_h+3N_v=17$ легко получить, что в каждой строке, свободной от квадрата, число горизонтальных прямоугольников равно $N_h=2$, а вертикальных $N_v=3$, т. е. всего прямоугольников $N=5$. Для всех строк, в которых имеются клетки квадрата, соответствующее число также одинаково и равно $N’=4$. Следовательно, если мы просканируем строки всего поля и посчитаем общее число пересечений границ прямоугольников то получим $G_v=160$.
Те же рассуждения для столбцов поля дают общее число пересечений границ прямоугольников при сканировании по столбцам $G_v=160$.
4. Таким образом, общее число пересечений границ прямоугольников при вертикальном и горизонтальном сканировании равно $G=320$. Но это число должно быть равно сумме периметров всех прямоугольников $P_{\sigma}$, а это не так, поскольку $P_{\sigma}=22\cdot14=308$.

Следовательно, замощение квадрата $17 \times 17$ при таких условиях невозможно.

Замечание. В принципе не обязательно позиционировать квадрат в центре поля. Достаточно убедиться в том, что его какая-либо сторона должна быть удалена от границы поля на расстояние $3$ или $6$ клеток (практически это очевидно). При этом, например, $G_h=160, G_v=120+2\cdot 4k+2 \cdot 3(5-k) $, $G=310+2k \ne P$, где $k$ - число занятых квадратом столбцов, в которых число горизонтально расположенных прямоугольников равно 4.

[grizzly]

DeBill, Iam
Ваш метод хорош, но это пока задачка такая простая -- есть один жирный квадрат $5 \times 5$ и понятно, что его никуда не приткнёшь. А вот пусть те же прямоугольнички $3 \times 4$ -- 22 штуки, а вместо жирного квадрата 5 полосочек $1\times 5$?

Upd. Удалено. Grizzly промахнулся