October 27th, 2014

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

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

Начнем с задачки попроще.
Напомню условие: из шахматной доски 8x8 вырезаются две угловые, диагонально противоположные клетки (a-1 и h-8). Можно ли замостить оставшуюся "усеченную" шахматную доску прямоугольниками размером 2x1?

Давайте взглянем на шахматную доску поближе.

Шахматная доска

Понятно, что всякий прямоугольник 2х1 будет накрывать одну черную и одну белую клетки. И не важно, вертикально ориентирована наша "доминошка", или горизонтально. На этом месте становится очевидно: для того, чтобы фигуру, полученную вырезанием некоторого набора клеток, можно было замостить доминошками, совершенно необходимо, чтобы число оставшихся в фигуре черных клеток было равно числу оставшихся белых клеток. Однако обе клетки из условия задачи (a-1 и h-8) — черные. Поэтому замостить такую фигуру невозможно.

Равенство количества черных и белых клеток на вырезанной из шахматной доски фигуре, как необходимое (но, разумеется, недостаточное) условие успешного замощения, является простейшим примером так называемого инварианта.
Collapse )