Л.А. Калужнин, В.И. Сущанский - Преобразования и перестановки

ПРОБЛЕМЫ НАУКИ И ТЕХНИЧЕСКОГО ПРОГРЕССА Л. А. КАЛУЖНИН, В. И. СУЩАНСКИЙ ПРЕОБРАЗОВАНИЯ И ПЕРЕСТАНОВКИ Перевод с украинского Г. И. Фадина ИЗДАНИЕ ЕТОРОЕ, ДОПОЛНЕННОЕ МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКНИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ Гааа Бь»К 22.!41 К)7 УЛК 512.54+519,1+ 519.515 К а л у ж пи и Л.

Л., Суп!а н с кн й Ги И. Преобразования н перестановки: Пер. с укр. — '2-е изд., перераб. и доп. — Мл Наука. Главная редакция физюсо-математической литературы, 1985. — 160 с.— 1Проблемы науки и технического прогресса). Рецензент доктор физино-математических наук С. А. Степанов Лгз Аркадьевич Кааужкин вигалиа Неаиазич Еужаискид ПРЕОБЛЗОВЛНИИ И ПЕРЕЕТЛИОВКИ Редзнтор ВХ Л!. Горячая Технический редактор и. ЦЛ А ксельрад Художес!еенный редактор 7. Н. Коль«сизо Корректоры Л. и. Назарова, М. Л.

й!едзсдская ПБ !0 12670 Елена в набор 2б 1184 Подписано к печзтн 9107.85. Формзт 84«108'Бл БУмага тнп. лч 3 гзРннтУРз лнт«РзтУРнзв. печать высокая Уел аеч. л 8,4. лсл гр.-отт. 8,82. Уч.-нзд. л. 8,79. 1!евз 55 коп. Орленз Трудового Крзсного й~ зл нн нздзтельство «Нзукв» Глзвнзя редакция фнзнко-мзтемзтнческой литературы !17071 Москва В-71, Ленннсннй проспент, 15 грцепв Трулового Красного Впямеяи Пернья впогрзбнп гтзвтельствв «нзукви. 199021, ленинград, В-зй, 9 линял, !2 1702330000 — 121 053(02)-85 © Издвтельегво «Нзукз», Глзвнвн рпввкцня бмзпно-мвтелытнчесной литературы. Плерезол с ивановского, !979: с нзмепеннянн н дополненмямн, !985 Изучаются преобразования и перестановки конечных множеств, вводятся понятия группы перестановок и полугруппы преобразований, Приводятся элементарные сведения о группах преобразований.

Пз конкретных примерах рассказывается о применениях теории групп при решении комбпнаторных задач, изучении явлений симл!стрип в алгебре и геометрии, построении математической теории игр типа игры «в пятнадцать» плн «кубик Рубика». Проводится математический анализ теории этих игр. Первое издание вышло в 1979 г. Книга рассчитана на члпателей, серьезно интересующихся математикой.

Кинга будет также интересна всем, интересующимся игрой «кубик Рубика» п другпллн подобными играми. Табл. 8 Ил. 53. Пиблиогр. 27 назв. ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ В книге в популярной форме излагаются начальные сведения из теории групп. Аппарат теории групп является основным прн изучении явлений симметрии, лежаших в основе фундаментальных закономерностей современного естествознания.

Именно поэтому теория групп нашла широкое применение не только в современной математике, но и в ядерной физике, кристаллографии, теории относительности, различных разделах химии. Име1отся опыты применения теоретико-групповых методов анализа в теории музыки, литературоведении, теории живописи, архитектуре. Математическая глубина п необычайно широкая сфера применений теории групп сочетаются с простотой ее основных положений, вполне доступных прн наличии хорошо иллюстрируюших примеров школьникам старших классов.

Поэтому теория групп как нельзя лучше подходит для того, чтобы показать школьникам образец современной математической теории н проиллюстрировать на примерах, как абстрактные теоретико-групповые понятия применя1отся при решении конкретных задач из разделов математики, уже знакомых читателю. Изучение понятия группы будет в достаточной степени оправдано, только если его применения будут разнообразны и интересны.

Это одна из причин того, что основные теоретико-групповые понятия и результаты в книге излагаются в рамках теории групп перестановок конечных множеств. При таком изложении читатель постоянно работает с отображениями конечных множеств, что позволяет лучше усвоить понятия множества и функции — центральные понятия в школьном курсе математики. При написании книги использовался опыт изложения основ теории групп на кружках и факультативных занятиях в республиканской физико-математической школе- интернате при Киевском государственном университете.

3 Первое издание книги, вьппелшее в 1979 г.,— вто выполненный Г. Р!. Фа.шным перевод с украинского, котоГый был дополнен авторами включением новых параграфов, касающихся приложений групп перестановок. В настоящем издании по сравнению с первым 'расширены следующие параграфы: «Образующие симметрической группы», «Подгруппы симметрических групп. Группы перестановок», «Группы симметрий», «О решении алгебраических уравнений».

