Таблицы Брадиса

Построим биекцию между множествами четных

Построим биекцию между множествами четных

Элементы математики в задачах - Г. А. Мерзон

б)  Как следует из предыдущего пункта, четность подстановки ап равна произведению четности п на четность а.

Решение 2. Запишем подстановку а канонически, а Ь — так, что­бы числа в нижней строке стояли по порядку: а = ^, Ь = = (I1 . Тогда аЬ = ^• В силу задачи 0 четность подста­новки а равна четности числа беспорядков в строке а1, , ап, под­становки Ь — в строке Ь1,. . . , Ьп, а подстановки аЬ — четности суммы этих чисел.

Задача 5. Каких подстановок в Бп больше: четных или нечетных?

Ответ. Число четных подстановок равно числу нечетных.

Решение. Построим биекцию между множествами четных и нечет­ных подстановок: зафиксируем некоторую транспозицию £ и каждой четной подстановке а поставим в соответствие (нечетную, как мы уже доказали) подстановку а£. Осталось убедится в том, что это

148                                    Подстановки 2

биекция. Для этого достаточно заметить, что у него есть обратное — то же самое отображение (на нечетных подстановках).

Задача 6*. Докажите, что если в игре «пятнашки» поменять местами фишки с номерами «14» и «15», то, играя в эту игру, невозможно получить первоначальное расположение фишек.

 

 

Набросок решения. Допустим, из начального расположения фишек можно поменять фишки «14» и «15» местами, вернув остальные на свои места. Положим на место пустой клетки фишку с надписью «16». Тогда каждому расположению фишек соответствует некоторая подстановка а є S16. Ход заключается в том, что мы меняем некоторую фишку с фишкой «16», то есть умножаем имеющуюся у нас под­становку на некоторую транспозицию. Следовательно, при каждом ходе четность подстановки меняется, а значит, всего было сделано нечетное число ходов.