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

[lexus c.]

Помогите, пожалуйста с этими тремя задачами:

1. Отметить на доске 8Х8 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.

Ясно, что отмеченные клетки должны группироваться "парами". Мне кажется, что подобная задача невыполнима.

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

Не встречал таких задач ранее, честно говоря, поэтому нет особых идей.

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

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

[PAV]

Переезжаем из "Помогите решить" в олимпиадный раздел

[Henrylee]

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

Помогите, пожалуйста с этими тремя задачами:

1. Отметить на доске 8Х8 несколько клеток так, чтобы любая (в том числе и любая отмеченная) клетка граничила по стороне ровно с одной отмеченной клеткой.

Ясно, что отмеченные клетки должны группироваться "парами". Мне кажется, что подобная задача невыполнима.

Нашел нужную расстановку. Перечислю отмеченные клетки, пользуясь шахматными координатами.

$a3,a4,a7,a8,b1,c1,c5,c6,d3,d8,e3,e8,f1,f5,f6,g1,h3,h4,h7,h8$

[lexus c.]

PAV, ну, здесь только одна задача, насколько мне известно, олимпиадная.

Henrylee, точно! Спасибо Вам большое )

[Brukvalub]

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

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

Не встречал таких задач ранее, честно говоря, поэтому нет особых идей.

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

[lexus c.]

Brukvalub писал(а):

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

2. Можно ли доску 6Х6 с двумя вырезанными противоположными углами обойти ходом шахматного коня, побывав в каждой клетке ровно по одному разу?

Не встречал таких задач ранее, честно говоря, поэтому нет особых идей.

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

Надо же, и правда )))
Что-то я торможу )
Спасибо огромное!

[Батороев]

Brukvalub писал(а):

на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета...

От четности не зависит. Просто диагонали досок так раскрашивают

[Brukvalub]

Батороев писал(а):

Brukvalub писал(а):

на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета...

От четности не зависит. Просто диагонали досок так раскрашивают

Разве я где-либо утверждал, что у досок с нечетным числом клеток на стороне это свойство нарушается?

[ИСН]

Батороев писал(а):

От четности не зависит.

От чётности зависит другое, для нас тоже нужное: что клеточек каждого цвета на доске (до обрезания) поровну.

[lexus c.]

А, и вот ещё одна вдогонку:

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

[Батороев]

ИСН писал(а):

Батороев писал(а):

От четности не зависит.

От чётности зависит другое, для нас тоже нужное: что клеточек каждого цвета на доске (до обрезания) поровну.

Я только "обрезание" и имел в виду

[Zak]

Brukvalub писал(а):

Батороев писал(а):

Brukvalub писал(а):

на доске, стороны которой имеют четное число клеток, такие вырезы убирают клетки одного цвета...

От четности не зависит. Просто диагонали досок так раскрашивают

Разве я где-либо утверждал, что у досок с нечетным числом клеток на стороне это свойство нарушается?

А на прямоугольной доске вообще нет диагоналей...

[Henrylee]

У меня есть смутное ощущение, что задачу про тараканов можно переформулировать таким образом, что она станет похожа на первую. В качестве отмеченных будут пустые клетки после "тараканьих бегов" итп.. Только условия "соседства" нужно подобрать особым образом..

Добавлено спустя 14 минут 6 секунд:

Может быть таким образом.
Будем считать клетки с тараканами после бегов (непустые) отмеченными Тогда задача (видимо) переформулируется так:
отметить на доске клетки так, чтобы любая клетка граничила стороной с двумя отмеченными. Причем отмтить таким образом, чтобы число отмеченнх леток было наименьшим.

[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$), что количество парных инверсий (равное количеству фигур) должно быть чётным.

[Henrylee]

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