Дальше кладем третью, четвертую и так далее. И каждый раз домножаем и домножаемколичество вариантов очень быстро растет. (Показывает на доске всё новые варианты.)
Есть миф, будто математика состоит из формул. В 1993 году, когда я учился на 3-м курсе мехмата, я ехал на Урал к тете. Со мной в купе ехала мама с маленькой 4-летней дочкой. И дочка говорит: «Мам,а, а можно почит,ат,ъ дядину книгу?» Книга м,оя называлась «Алгебра». Мама сказала: «Ты в ней ничего не поймешь, там одни формулы». Я передаю книгу и говорю: «Найдите первую формулу. На какой она странице?» Формул в книге по алгебре не очень много, и самое страшное не в их количестве, а в том, что они ужасающие, в них одни буквы, даже цифр почти нет. Это, скорее, похоже на какой-т,о древний язык. Совершенно не то в книге, что должно быть с точки зрения людей. Идея, что математика состоит из формул, столь же чудовищна, как мысль, что в храм люди заходят, чтобы просто совершить обряд, поставить свечку. Моя дочь говорит, например: «Пойдем,, поставим огоньки». Для нее это нормально, она маленькая. Математикаэто вселенная, в которой есть язык формул. Но суть не в нём, а в том, какие глубинные законы есть в математике. И вот эти законы, эту внутреннюю красоту я постараюсь вскрыть.
После такого философского отступления вернемся к нашей доске.
Произведение, которое получится уже через 20 умножений, имеет порядок количества атомов во вселенной (как любят говорить в научно-популярных книгах). Вот с чем сравнимо количество способов, которые нужно перебрать, чтобы заявить: «Мы перебрали все варианты, задачу решить нельзя». Надо придумать что-то другое. И то, что мы сейчас придумаем это абсолютное доказательство.
Может быть, у кого-то есть идеи?
Слушатель: Взять площадь каждой фишки и разделить на нее общую площадь поля.
А.С.: Ничего не выйдет. Общая площадь 62, у каждой фишки 2, значит нужна 31 доминошка, это мы понимаем. Но 30 умещается, а 31 нет (рис. 6).
Последняя доминошка распадается на два квадратика в разных местах. И что бы вы ни делали, последняя будет, как заколдованная, распадаться на два квадратика.
Теперь я доказываю, что замостить доску доминошками невозможно.
Ведь перед нами, по сути, шахматная доска. Давайте вернем ей ее шахматный вид. Клетки на ней будут то черные, то белые (рис. 7).
После вырезания двух угловых квадратиков, сколько черных и сколько белых клеточек останется?
Слушатель: Одних будет больше, других меньше.
Слушатель: Одна доминошка должна покрывать и белую, и черную, да?
А.С.: Кто-то уже всё понимает (см. рис. 8). Любая доминошка, уложенная на эту доску, покрывает и белую, и черную клет-
ку. Поэтому, если бы фигуру, которую я сейчас нарисовал, можно было бы заложить доминошками, черных и белых клеток было бы одинаковое количество. Но мы вырезали две белых. Осталось 30 белых и 32 черные клетки. Противоречие. Количества черных и белых клеток не равны друг другу. Значит, нашу фигуру нельзя замостить доминошками. Абсолютное доказательство закончено. Не надо ничего перебирать.
Повторю еще раз.
Я взял урезанную с двух сторон шахматную доску. Исходная шахматная доска имела 32 черные и 32 белые клетки. А в урезанной шахматной доске пропали две белые угловые клетки. Поэтому стало 30 белых и 32 черных. Теперь предположим на секундочку, что мы решили задачу, и все клетки заполнены доминошками. Следует заметить, что каждая доминошка обязана лежать одной своей половиной на черной, а другой своей половиной на белой клеточке, как ты ее ни клади. Следовательно, если бы мы смогли замостить эту фигуру доминошками в количестве 31 штуки, то была бы 31 черная и 31 белая клетка. У нас же 32 черные и 30 белых клеток. А значит, замостить обрезанную доску нельзя. В этом и состоит препятствие, как говорят математики, препятствие к решению задачи. Заметьте, что мы проводили доказательство от, противного. Это очень важный прием. Я предположил, что мы задачу решили, и привел ситуацию к явному противоречию.
Переходим к более сложному сюжету«разоблачению игры в пятнадцать».
Сейчас вы узнаете тайну, которую почти никто не знает: почему в пятнашки нельзя «выиграть», то есть перевести игру из позиции на рис. 2 в исходную позицию на рис. 1. Посмотрим на измененную позицию:
Глядя на рис. 9, выпишу числа от 1 до 15 в линеечку, но не подряд, а хитрым способом. Зачем я это сделаю, будет ясно потом. Вот они:
1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 14, 15, 13.
Такой порядок движения древние греки называли «бустрофедон», что в переводе значит «так, как пашет бык» (рис. 10).
С помощью такого движения я закодировал информацию об игровом поле в виде одной строки. Обратно раскодировать так же просто, как и закодировать (с :точностью до нахождения пустого места).
Если, например, сдвинуть 14 в угол, то при кодировании я получу такую же строчку (см. рис. 11). Вообще, легко понять, что правила игры «15» позволяют быстро и уверенно перегнать пустое место на игровом поле на любую клетку из шестнадцати, двигаясь бустрофедоном.
Примечание. Кодированием называется процедура изображения элементов одного множества с помощью элементов другого (обычно более простого) множества, желательно таким образом, чтобы не потерялась никакая существенная часть информации
о первом множестве.
При этом если пустое место находилось где-то в другом месте, в середине, например, то всегда можно передвинуть фишки так, чтобы оно оказалось в конце.
Теперь мы, начиная с положения рис. 9, должны каким-то образом менять это положение, гонять пустое место, чтобы прийти к последовательности, соответствующей рис. 1:
1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 15, 14, 13.
Каждый раз, когда я переставляю пустое место, наша строка меняется. Я хочу показать, что как бы она ни менялась, кое-что сохраняется. В математике это называется словом инвариант.
Инвариантчто-то, что не меняется.
Понятие инвариантаодно из ключевых математических понятий.
Итак, есть что-то, что связано с нашей последовательностью, что при выполнении разрешенных действий не будет меняться. Что это, угадать так просто нельзя, иначе миллионы людей в Америке и в Европе не занимались бы ерундой.
В процессе перестановок строка будет сильно меняться, вплоть до очень серьезного перемешивания. Но что-то меняться не будет никогда. Давайте напряжемся и поймем, что это такое.
Рассмотрим все пары чисел (чисел всего 15). Сколько всего можно составить пар?
Слушатель: 7.
А.С.: Нет. Всех различных пар. Пусть у нас есть 15 кружочков разного цвета. Сколько существует способов вынуть два кружка?
Пока будем считать, что порядок, в котором мы вынимаем кружочки, нам важен. Сколькими способами я могу взять первый кружок?
Слушатель: Пятнадцатью.
А.С.: Пятнадцатью. Правильно.
Слушатель: 15 факториал?
А.С.: Нет. 15 факториалэто множество всех возможных строк.
Но водь гуманитарии но обязаны знать слово «факториал», о котором мы с вами говорим. Термин «факториал» нам понадобится в других томах, поэтому я ого определю.
Есть некоторое число п. Простите, я употреблю буковку. Умножим п на п1, потом на п^2 и так далее, и. наконец, умножим на 2 и на 1. То. что получилось, обозначается п! (это и есть факториал числа п):
п! = п · (п 1) · (п 2) · ... · 2 · 1.
Например. «15 факториал»:
15! = 15-14-13-12-11-...-2-1.
Слушатель: Мы сейчас что-то прояснили?
А.С.: Нет. Было произнесено слово «факториал». И теперь я его объясняю.
Факториал это произведение подряд идущих, убывающих до единицы натуральных чисел. В нашей задаче он не понадобится (понадобится в другой лекции).
Первый кружок вы можете выбрать 15 разными способами. Сколько остается способов для выбора второго кружка?
Слушатели: 14.
А.С.: 14. Итого? Есть такое знаменитое правило произведения. Число способов выбрать пару это произведение количества способов выбрать первый ее элемент на количество способов выбрать второй. Почему? Мы выбрали первый. Посмотрим, сколько пар мы с ним можем получить. Второй выбирается 14 способами, значит пар 14. А теперь мы выбрали другой первый, с ним тоже можно составить 14 пар. И так далее. Получается 14 + 14 + 14... и так
раз.
Отсюда и берется правило произведения: 15 · 14 способов.
Но есть одна хитрость. Я хочу посчитать пары независимо от порядка кружочков. Чтобы вот такие пары (см. рис. 13) не различались. Что надо сделать с количеством способов?
Слушатель: Разделить на два.
А.С.: Да. Мы любую такую пару посчитали два раза. Один раз. когда мы сначала взяли синий круг, а потом белый. В другой раз мы первым взяли белый круг, а вторым синий. То есть мы каждую пару посчитали два раза. Поэтому ответ (15 · 14) : 2 = 105.
Мы посчитали число имеющихся пар из 15 элементов «Цэ из 15 по 2». как говорят математики. «Цэ» означает первую букву слова combination (комбинация). См. формулу (1).
С2_ = 15_14 = 105> ^
Математики любят символы. Но зачем они? Затем, что иначе придется очень много писать. Символы и язык математики нужны, чтобы сокращать запись. Почему древние греки и римляне не дошли до современных высот математики? Потому, что они тратили очень много времени на лингвистическую работу перевода математики в слова (и обратно: слов в математику). А вот когда математика перешла на символы, начался прорыв, о котором я еще расскажу.
Вернемся к нашим змейкам (формула (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.