|
|
 |
Условие
Назовём лабиринтом шахматную доску 8×8, где между некоторыми полями вставлены перегородки. Если ладья может обойти все поля, не перепрыгивая через перегородки, то лабиринт называется хорошим, иначе – плохим. Каких лабиринтов больше – хороших или плохих?
Решение 1
Пусть всего лабиринтов N. Заметим, что только у N1 = ¾ N лабиринтов поле a1 не отгорожено. Действительно, все лабиринты можно разбить на группы: в каждой группе собраны лабиринты, у которых все перегородки, кроме граничащих с a1, совпадают. Ясно, что в каждой группе ровно четыре лабиринта, причём в одном из них имеются перегородки как между a1 и a2, так и между a1 и b1, а в остальных трёх поле a1 доступно для ладьи (по крайней мере одна из двух указанных перегородок отсутствует). Аналогично покажем, что у ¾ N1 = (¾)² N лабиринтов не отгорожено ни поле a1, ни поле a8. Продолжая эти рассуждения, получим, что количество лабиринтов, в которых не отгорожено ни одно из полей a1, a8, h1, равно (¾)³ N < N/2. Тем более, количество хороших лабиринтов меньше N/2.
Решение 2
Поставим сначала на доске все 112 перегородок. Чтобы получить хороший лабиринт, надо убрать как минимум 63 перегородки (вначале доска разделена на 64 части; надо объединить все эти части в одну, а при убирании одной перегородки количество частей уменьшается не больше, чем на 1: уменьшение происходит, если убирается перегородка, разделявшая две части). Значит, каждый хороший лабиринт содержит не более 112 – 63 = 49 перегородок.
Назовём лабиринт B дополнительным к лабиринту A, если у B перегородки стоят на тех местах, где у A их нет, и наоборот. Разобьём все лабиринты на пары, каждая из которых состоит из двух дополнительных друг к другу лабиринтов. Ни в какой паре оба лабиринта не могут оказаться хорошими (иначе они в сумме содержали бы не более 49 + 49 перегородок, что меньше 112). В то же время, есть пары, где оба лабиринта плохие (к примеру, такие, где оба лабиринта содержат по 56 перегородок). Поэтому плохих лабиринтов больше.
Ответ
Плохих лабиринтов больше.
Замечания
6 баллов
