Математика для гуманитариев: живые лекции

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

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

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

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

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

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

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

Что произойдет, где начались изменения? Только в нижних двух строках. Было 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):

Выпишем змейку до того, как подвинули 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). Изменятся ровно две пары.

Слушатель: То есть нечетное число поменяться не может.