Математики любят символы. Но зачем они? Затем, что иначе придется очень много писать. Символы и язык математики нужны, чтобы сокращать запись. Почему древние греки и римляне не до­шли до современных высот математики? Потому, что они тратили очень много времени на лингвистическую работу перевода мате­матики в слова (и обратно: слов в математику). А вот когда ма­тематика перешла на символы, начался прорыв, о котором я еще расскажу.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вы, доказали недоказанную гипотезу, то чем бы вы ни пользо­вались, всё прощается. Победителей не судят (но иногда их слегка журят за сложноватое доказательство).

Итак, зачем я считаю пары, и почему так выписал змейку, пока не будет, понятно. Мы, договорились о некотором правиле. Мы, именно так выписываем числа. Вам придется принять это как есть. А дальше я считаю количество пар, которые стоят в неправильном порядке. Раз, два, три, четыре, пять, шесть... (см,, рис. 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) выше.)

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

А.С.: Да. 9. Мы находимся на подступах к пониманию. Сейчас я покажу, что никакие изменения пустого места не меняют чет­ности, количества неправильных пар. Само количество, конечно.

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

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

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

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

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

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

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

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

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

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

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

А.С.: Да. у нас либо появляются, либо пропадают неправиль­ные пары. Вопрос, сколько таких пар появляется и сколько про­падает? Ответ на этот вопрос зависит от того, где стояло пу­стое место. И вот здесь придется рассмотреть уже 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). Изменятся ровно две пары.

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

А.С.: Ни при каких условиях. Мы уже знаем, что движение по горизонтали — бессмысленно. Получится та же самая змей­ка. Если мы движемся сверху вниз, то количество неправильных пар меняется либо на 2, либо на 4, либо на 6, либо ничего не ме­няется. Можно честно перебрать все возможные переходы снизу вверх. Можно просто понять, что никаких других вариантов, кро­ме четных, нет. То есть в пятнашку выиграть нельзя, потому что в стандартной исходной позиции количество неправильных пар 8, и изменить его можно только на четное число. А в требуемой по­зиции имеется 9 неправильных пар.

Слушатель: Из любой ли позиции выиграть невозможно?

А.С.: Почему? На самом деле из половины всех исходных пози­ций. Из половины невозможно, из половины возможно. Потому что в «высокой» математике учат, что половина последовательностей имеет четное число неправильных пар, а половина — нечетное4. Поэтому половина вариантов будет собираться в стандартную ис­ходную позицию. Если пятнашки как угодно перемешать, вывалив из коробки и затем вставив обратно как придется, то перестанов­кой фишек всегда можно прийти либо к случаю «13, 14, 15», либо к случаю «13, 15, 14».

Чтобы понять, можно ли привести фишки в исходную позицию, нужно посчитать количество неправильных пар в змейке, соответ­ствующей изучаемой исходной позиции. Если оно нечетное — при­вести к исходной позиции можно. Если четное — то нельзя.

Слушатель: Какие числа можно поменять местами?

Другой слушатель: Например, 1 и 3 можно поменять?

А.С.: Если я меняю 1 и 3 местами (было 1, 2, 3, — стало 3, 2, 1), то как изменилась четность? Было отсутствие беспорядков (то есть 0), стало три беспорядка. Четность, стало быть, изменилась. Так что поменять в игре «пятнадцать» 1 и 3 местами, сохраняя остальные фишки на своих местах, тоже невозможно. Ваши вопро­сы относятся к теории групп, основе современной алгебры. Что и как можно поменять, чтобы четность менялась — этот вопрос напрямую к теории групп5. Почему ровно половина позиций име­ет четное количество беспорядков? Это тоже связано с некоторым фактом из теории групп. Сейчас я продолжу развивать эту тему. Рассмотрим «кубик Рубика». Венгерский инженер Рубик достойно продолжил дело, начатое Сэмом Лойдом.

Давайте разберем этот кубик и соберем его обратно.

Слушатель: По-моему, есть даже какие-то соревнования на этот счет.

А.С.: На соревнованиях надо собрать тот, который теоретиче­ски возможно собрать. Под словом «разобрать» я понимаю более радикальную операцию: «разодрать».

Как только мне купили кубик Рубика, я сразу его разодрал. Потому что мне было интересно, любую ли позицию можно при­вести к исходной. Мне было это настолько долго интересно, что на мехмате МГУ я решил соответствующую задачку в качестве зачета. Возможно (если мне не изменяет память) 12 разных рас­положений, не переводящихся друг в друга. В пятнашках — 2, а для кубика Рубика — 12 ситуаций. Это тоже следует из теории групп (по которой я и сдавал зачет).

Если перевернуть угловой кубик в кубике Рубика путем прину­дительного «раздирания» и восстановления его формы — его не­льзя будет собрать. Если перевернуть центральный кубичек в ре­бре — тоже нельзя. Если поменять местами два кубика малой «диагонали» любой грани — опять не получится. Эти изменения и все их сочетания задают набор различных позиций кубика Ру­бика, которые нельзя собрать. Однако это — трудная задача.

А теперь поговорим про мяч (рис. 3). То есть, как ни странно, снова про математику.