Итак, с помощью математики мы одну задачу заменили другой, а именно, если мы докажем, что с помощью перекидывания чисел вот в такой строке, только через четное количество других чисел, невозможно отсюда перейти сюда, то мы докажем всё, что надо, потому что игра в «Пятнадцать» передвигание фишек на вот этой последовательности отражается как перекидывание некоторых чисел через четное количество других. Что же такое здесь может сохраняться, что разное здесь и здесь и что не меняется при таких операциях? Что может сохраняться, что это такое? В математике есть понятие четности перестановки. Сейчас мы ее введем и объясним, что она означает. Четность перестановки. Но прежде всего, что такое перестановка? Перестановка — это любая вот такая вот строка из данного количества символов вот мы, например, работаем с 15 разными числами, первыми 15 числами натурального ряда. Перестановкой называется просто любая строка, в которой они перечисляются подряд без повторений все. То есть любая строка длины 15, содержащая различные числа от 1 до 15, называется перестановкой. И у перестановки есть такая замечательная характеристика, которая называется четность. Что же это такое? Это вот что такое. Нужно посчитать прежде всего количество пар чисел, стоящих в неправильном порядке. То есть таких, как вот здесь, например, 7, 6. Пара 7, 6 стоит в неправильном порядке. Почему в неправильном? Потому что 7 больше 6, а стоит раньше. Например, вот эта пара 3, 7 она стоит в правильном порядке. 3 меньше 7 и стоит раньше. Вот эта пара 5, 13 тоже стоит в правильном порядке. Пара 5, 3 — в неправильном порядке, то есть вот это вот правильная пара, а это — неправильная. И требуется немного воображения, чтобы понять, что пар здесь очень много, потому что каждое конкретное число может быть спарено со всеми остальными. То есть получается, что пятерка входит в 14 разных пар. И мы про каждую из этих пар должны спросить, она в правильном порядке или в неправильном порядке? Ну-ка, вот эта пара в правильном, вот эта в неправильном, считаем, первая в неправильном порядке. Дальше, какие еще здесь будут в неправильном порядке? пятерка будет в неправильном порядке только в паре с тройкой, четверкой единицей и двойкой. Потому что она стоит здесь первая, а все они после нее. Шестерка, семерка и прочие стоят тоже после пятерки, но они больше нее, поэтому соответствующие пары упорядочены правильно. Итого пятерка нам даст четыре пары в неправильном порядке: 5, 3; 5, 4; 5, 1 и 5, 2. Переходим к 13. Пару 5, 13 мы уже учли. В паре неважен порядок, речь идет о неупорядоченных парах, как говорят математики, то есть просто вот мы перебираем все комбинации чисел по два. Если мы вот эту пару уже учли, то 13 участвует еще в скольких? Еще в 13 парах, а именно ее можно спарить со всеми, которые идут дальше нее. Поэтому если мы, например, посчитаем одновременно количество вообще всех пар, то у пятерки 14 пар, у следующего числа 13 пар, у следующего числа все пары, которые идут с более ранними числами, уже учтены, поэтому новых появляется еще 12. Ну и получается вот такая сумма, если ее посчитать, ее очень легко посчитать, например, маленький Гаусс умел считать такие суммы, ну и мы с вами в дальнейшем тоже научимся. Можно не суммировать всё подряд, там есть один фокус. Такая сумма будет равна 14 умножить на 15 пополам. Но даже если вы этого не знаете, вы можете просто сложить, получится 105. И вот для каждой пары из этих 105 имеющихся пар нужно спросить, в правильном или неправильном она порядке идет. И сложить каждый раз вот эти вот количества неправильных пар. С пятеркой у нас четыре неправильных пары, с 13 у нас довольно много неправильных пар, мы тоже можем это сейчас понять. Ну давайте поймем это про 13, а дальше понятно, что надо делать, я уже не буду это выписывать, это каждый слушатель может сделать сам. Сколько неправильных пар будет с числом 13? Всего у числа 13-- Да, но у нас уже вот одна пара правильная, значит, остается 13 различных пар, и правильными будут только две, а именно 13, 14 и 13, 15. Все остальные будут неправильными, потому что в них 13 идет раньше. Из оставшихся 13 пар с числом 13 неправильных будут целых 11. Отлично. Дальше мы изучаем, сколько неправильных пар с числом 3. Это очень просто. Их всего две, потому что и 2, и 1 идут справа от тройки, и соответственно, вот эти пары 3, 2 и 3, 1 — они неправильные. Все остальные пары, в которые входит тройка и которые мы еще не учли, они все правильные. Поэтому здесь будет + 2 написано, и дальше нужно будет проделать просчет для всех остальных чисел. В общем-то, это несколько минут работы. Ключевое наблюдение, можно сказать, теорема. Теорема заключается в том, что если я перекидываю одно число через четное количество других, например, взял и здесь написал, а здесь зачеркнул, то количество неправильных пар меняется на четное число, то есть меняется четным образом. К нему прибавляется или вычитается что-то четное. Давайте поймем, почему это так. Если мы поймем, почему это так, то мы, конечно, поймем, что при всех разрешенных операциях не меняется четность вот этого числа четность количества неправильных пар. Ну, действительно, давайте просто проследим, что происходит при таком перескоке. Какие пары меняют четность, а какие сохраняют? Прежде всего заметим, что так как мы взяли одно число и куда-то переставили, то все пары, которые это число не включали, они как стояли, так и стоят. У них не изменилось ничего. Поэтому те из них, которые были правильные, остались правильные. Те, которые были неправильные, остались неправильные. Значит, вот в этой сумме они сколько вкладывали сюда слагаемых, столько и вкладывают. То есть вот эта сумма, она менялась только в тех местах, в которых мы учитываем 15. Вот эту 15 оно перепрыгнуло. Значит, только пары с участием 15 менялись с правильных на неправильные и наоборот. с какими числами правильность пары менялась вот у 15? Понятно, что ни с одним из вот этих она не менялась. Потому что как 15 было справа от них всех, так и осталось справа. Далее, понятно, что вот с каждым из чисел посередине правильность пары менялась. В данном случае 15 было со всеми ними неправильно расположено, а теперь со всеми ними расположено правильно. Но если бы это было не 15, а если бы, напротив, скажем, число 6 вот мы сюда бы кидали, то произошло бы наоборот. Что произошло бы? Ничего не менялось, кроме тех пар, в которых участвует 6. И для 6 расположение 6 с этими числами не будет меняться и с вот этими числами тоже не будет меняться, зато с любым из вот этих двух обязательно будет. Я выписываю вот такой фрагмент. Было 11, 14, 6, а стало 6, 11, 14. И обе включенные в шестерку пары, вот эти вот 11, 6 и 14, 6, заменились на пары правильные. Были неправильные, стали правильные. Могло быть так, что наоборот, если, скажем, какое-то число стояло в правильном порядке, скажем, 3 стояла с 7 и 11, если она перепрыгнет их обоих, напомню, что разрешены только скачки через четное количество чисел. Вот были две правильные пары обе стали неправильные. Может быть даже, что часть этих пар она была правильной, часть — неправильной. Скажем, 14 могла перескочить через шесть чисел, и были неправильные все пары, кроме пары 14, 15, а стали правильными все пары, кроме пары 14, 15, которая идет в обратном порядке. Таким образом, всегда меняется четность, и меняется она четное количество раз. Потому что число перепрыгивает через четное количество других чисел. Поэтому четность вот этого вот числа, которая и является четностью перестановки четность перестановки — это четность вот этого числа, четность числа пар, которые стоят в неправильном порядке вот эта четность — она не меняется никогда. Если мы стартовали с какой-то позиции в игре 15, которой соответствовала строка с четным количеством неправильных пар, то какие бы разрешенные операции вы ни делали, факт четности количества разрешенных пар не меняется, это инвариант. Будет все равно четное количество разрешенных пар. Могло быть, скажем, восемь, а потом после долгих действий станет ноль. То есть вы привели в исходную ситуацию или не исходную. В исходной, кстати, не ноль, нет. Станет ноль, это соответствие ситуации змейки на этой картиночке, на табличке. Или станет 28, 48, 44. То есть, в принципе, в пределах от 0 до 104 может быть любое число, но оно обязано быть четным. Количество неправильных пар не меняет свою четность. А если вы стартовали с нечетной, то вы тоже никогда не сможете добиться того, что количество неправильных пар будет четным. Оно будет всегда оставаться нечетным. То есть мы фактически свели задачу к очень похожей ситуации на ситуацию с бумажками и кучками камней. Мы свели ее к четности, просто четность здесь прячется довольно глубоко Чтобы понять, что здесь остается четным, нужно ввести понятие четности перестановки. То есть все пары учесть, про каждую из них спросить в правильном-неправильном порядке, посчитать четность количества пар в неправильном порядке. Чтобы полностью завершить анализ ситуации игры в 15, нужно сравнить четность здесь и здесь. Можно, конечно, было бы просто посчитать количество неправильных пар в обоих случаях, но математики поступают не так. Математики экономят свои усилия. В самом деле, посмотрите, до сих пор вообще ничего не менялось в этой ситуации по сравнению с этой. Поэтому никакие пары чисел от 1 до 12 своей четности не меняли при этом переходе. То есть если я переставил физически вот так вот, не по правилам, а физически переставил на пятнашки 15 и 14, то все пары, включающие числа до 13 12, 11, 10 и так далее, они какие были, такие и остались. У них четность явно не менялась. Четность количества неправильных пар слева не менялась. Поэтому надо изучить какой вопрос? Что происходит с четностью справа, а также с четностью тех пар, которые содержат один элемент отсюда и один отсюда. По счастью, нам очень легко заметить, что все числа слева меньше всех чисел справа. Поэтому ни одной нечетной пары такой, что один элемент отсюда, а один — отсюда, у нас нет. А значит, окончательно надо лишь сравнить, что произошло внутри вот этих вот троек. Внутри этих троек всего три пары пара 15, 14; 15, 13 и 14, 13. Что изменилось? 14, 13 и 15, 13. А пара 14, 15 стала правильной. Поэтому при физическом вырывании квадратика и переносе его через соседний четность количества неправильных пар меняется на единицу в данном конкретном случае. Всё, это означает, что отсюда сюда вы никогда не перейдете по разрешенным правилам.
