Сложный вариант весеннего тура Турнира Городов

Первое решение. Пусть — количество всех лабиринтов. Давайте рассмотрим плохие лабиринты, в которых огорожена какая-нибудь угловая клетка. Заметим, что таких плохих лабиринтов ровно В силу того, что нам нужно поставить две перегородки. Следовательно, хороших, в которых не огорожена эта угловая клетка точно меньше, чем Аналогично количество хороших лабиринтов, у которых не огорожено две угловых клетки точно меньше, чем а у которых не огорожено три угловых клетки точно меньше, чем Следовательно, хороших точно меньше половины, а значит, плохих больше.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Давайте думать о клетках, как о вершинах графа. Ребра будут общими сторонами, а если есть перегородка, то ребро убираем. Хорошим лабиринтам соответствует связный граф. Заметим, что в связном графе на вершинах должно быть хотя бы ребра. А значит, хороший лабиринт содержит не более перегородок. Давайте рассмотрим какой-нибудь лабиринт и определим для него инвертированный лабиринт, то есть в нашем графе мы убираем ребра и добавляем ребра, которых не было. Тогда мы получаем соответствие лабиринтов с перегородками лабиринтам с перегородками. То есть каждому хорошему лабиринту мы точно сопоставили плохой. А у нас точно еще есть плохие лабиринты, поэтому плохих лабиринтов точно больше.