Добавлены новые параграфы: «Георема Кэпи», «Перестановочные конструкции», «Венгерский шарнирный кубик», «Другие игры». Расширены н частично изменены подборки задач. Киев Л. А. Калужнин В. И. Суи1анский 5 Ц СУПЕРПОЗИЦИЯ ФУНКЦИЙ Действие (илн, иначе, операция) суперпозиции функций имеет ряд интересных свойств и много важных применений. Напомним определение и простейшие свойства суперпозицни для функций действительной переменной (функций, области определения и множества значений которых являются подмножествами множества действительных чисел). Пусть Г(х) и д(х) — произвольные функции действительной переменной. Суперпозицией этих функций (именио в том порядке, в котором они записаны) называется такая функция 6(х), что: а) область определения й(х) образована теми числами ло из области определения функции г (х), для которых ) (хо) принадлежит области определения функции д(х); б) значение функции й(х) в какой угодно точке хо из области ее определения связано со значениями ) (х) и д (х) равенством й (хо) = д Д(хо)) Таким образом, чтобы найти значение функции й(х) в точке хо, нужно найти г'(хо)=ио, а затем д(уо).

Число д(ио) и есть значение функции 6(х) в точке х,. Если функция и(х) в точке хо принимает значение и«о то это будем изображать так: хо —" и (хо) ио. Читается такая схема одним нз следующих способов: «функция и(х) в точке хо принимает значение по», «функция и (х) точке хо ставит в соответствие точку и,», «точка ио является образом точки х, под действием функции и(х)».

Для суперпозиции й(х) функций р=)(х) и х = д(х) такая схема будет иметь вид « хо — ро — ео о (егли функция ! (х) точке хо ставит в соответствие точку уо, а функция д(х) точке у,— точку го, то функция Й(х) точке х, ставит в соответствие точку го). 4 Пример. Пусть Г(х)=х', д(х)=япх. Чтобы найти значение суперпозиции Й(х) этих функций в неко. торой точке х„нужно возвести хо в квадрат, хо уо= хо, ! и найти значение у(х) в точке уо'. у, — з1 и у, = з! и (х';), И Объединяя эти две схемы, получаем хо уо=х~о е яп(х~о). 1 Таким образом, функция Й(х) каждой точке хо ставит в соответствие яп(хо), т.

е. Й(х) можно задать формулой Й (х) = з(п (х'). Рассмотрим теперь суперпозицию Й, (х) функций д (х) = = з1пх и 1(х) =х', т. е. суперпознцию тех же самых функций, но в обратном порядке. Получим хо — з)п хо — "-'(яп хо) . о!п ° ь.з' о, Это означает, что суперпозиция функций д(х) =з(пх и 1(х) =х' есть функция Й,(х) =(япх)'=з(пох. В Таким образом, суперпозиция функций зависит от порядка, в котором записаны функции. Будем обозначать суперпозицню функций у=~(х) и а=у(х) так: (! д) (х), т. е. х — у=1(х) о г =д(у).

1и 1 Следовательно, (! д) (х) =д(г'(х)). Особую роль относительно операции суперпозиции играет функция у=х, которую будем обозначать е(х). Схема этой функции такая: о ко хо для каждого числа хо. Очевидно, для любой функции у=)(х) выполняются равенства (1 е) (х) = (е 1) (х) =1 (х), или, в виде схемы, хо — уо = )' (хо) — уо, хо — хо — уо = ) (х,). о о Дадим отдельное обозначение и для функции у= — х, а именно е'(х). Мы будем рассматривать ьпюжества функций, имеющих следующее свойство.' Если функции 1' (х) и а (х) принадлежат заданному множеству функций, то и суперпозиция (1 а) (х) этих функций также принадлежит этому множеству. О таком множестве говорят, что оно замкнуто относительно операции суперпозиции функций, нли, иначе, что суперпозиция является внутренней операцией для такого множества. Найдем, например, суперпозицию двух линейных функций.

Пусть 1(х) =2х+5, д(х) =Зх+!. Для произвольного числа х, имеем хо ~ 2хо+5=уо ~ Зуо+1=3(2хо+ 5)+1, т. е. хоХ в З(2хо+5)+1=6хо+16, а следовательно, (~ д)(х)=-6х+16. Отсюда суперпозиция двух заданных линейных функций снова есть линейная функция. Легко доказать, что это верно и в общем случае; если ~(х) =ах+ 5, а д(х) =сх+й, то () а) (х) =с(ах+Ь)+й =- =асх+Ьс+й=аох+'Ьь т. е. снова функция линейная. Прн этом коэффициенты этой функции выражаются через коэффициенты )(х) и й (х) с помощью равенств ат = ас, Ьо — — Ьс+ А Следовательно, множество всех линейных функций вместе с каждыми двумя функциями содержит и их супер- позицию, т.