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