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

Переходим к более сложному сюжету — «разоблачению игры в пятнадцать».

Сейчас вы узнаете тайну, которую почти никто не знает: почему в пятнашки нельзя «выиграть», то есть перевести игру из позиции на рис. 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>} ^