Решение. Доказательство максимальности: Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.

Ответ: 16 королей.

Доказательство максимальности: Разобьём доску на 16 квадратиков, в каждом может быть не более одного короля.

 

 

 

V.Раскраски

1. Свойства раскрасок

Раскраска «решает» задачу, если она:

Инвариантна, т.е. при любом движении замощающей фигуры сохраняется некоторое свойство. Например, количество чёрных клеток постоянно или количество белых клеток нечётно

 

Виды и модификации раскрасок

Основные виды:

Шахматная

Диагональная

Галетная

 

 

Подвиды:

Крупная

 

Многоцветная

 

 

Способы прийти к противоречию

Доказать, что клетчатую доску 10´10 нельзя разрезать по линиям сетки на прямоугольники 1´4.

По количеству

 

Решение. Разделим доску на квадраты 2´2 и раскрасим их в шахматном порядке. Заметим, что любой прямоугольник 1´4 содержит поровну (по 2) чёрных и белых клеток, но при данной раскраске на доске ______ чёрных клетки и ___ белых, т.е. не поровну. Значит, разрезать доску 10´10 на тетрамино 1´4 не удастся.

 

По делимости без уравнения

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

 

По делимости с уравнением

Решение;

Каждая мегадоминошка может занимать либо 1, либо 3 чёрных клетки

Пусть первых будет x штук, тогда вторых штук

Тогда всего чёрных клеток будет:

Значит,

 

Это уравнение не имеет решений в целых числах, значит замостить нельзя

 

 

 

Раскраски для тетрамино

I-тетрамино: тельняшка вертикальная и горизонтальная (по чётности)

T-тетрамино: тельняшка (уравнение, делимость на 3)

L-тетрамино:

Z-тетрамино:

Мигрирующие жуки

Задача: На каждой клетке доски 5 × 5 сидит жук. В некоторый момент времени все жуки взлетают и приземляются на соседние по стороне клетки. Докажите, что при этом обязательно окажется хотя бы одна пустая клетка?

Решение: Раскрасим доску шахматной раскраской.

 

Обходы

Задача 1. Фигура «верблюд» ходит по шахматной доске ходом типа (1, 3). Можно ли пройти ходом «верблюда» с произвольного поля на соседнее?

Решение: Ход верблюда, на которой он стоит, поэтому на соседнюю клетку перейти он не сможет.

 

Задача 2. Шахматный король обошёл всю доску 8*8, побывав на каждой клетке по одному разу, вернувшись последним ходом в исходную клетку. Докажите, что он сделал чётное число диагональных ходов.

Решение: При каждом недиагональном ходе меняется цвет поля, на котором стоит король; при диагональном — не меняется. Поскольку король обошёл всю доску и вернулся обратно, то цвет поля менялся с белого на чёрный столько же раз, сколько с чёрного на белый, значит недиагональных ходов король сделал чётное число. Число диагональных ходов равно 64 минус число недиагональных ходов — чётное число.

 

Задача 2.3: Замок имеет форму правильного треугольника, разделенного на 25 маленьких залов той же формы. В каждой стене между залами проделана дверь. Путник ходит по замку, не посещая более одного раза ни один из залов. Найти наибольшее число залов, которое ему удастся посетить.

Решение:

Ответ: 21 зал.

Доказательство максимальности: Раскрасим треугольник в шахматном порядке. Залов одного цвета (например чёрного) – 15, а другого цвета (белого) – 10. Заметим, что в чёрном зале путник может находиться с самого начала, или попасть в него из белого, поэтому он побывает не более, чем в 11 чёрных залах. Таким образом, не менее 4 чёрных залов останутся непосещёнными.

 

 

[s1]Хэхэй