Алексей Владимирович Савватеев - Математика для гуманитариев: живые лекции

сейчас нарисовал, можно было бы заложить доминошками, черных и белых клеток было бы одинаковое количество. Но мы вырезали две белых. Осталось 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).

--">