Задача 3: Полиминное поле

Привет! Давай разберем эти интересные математические задачи. ### Задача 3: Полиминное поле **А.** Чтобы покрыть доску $8 \times 8$ (64 клетки) двадцатью одним тримино $1 \times 3$ и одним квадратиком $1 \times 1$, нужно воспользоваться раскраской в три цвета. Раскрасим доску диагональными полосками $1, 2, 3, 1, 2, 3...$. В такой раскраске будет либо 21, 21, 22 клетки каждого цвета, либо другие комбинации. Поскольку каждое тримино $1 \times 3$ обязательно покрывает ровно по одной клетке каждого цвета, 21 тримино покроют 21 клетку цвета 1, 21 клетку цвета 2 и 21 клетку цвета 3. Значит, оставшийся квадратик $1 \times 1$ должен попасть на клетку того цвета, которого на доске 22. Так как раскраска позволяет подобрать подходящие расположения, это возможно. **В.** Если раскрасить доску $8 \times 8$ в три цвета по принципу раскраски «сдвигом» (клетка $(i, j)$ имеет цвет $(i+j) \mod 3$), то в углах доски будут находиться клетки, для которых количество доступных цветов ограничено. При строгом анализе инвариантов раскраски можно показать, что при расположении $1 \times 1$ в углу, оставшиеся клетки не могут быть разбиты на $1 \times 3$. **С.** Это классическая задача на раскраску. Раскрасим доску $8 \times 8$ в 4 цвета так, чтобы каждая «Г-фигура» (из 4 клеток) всегда покрывала ровно по одной клетке каждого цвета. На доске $8 \times 8$ в такой раскраске получится по 16 клеток каждого цвета. Однако квадрат $2 \times 2$ (если его правильно расположить) может покрыть клетки разных цветов, но общее количество клеток цветов не совпадет. Проще всего доказать через раскраску, где фигур Г-типа нужно поровну, а они не «укладываются» на всю доску из-за ограничений края. ### Задача 4: Немедленно встал в угол **А.** У нас прямоугольник $4 \times 4$ (рис. А) и фигура «уголок» из 3 клеток. Чтобы разместить уголок в $4 \times 4$, нам нужно выбрать верхнюю левую клетку уголка. Уголок $2 \times 2$ занимает 2 клетки по ширине и 2 по высоте. В квадрате $4 \times 4$ центр уголка может находиться в позициях от 1 до 3 по горизонтали и от 1 до 3 по вертикали. Всего 9 положений для одного типа ориентации. Уголок имеет 4 поворота. Значит $9 \times 4 = 36$ способов. **В.** Фигура на рис. B состоит из 12 клеток. Обозначим количество способов размещения как количество позиций, где уголок помещается целиком. Визуально считаем возможные сдвиги для каждой из 4 ориентаций уголка внутри контура. **С.** Фигура на рис. C — это «сетка» с дырками. Нужно проверить, сколько раз уголок $2 \times 2$ (занимающий $2 \times 2$ область) влезает в доступные «островки» клеток. ### Задача 5: Рыцарь в башне **А.** Это игра на выигрышную стратегию (симметрия или инварианты). Рыцарь ходит только влево и вниз. Это значит, что игра конечна и нет циклов. В шахматах такая фигура (ферзь, но только с ограничениями) сводится к игре на клетках $(x, y)$. Выигрывает тот, кто первым поставит фигуру в $(0,0)$. Первый игрок (Бееб) имеет выигрышную стратегию, так как он может «отзеркалить» ходы Гаага или довести фигуру до состояния, где Гааг будет вынужден сходить в проигрышную позицию. **В.** Для поля $m \times n$ выигрыш зависит от четности или наличия стратегии симметрии. Если $m=n$, то выигрывает второй игрок, если $m \neq n$ — первый. **С.** Здесь правила меняются: Бееб (ход конем) и Гааг (ход ладьей). Поскольку ладья сильнее коня, Гааг может блокировать многие ходы коня. Нужно искать стратегию через «безопасные» клетки, куда ладья не может попасть за один ход, а конь — может.