me.neoascetic

Puzzle. Математическая индукция на примере

В курсе Algorythms: Design and Analysis на Coursera (на который, к слову, забил, предпочев книжке Кормена) посоветовали Mathematics for Computer Science за авторством двух товарищей из Принстонского университета, дабы восполнить пробелы в необходимом математическом бэкграунде. Начал читать, весьма понравилась, в главе про доказательство с использованием математической индукции так понравился пример использования оной, что решил перевести и поделиться.

Итак, есть мозаика. Она состоит из пятнадцати пронумерованных ячеек и одной пустой, находящихся в сетке 4 на 4. Любая пронумерованная ячейка, соседствующая с пустой, может быть перемещена в сторону постой. К примеру, ниже изображены два последовательных хода:

 1   2   3   4       1   2   3   4       1   2   3   4
 5   6   7   8  →    5   6   7   8  →    5   6   7   8
 9  10  11  12       9  10  11  12       9  10      12
13  15  14          13  15      14      13  15  11  14

В самом левом состоянии мозаики выше ячейки 14 и 15 идут не по порядку. Сможете ли вы найти такую последовательность ходов, которые расставят все ячейки в нужном порядке? После нескольких экспериментов ответом, вероятно, будет “нет”. Но давайте попробуем это доказать.

Мы будем использовать подход, который часто используется при анализе программных продуктов и систем. Мы будем смотреть на инвариант, свойство мозаики, которое всегда остаётся истинным, вне зависимости от того, как вы двигаете ячейки. Если мы сможем показать, что перемена ячеек 14 и 15 местами нарушит инвариант, значит мы можем подытожить, что решение отсутствует.

Итак, приступим. Вот теорема, которую мы пытаемся доказать:

Теорема 1. Нет такой последовательности ходов, которые изменят мозаику из состояния, изображенного ниже слева в состояние, изображенное ниже справа.

 1   2   3   4      1   2   3   4
 5   6   7   8      5   6   7   8
 9  10  11  12      9  10  11  12
13  15  14         13  14  15

Мы будем выстраивать последовательность наблюдений в виде лемм. Как только будет достигнута критическая масса, мы объединим эти наблюдения непосредственно в доказательство.

Определим движение строки как движение, при котором ячейки перемещаются горизонтально, и движение столбца как движение, при котором ячейки перемещаются вертикально. Условимся, что ячейки читаются слева направо сверху вниз как обычный текст; то есть, когда мы говорим, что ячейки расставлены “не по порядку”, мы подразумеваем, что больший номер ячейки находится перед меньшим в заданном порядке.

Сложность в нашем случае в том, что одна пара ячеек (14 и 15) находится в неверном порядке изначально. Из этого сразу же можно сделать наблюдение, что простое движение строки не сильно помогает нам в нашем доказательстве, а именно:

Лемма 2. Движение строки не меняет порядок ячеек.

Обычно лемма требует доказательства. Тем не менее, в данном случае нет ничего более убедительного, чем непосредственно наблюдение, поэтому мы оставим это высказывание и двинемся дальше, к движениям столбцов.

Лемма 3. Движение столбца меняет относительный порядок ровно трех пар ячеек.

К примеру, движение столбца, изображённое ниже, меняет относительный порядок пар ячеек (j, g), (j, h) и (j, i).

a  b  c  d      a  b  c  d
e  f     g  →   e  f  j  g
h  i  j  k      h  i     k
l  m  n  o      l  m  n  o

Доказательство. Движение ячейки вниз смещает её относительно следующих трёх ячеек, идущих следом. Движение ячейки вверх смещает её относительно трёх ячеек, идущих перед ней. □

Эти наблюдения показывают, что существуют ограничение на то, как ячейки могут меняться местами. Некоторые такие ограничения могут привести нас к нужному нам инварианту. Чтобы рассуждать об обмене ячеек местами более точно, давайте сделаем определение: пара ячеек i и j инвертирована, если i < j, но при этом i находится после j в нашей мозаике. К примеру, в мозаике ниже есть четыре инвертированных ячейки: (12, 11), (13, 11), (15, 11) и (15, 14).

 1   2   3   4
 5   6   7   8
 9  10      12
13  15  11  14

Давайте рассмотрим эффекты движений строк и столбцов в терминах инверсии ячеек.

Лемма 4. Движение строки никогда не меняет чётность числа инверсий. Движение столбца всегда меняет четность числа инверсий.

“Чётность” числа говорит о том, является оно чётным либо нечётным. К примеру, числа 7 и -5 - нечётные, а 18 и 0 - чётные.

Доказательство. Согласно лемме 2, движение строки не меняет порядок ячеек; таким образом, в частности, движение строки не меняет числа инверсий.

Согласно лемме 3, движение столбца меняет относительный порядок ровно трёх пар ячеек. Таким образом, инвертированная пара становится не инвертированной и наоборот. Таким образом, один обмен меняет чётность общего числа инверсий на противоположную, второй меняет её в исходное значение, а третий - вновь на противоположную. □

Эта лемма подразумевает, что мы должны сделать нечётное количество движений столбцов с целью поменять только одну пару ячеек (например, 14 и 15). Но это проблематично, поскольку каждое движение столбца также двигает пустую ячейку вверх или вниз на одну строку. Потому после нечётного количества движений столбцов невозможна ситуация, когда пустая ячейка возвратилась бы в исходное положение в последней строке! Теперь мы можем связать все эти наблюдения и вывести инвариант, свойство мозаики, которое никогда не меняется, вне зависимости от того, как вы перемещаете ячейки.

Лемма 5. В каждом из состояний, достижимом из позиции, показанной ниже, чётность количества инверсий отличается от четности строки, содержащей пустую ячейку.

строка 1     1   2   3   4
строка 2     5   6   7   8
строка 3     9  10  11  12
строка 4    13  15  14

Доказательство. Используем индукцию. Пусть P(n) будет утверждением, что после n движений, чётность количества инверсий отличается от чётности строки, содержащей пустую ячейку.

База индукции: После нуля движений, ровно одна пара ячеек инвертирована (14 и 15), что является нечётным числом. Также, пустая ячейка находится в строке 4, что является чётным числом. Таким образом, P(0) истинно.

Шаг индукции: Теперь мы должны доказать, что из истинности P(n) следует истинность P(n + 1) для всех n ≥ 0. Итак, предположим, что P(n) истинно; таким образом, после n движений чётность количества инверсий отличается от чётности строки, содержащей пустую ячейку. Здесь мы имеем два случая:

  1. Допустим движение n + 1 является движением строки. Тогда чётность общего количества инверсий не меняется согласно лемме 2. Чётность строки, содержащей пустую ячейку, также не меняется, поскольку пустая ячейка остаётся в той же строке. Следовательно, эти две чётности также различаются после n + 1 шагов, потому P(n + 1) истинно.

  2. Допустим, движение n + 1 является движением столбца. Тогда чётность общего количества инверсий меняется согласно лемме 2. Однако, чётность строки, содержащей пустую ячейку, также меняется, поскольку пустая ячейка движется вверх или вниз на одну строку. Таким образом, чётности остаются различными и после n + 1 ходов, и потому P(n + 1) снова истинно.

Таким образом, из истинности P(n) следует P(n + 1) для всех n ≥ 0. По принципу индукции, P(n) истинно для всех n ≥ 0. □

Теорема. Нет такой последовательности перемещений ячеек, которые изменят мозаику из состояния, изображенного внизу слева в состояние, изображенное внизу справа.

 1   2   3   4      1   2   3   4
 5   6   7   8      5   6   7   8
 9  10  11  12      9  10  11  12
13  15  14         13  14  15

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