Олимпиадная задача про лабиринты на шахматной доске 8×8 для 8–10 классов

Решение 1:   Пусть всего лабиринтов N. Заметим, что только у  N₁ = ¾ N  лабиринтов поле a1 не отгорожено. Действительно, все лабиринты можно разбить на группы: в каждой группе собраны лабиринты, у которых все перегородки, кроме граничащих с a1, совпадают. Ясно, что в каждой группе ровно четыре лабиринта, причём в одном из них имеются перегородки как между a1 и a2, так и между a1 и b1, а в остальных трёх поле a1 доступно для ладьи (по крайней мере одна из двух указанных перегородок отсутствует). Аналогично покажем, что у  ¾ N₁ = (¾)² N  лабиринтов не отгорожено ни поле a1, ни поле a8. Продолжая эти рассуждения, получим, что количество лабиринтов, в которых не отгорожено ни одно из полей a1, a8, h1, равно  (¾)³ N < ^N/₂.  Тем более, количество хороших лабиринтов меньше  ^N/₂.

Решение 2:   Поставим сначала на доске все 112 перегородок. Чтобы получить хороший лабиринт, надо убрать как минимум 63 перегородки (вначале доска разделена на 64 части; надо объединить все эти части в одну, а при убирании одной перегородки количество частей уменьшается не больше, чем на 1: уменьшение происходит, если убирается перегородка, разделявшая две части). Значит, каждый хороший лабиринт содержит не более  112 – 63 = 49 перегородок.

  Назовём лабиринт B дополнительным к лабиринту A, если у B перегородки стоят на тех местах, где у A их нет, и наоборот. Разобьём все лабиринты на пары, каждая из которых состоит из двух дополнительных друг к другу лабиринтов. Ни в какой паре оба лабиринта не могут оказаться хорошими (иначе они в сумме содержали бы не более  49 + 49  перегородок, что меньше 112). В то же время, есть пары, где оба лабиринта плохие (к примеру, такие, где оба лабиринта содержат по 56 перегородок). Поэтому плохих лабиринтов больше.

Плохих лабиринтов больше.