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

[lexus c.]

CD_Eater писал(а):

lexus c. писал(а):

Можно ли доску 10*10 разрезать на набор фигурок из четырех клеток в форме букв Г и L (т.е. набор может быть смешанным)?

Нельзя. Потому что 25 фигур.

Утверждение Если прямоугольная доска разбивается на Г- и L- фигуры, то разбиение состоит из чётного числа фигур.
Пусть такое разбиение существует - доска покрыта Г- и L- фигурами полностью и без пересечений. По крайней мере одна из длин сторон доски (или количество рядов $h$, или количество столбцов $w$) должна быть чётна. Пусть количество столбцов $w$ чётно. Будем по одной снимать фигуры с доски и подсчитывать, сколько клеток осталось закрыто фигурами на каждой горизонтали. Сначала в каждом ряду закрыто по $w$ клеток $x_1=x_2=...=x_h=w$, после снятия всех фигур станет $x_1=x_2=...=x_h=0$. Заметим, что снятие каждой фигуры уменьшает счётчики клеток на (1,3) или (3,1) или (1,1,2) или (2,1,1). Рассмотрим чётности этих количеств $y_i=x_i \mod 2$. Перед снятием фигур и после снятия все $y_i=0$, а снятие одной фигуры инвертирует чётность какой-то пары соседних счётчиков $y_i, y_{i+1}$. Легко доказать по индукции (индукция по числу рядов $h$), что количество парных инверсий (равное количеству фигур) должно быть чётным.

Спасибо большое! Теперь всё с этой задачей ясно )

Добавлено спустя 35 минут 2 секунды:

Henrylee писал(а):

Про тараканов.
Действительно, удалось найти 1 расстановку, в которой любая клетка граничит ровно с 2-мя отмеченными и одну расстановку (с точностью до поворота доски), где выполняется условие выше кроме 2-х клеток, которые граничат с тремя отмеченными. В обоих случаях число неотмеченных (путых) клеток 24.

А Вы не могли бы "показать" свой вариант?
Очень жаль, но в своём я ошибся. У меня, всё же, не получилось освободить 24 клетки.

[ИСН]

 ________________
|X|X|X|X|X|X|X|X|
|X|_|_|_|_|_|_|X|
|X|_|X|X|X|X|_|X|
|X|_|X|_|_|X|_|X|
|X|_|X|_|_|X|_|X|
|X|_|X|X|X|X|_|X|
|X|_|_|_|_|_|_|X|
|X|X|X|X|X|X|X|X|

[TOTAL]

Тараканы

Черных клеток с четырьмя белыми тараканами на каждой может быть не более 5 (они расположены не у края, по крайней мере через одну по диагонали, по крайней мере через три по вертикали, горизонтали). Из рисунка это хорошо видно. Для размещения оставшихся по крайней мере 44 белых тараканов (их уже не более 3 на клетке) понадобится по крайней мере 15 черных клеток. Всего будет занято тараканами по крайней мере 5+15=20 черных клеток. Столько же белых. Свободно не более 24 клеток.

[CD_Eater]

Про тараканов. Как известно, шахматная доска состоит из зелёных и жёлтых клеток.
Докажем, что среди зелёных клеток останется не более 12 свободных.
Достаточно рассмотреть не всех тараканов, а только выползших из жёлтых клеток, обведённых чёрной рамкой. Разобьём доску на зоны, как показано, и в каждой зоне оценим сверху количество свободных зелёных клеток.

[Батороев]

lexus c. писал(а):

А Вы не могли бы "показать" свой вариант?

Если нигде не ошибся, то может, пойдет ...для статистики:
Свободные: b2, b3, b4, b5, b6, b7, c7, d1, d2, d3,
d4, d5, d7, e7, f2, f3, f4, f5, f6, f7, g2, h4, h5, h8.
Здесь три клетки граничат с тремя отмеченными.

[lexus c.]

TOTAL писал(а):

Тараканы

Черных клеток с четырьмя белыми тараканами на каждой может быть не более 5 (они расположены не у края, по крайней мере через одну по диагонали, по крайней мере через три по вертикали, горизонтали). Из рисунка это хорошо видно. Для размещения оставшихся по крайней мере 44 белых тараканов (их уже не более 3 на клетке) понадобится по крайней мере 15 черных клеток. Всего будет занято тараканами по крайней мере 5+15=20 черных клеток. Столько же белых. Свободно не более 24 клеток.

По поводу клеток с четырьмя тараканами на диагонали:
по-моему, ничто не мешает шести клеткам на главной диагонали (кроме самых "угловых") содержать по 4 таракана каждой (и всё тараканы при этом будут белыми )) ).

Добавлено спустя 4 минуты 30 секунд:

ИСН, Батороев, спасибо )

Добавлено спустя 52 секунды:

CD_Eater, Вам отдельное спасибо за столь изящное доказательство

[TOTAL]

убрано

[baghi]

CD_Eater писал(а):

lexus c. писал(а):

Можно ли доску 10*10 разрезать на набор фигурок из четырех клеток в форме букв Г и L (т.е. набор может быть смешанным)?

Нельзя. Потому что 25 фигур.

Утверждение Если прямоугольная доска разбивается на Г- и L- фигуры, то разбиение состоит из чётного числа фигур.
Пусть такое разбиение существует - доска покрыта Г- и L- фигурами полностью и без пересечений. По крайней мере одна из длин сторон доски (или количество рядов $h$, или количество столбцов $w$) должна быть чётна. Пусть количество столбцов $w$ чётно. Будем по одной снимать фигуры с доски и подсчитывать, сколько клеток осталось закрыто фигурами на каждой горизонтали. Сначала в каждом ряду закрыто по $w$ клеток $x_1=x_2=...=x_h=w$, после снятия всех фигур станет $x_1=x_2=...=x_h=0$. Заметим, что снятие каждой фигуры уменьшает счётчики клеток на (1,3) или (3,1) или (1,1,2) или (2,1,1). Рассмотрим чётности этих количеств $y_i=x_i \mod 2$. Перед снятием фигур и после снятия все $y_i=0$, а снятие одной фигуры инвертирует чётность какой-то пары соседних счётчиков $y_i, y_{i+1}$. Легко доказать по индукции (индукция по числу рядов $h$), что количество парных инверсий (равное количеству фигур) должно быть чётным.

вроде придумал геом решение: раскраска полосками ч-б-ч-б...
каждая фигура будет содержать нечетное кол-во черных [пусть] клеток, фигур 25 =>
покроется нечетное число квадратов [которых всего 50, то есть разрезать нельзя]