Алексей Савватеев – Математика для гуманитариев. Живые лекции (страница 4)

Вернемся к нашим змейкам (формула (2))[5]. Первая из них соответствует измененной позиции, а вторая — исходной:

Для каждой пары чисел в каждой строке (а пар всего 105) мы спрашиваем, в правильном ли порядке написаны числа.

Слушатель: Частично да, частично нет.

А.С.: Верно. Например, 1 и 2 — в правильном порядке.

Слушатель: И последующая пара (2, 3) — тоже.

А.С.: Да, и следующая, и следующая за ней. То есть (4, 8).

Слушатель: В смысле «в правильном порядке»?

А.С.: «В правильном» не значит, что числа в паре соседние: и в (2, 3), и в (2, 7) — числа в паре расположены в правильном порядке.

Слушатель: По возрастанию.

А.С.: Да, по возрастанию. Большее следует за меньшим. Но, например, пара (15, 13) «нарушает порядок», потому что вначале идет большее число, потом меньшее.

Посчитаем количество пар, которые стоят в неправильном порядке. То есть по убыванию.

Слушатель: Простите, но ведь мы сами выбрали такую запись в виде извивающейся змеи. Мы разве не могли записать как-то иначе?

А.С.: Могли. Могли записать иначе, но тогда мы бы не преуспели в доказательстве того факта, который нам нужен.

Математика дает полную свободу исследователю. Когда он провел рассуждение и сказал: «Теперь всё доказано», — он оправдывает всё, что построил. Математик скажет: «Рассмотрим то-то и то-то». Зачем? Ужас, зачем, это рассматривать? А потом раз — и всё получилось (невзирая на «ужас»). Математика — самый свободный род занятий. Никакой моды, нет, ничего. Если вы, доказали недоказанную гипотезу, то чем бы вы ни пользовались, всё прощается. Победителей не судят (но иногда их слегка журят за сложноватое доказательство).

Итак, зачем я считаю пары, и почему так выписал змейку, пока не будет, понятно. Мы, договорились о некотором правиле. Мы, именно так выписываем числа. Вам придется принять это как есть. А дальше я считаю количество пар, которые стоят в неправильном порядке. Раз, два, три, четыре, пять, шесть… (см. рис. 14).

Рис. 14. Вылавливание неправильных пар в самом разгаре!

Условно разобьем наш ряд из 15 чисел на 4 группы в соответствии с номером строки. Рассмотрим для начала пару, элементы которой принадлежат разным группам. Ясно, что такая пара обязательно будет «правильной», так как любой элемент из группы слева меньше любого элемента из группы, стоящей правее: у нас группы от 1 до 4, от 5 до 8, от 9 до 12 и от 13 до 15. Значит, «неправильные» пары следует искать внутри групп. В первой и третьей группе всё хорошо, поэтому считать надо только оставшиеся две группы. Во второй группе 6 неправильных пар (8, 7; 8, 6; 8, 5; 7, 6; 7, 5; 6, 5). В четвертой группе чисел (для змейки, соответствующей измененной позиции) неправильных пар 2. Итого 8. А сколько неправильных пар в исходной позиции? (См. нижнюю строку на рис. 15 или в формуле (2) выше.)

Рис. 15. В верхней строке — восемь «беспорядков», а в нижней — девять.

Слушатель: 9.

А.С.: Да. 9. Мы находимся на подступах к пониманию. Сейчас я покажу, что никакие изменения пустого места не меняют четности, количества неправильных пар. Само количество, конечно, меняется. У нас оно пока равно 8, однако, если перемешать все фишки, согласно правилам игры «15», то количество неправильно стоящих пар изменится. Но удивительный факт состоит в том, что вы никогда не измените четности, этого количества. Само количество будет прыгать в сторону увеличения или уменьшения, но только на 2, на 4, на 6, словом, на ЧЕТНОЕ число единиц.

Начнем доказывать это утверждение. Где-то есть пустое место в коробке 4 x 4 (пусть конфигурация чисел, окружающих его, такая, как на рис. 16).

Рис. 16. И вот нашли пустое поле. Есть разгуляться где на воле!

Пустое место может сдвинуться в 4 направлениях (рис. 17).

Давайте рассмотрим все 4 варианта и посмотрим, что произойдет со змейкой.

Что происходит с выписанной змейкой чисел, если я передвигаю клетку с числом 11 налево?

Слушатели: Ничего.

А.С.: Правда. А что происходит со змейкой, если я передвигаю клеточку с числом 9 направо?

Рис. 17. Витязь на распутье. По какой же дороге мне пойти?..

Слушатели: Ничего.

А.С.: Ответ верный. Два других варианта немного более сложные, но совершенно однотипные.

Что происходит, когда клетка движется сверху вниз или снизу вверх?

Слушатель: У нас появляются неправильные пары.

А.С.: Да, у нас либо появляются, либо пропадают неправильные пары. Вопрос, сколько таких пар появляется и сколько пропадает? Ответ на этот вопрос зависит от того, где стояло пустое место. И вот здесь придется рассмотреть уже 4 варианта, но не для исходной стандартной змейки, а для любой. От самых простых в сторону самых сложных. Например, пусть в третьей строке получилось «9, 10, 11, пусто» (а номер 12 оказался в четвертой строке за счет каких-то предыдущих перемещений) (см. рис. 18).

