Об инвариантах и энтропиях. Часть 1.

[ahiin]

С изрядной задержкой, рассказываю об обещанном едином методе решения задач о шахматной доске и размножающихся шашках. Впрочем, область его применения выходит далеко за рамки борьбы с головоломками

Comments

[papa_lyosha]

А в задаче о размножающихся шашках можно ли сделать пустыми угловую клетку и еще одну из двух стартовых? Я не придумал ни доказательства, что это нельзя, ни способа это сделать.

[ahiin]

Нет, нельзя. Но это следует из более тонкой теории, построенный инвариант слишком груб.
Можно показать, что задача нормализации (см. по ссылке) зацикливается.

[neyasyt]

Была ещё хорошая задачка, похожая на ту где углы отрезают. Вроде такая: есть доска 8 на 8 на ней уже как-то размещены горизонтально 15 доминошек, какое максимальное количество вертикальных доминошек можно ещё впихнуть на эту доску?