Об инвариантах и энтропиях. Часть 1.
С изрядной задержкой, рассказываю об обещанном едином методе решения задач о шахматной доске и размножающихся шашках. Впрочем, область его применения выходит далеко за рамки борьбы с головоломками.
Начнем с задачки попроще.
Напомню условие: из шахматной доски 8x8 вырезаются две угловые, диагонально противоположные клетки (a-1 и h-8). Можно ли замостить оставшуюся "усеченную" шахматную доску прямоугольниками размером 2x1?
Давайте взглянем на шахматную доску поближе.
Понятно, что всякий прямоугольник 2х1 будет накрывать одну черную и одну белую клетки. И не важно, вертикально ориентирована наша "доминошка", или горизонтально. На этом месте становится очевидно: для того, чтобы фигуру, полученную вырезанием некоторого набора клеток, можно было замостить доминошками, совершенно необходимо, чтобы число оставшихся в фигуре черных клеток было равно числу оставшихся белых клеток. Однако обе клетки из условия задачи (a-1 и h-8) - черные. Поэтому замостить такую фигуру невозможно.
Равенство количества черных и белых клеток на вырезанной из шахматной доски фигуре, как необходимое (но, разумеется, недостаточное) условие успешного замощения, является простейшим примером так называемого инварианта.
Желающие поглубже (гора-ааздо поглубже) разобраться в математике замощений приглашаются сюда.
А мы теперь построим инвариант посложнее, для задачи с шашками.
Напомню условие:
На шахматной доске, бесконечно простирающейся вправо и вверх (то есть, заполняющей собой первый квадрант), в левом нижнем углу стоят три шашки в позиции, показанной на рисунке.
На каждом ходу выбирается одна из шашек, убирается с доски, а в соседнюю клетку справа и в соседнюю клетку сверху ставится по новой шашке. Ход возможен только в том случае если обе соседние клетки (и справа, и сверху) свободны.
Необходимо указать последовательность ходов, в результате которой все три стартовые клетки (на рисунках выше они обведены жирной линией) окажутся пустыми. Или показать, что это невозможно.
Занумеруем строки и столбцы доски целыми числами от нуля до бесконечности. И теперь пусть шашка, находящаяся в i-й строке и j-м столбце имеет вес
Очевидно,
Получается, что вес шашки, выбранной для хода, делится пополам между двумя ее потомками. Это, в свою очередь, означает, что суммарный вес "популяции" шашек на каждом ходу остается неизменным.
Этот самый суммарный вес и будет интересующим нас инвариантом.
Вес изначальной популяции 1+1/2+1/2=2. Очевидно, что если последовательность ходов, освобождающая три стартовые клетки, существует, то итоговый суммарный вес шашек за пределами стартового угла должен по прежнему равняться двум.
Однако, это невозможно.
Давайте представим, что доска полностью покрыта шашками. Дважды, последовательно, сначала для одной строки, а затем складывая суммы строк, применим формулу суммы бесконечной убывающей геометрической прогрессии (известную еще со школы). Получим, что суммарный вес полностью покрытой шашками доски равен 4.
Значит, даже если поставить в каждую клетку доски по шашке, суммарный вес шашек за пределами стартового угла равен двум. Ровно столько же, сколько весит начальная "популяция" из трех шашек. Собственно, уже видно, что решения нет. Совершая ходы по вышеописанным правилам, заполнить шашками всю внешнюю область за конечное число ходов в принципе невозможно.
Вообще-то, несложно заметить, что и за бесконечное число ходов задачка явно не решается. Обратите внимание, что в нулевой вертикали, а равно и в нулевой горизонтали, на каждом ходу будет ровно по две шашки. А значит, вес "внешней популяции" заведомо меньше двух.
Таким образом, задача очистки стартового угла от шашек решения не имеет.
Приятно, что в этот раз я имею возможность назвать вам автора этой замечательной задачи. Это Максим Концевич, выдающийся математик, филдсовский лауреат и прочая, и прочая, и прочая.
Задачка была впервые опубликована в журнале Квант, когда Максиму Львовичу было 16 лет.
Подробнейший разбор решения был опубликован в Кванте на следующий год. Настоятельно рекомендую ознакомиться.
Вернемся, однако, к инвариантам. Может сложиться впечатление, что они пригодны лишь для негативных утверждений: нет, не существует, невозможно. Это совсем не так. В следующий раз мы рассмотрим примеры инвариантов, известные, кстати, всем нам еще со школы, которые позволяют не просто делать некие качественные утверждения, но и вполне себе получать полезную количественную информацию.
Продолжение следует.
Начнем с задачки попроще.
Напомню условие: из шахматной доски 8x8 вырезаются две угловые, диагонально противоположные клетки (a-1 и h-8). Можно ли замостить оставшуюся "усеченную" шахматную доску прямоугольниками размером 2x1?
Давайте взглянем на шахматную доску поближе.
Понятно, что всякий прямоугольник 2х1 будет накрывать одну черную и одну белую клетки. И не важно, вертикально ориентирована наша "доминошка", или горизонтально. На этом месте становится очевидно: для того, чтобы фигуру, полученную вырезанием некоторого набора клеток, можно было замостить доминошками, совершенно необходимо, чтобы число оставшихся в фигуре черных клеток было равно числу оставшихся белых клеток. Однако обе клетки из условия задачи (a-1 и h-8) - черные. Поэтому замостить такую фигуру невозможно.
Равенство количества черных и белых клеток на вырезанной из шахматной доски фигуре, как необходимое (но, разумеется, недостаточное) условие успешного замощения, является простейшим примером так называемого инварианта.
Желающие поглубже (гора-ааздо поглубже) разобраться в математике замощений приглашаются сюда.
А мы теперь построим инвариант посложнее, для задачи с шашками.
Напомню условие:
На шахматной доске, бесконечно простирающейся вправо и вверх (то есть, заполняющей собой первый квадрант), в левом нижнем углу стоят три шашки в позиции, показанной на рисунке.
На каждом ходу выбирается одна из шашек, убирается с доски, а в соседнюю клетку справа и в соседнюю клетку сверху ставится по новой шашке. Ход возможен только в том случае если обе соседние клетки (и справа, и сверху) свободны.
Необходимо указать последовательность ходов, в результате которой все три стартовые клетки (на рисунках выше они обведены жирной линией) окажутся пустыми. Или показать, что это невозможно.
Занумеруем строки и столбцы доски целыми числами от нуля до бесконечности. И теперь пусть шашка, находящаяся в i-й строке и j-м столбце имеет вес
Очевидно,
Получается, что вес шашки, выбранной для хода, делится пополам между двумя ее потомками. Это, в свою очередь, означает, что суммарный вес "популяции" шашек на каждом ходу остается неизменным.
Этот самый суммарный вес и будет интересующим нас инвариантом.
Вес изначальной популяции 1+1/2+1/2=2. Очевидно, что если последовательность ходов, освобождающая три стартовые клетки, существует, то итоговый суммарный вес шашек за пределами стартового угла должен по прежнему равняться двум.
Однако, это невозможно.
Давайте представим, что доска полностью покрыта шашками. Дважды, последовательно, сначала для одной строки, а затем складывая суммы строк, применим формулу суммы бесконечной убывающей геометрической прогрессии (известную еще со школы). Получим, что суммарный вес полностью покрытой шашками доски равен 4.
Значит, даже если поставить в каждую клетку доски по шашке, суммарный вес шашек за пределами стартового угла равен двум. Ровно столько же, сколько весит начальная "популяция" из трех шашек. Собственно, уже видно, что решения нет. Совершая ходы по вышеописанным правилам, заполнить шашками всю внешнюю область за конечное число ходов в принципе невозможно.
Вообще-то, несложно заметить, что и за бесконечное число ходов задачка явно не решается. Обратите внимание, что в нулевой вертикали, а равно и в нулевой горизонтали, на каждом ходу будет ровно по две шашки. А значит, вес "внешней популяции" заведомо меньше двух.
Таким образом, задача очистки стартового угла от шашек решения не имеет.
Приятно, что в этот раз я имею возможность назвать вам автора этой замечательной задачи. Это Максим Концевич, выдающийся математик, филдсовский лауреат и прочая, и прочая, и прочая.
Задачка была впервые опубликована в журнале Квант, когда Максиму Львовичу было 16 лет.
Подробнейший разбор решения был опубликован в Кванте на следующий год. Настоятельно рекомендую ознакомиться.
Вернемся, однако, к инвариантам. Может сложиться впечатление, что они пригодны лишь для негативных утверждений: нет, не существует, невозможно. Это совсем не так. В следующий раз мы рассмотрим примеры инвариантов, известные, кстати, всем нам еще со школы, которые позволяют не просто делать некие качественные утверждения, но и вполне себе получать полезную количественную информацию.
Продолжение следует.