Рис. 18. Следите только за третьей строкой.

Записываю фрагмент змейки:

… 8, 7, 6, 5, 9, 10, 11, пусто…

Нас интересует только этот фрагмент, потому что при движении, которое будет совершено, слева и справа в змейке ничего не изменится. Будет меняться только этот набор цифр. Расположение остальных пар не меняется. Внимание: «8» пошло вниз, пустышка — наверх (рис. 19).

Рис. 19. «Восмерка» и «пустышка» поменялись местами.

Как теперь будет выглядеть середина змейки? Вот так:

… пусто, 7, 6, 5, 9, 10, 11, 8…

Что произошло? Восьмерка из начала группы скакнула в конец. Какие пары свое значение поменяли? Группа из шести чисел (7, 6, 5, 9, 10, 11) целиком сохранилась. Она просто поменялась местами с восьмеркой. Значит, какие пары поменяли, как говорят математики, «свой тип монотонности», то есть возрастание сменилось убыванием (или, наоборот, убывание — возрастанием)?

Слушатель: (8, 7).

А.С.: (8, 7). Здесь теперь (7, 8); а еще?

Слушатель: (8, 6), (8, 5)…

А.С.: При том движении, которое я произвел, поменяют взаимное расположение чисел только те пары, в которых участвовало число 8. Поэтому 6 пар изменили тип монотонности. Если были возрастающими — стали убывающими, и наоборот.

Рассмотрим каждую пару в отдельности.

Было (8, 5) (числа в порядке убывания), стало (5, 8) — возрастание. Количество неправильных пар изменилось на единицу вниз. Было (8, 10), стало (10, 8), количество неправильных пар изменилось на единицу вверх. С остальными парами — то же самое. Каждый раз мы добавляем или вычитаем единицу. Не может быть, чтобы где-то (вместо плюс/минус единицы) получился нуль, так как среди указанных шести чисел нет восьмерок (ведь каждое число, написанное на фишке, единственно).

Вне зависимости от знаков, количество изменивших тип монотонности пар всегда четно. Имеется 64 способа расставить знаки, но в результате всегда в качестве суммы получится четное число. Соседние плюс/минус единички либо добавят к сумме 2, либо добавят (−2), либо взаимно уничтожатся, давая ноль:

±1 ± 1 ± 1 ± 1 ± 1 ± 1

В каждой паре соседних плюс/минус единичек получится или 0, или 2 или −2. То есть общее изменение количества «неправильных пар» может произойти на 6, 4, 0, −2, −4, −6.

Изменения происходят на четную величину, поэтому исходное количество «беспорядков» (оно было равно 8) могло стать числом 14, если все единички оказались бы с плюсом, могло остаться 8 (если бы было +1, +1, +1, −1, −1, −1). Могло стать 6, могло 4 или 2. Но никак не могло стать ни 5, ни 7.

В принципе, на этом месте я мог бы сказать «остальное проверьте сами», потому что в других случаях передвижения пустой фишки происходит ровно тот же самый эффект. Но давайте для аккуратности проверим что-нибудь еще. Например, вверх могло пойти число 14 (вместо того, чтобы опустить вниз число 8) (см. рис. 20).

Рис. 20. Еще один способ «освоения» пустого поля.

Что произойдет, где начались изменения? Только в нижних двух строках. Было 1, 2, 3, 4, 8, 7, 6, 5, а потом вместо 9, 10, 11, 14, 12, 15, 13 мы увидели 9, 10, 11, 14, 12, 15, 13. Ничего вообще не изменилось.

Давайте теперь представим себе внутреннюю пустую фишку. Скажем, если в позиции на рис. 18 клеточку 11 сдвинули к краю, а 7 сдвинули вниз (рис. 21):

Рис. 21. Семерка «переселилась» с 3-го этажа на 2-й.

Выпишем змейку до того, как подвинули 7:

1, 2, 3, 4, (8, 7, 6, 5, 9, 10, 11), 14, 12, 15, 13.

Теперь я двигаю 7 вниз и получаю вот такой фрагмент змейки:

1, 2, 3, 4, 8, 6, 5, 9, 10, 7, 11…

Выделяю в змейке группу, которая менялась.

Было: 1, 2, 3, 4, 8, (7, 6, 5, 9, 10), 11, 14, 12, 15, 13.

Стало: 1, 2, 3, 4, 8, (6, 5, 9, 10, 7), 11, 14, 12, 15, 13.

6, 5, 9, 10 переехали на шаг левее, а 7 через них перепрыгнула. Сколько будет изменений? Ровно 4. Пары опять поменялись. Правильные стали неправильными, и наоборот. Опять каждый раз мы прибавляем или отнимаем единицу. И так 4 раза. А 4 ведь — четное число, вот незадача. Опять результат меняется на четное число.

Что мы можем еще сделать? Мы могли вместо 7 подвинуть 12 (рис. 22). Тогда 12 прыгнет за пару (11, 14). Изменятся ровно две пары.