Таким образом, мы пишем:

(28:1) Р: i->ip

или, используя полное перечисление,

(28:2, Р: 2-"-» V>.

Некоторые из подстановок заслуживают особого упоминания.

(28:А:а) Тождественная подстановка 1п, которая оставляет каждое i (i = 1, . . ., п) неизменным: i ->- iIn = i.

(28: А: Ь) Произведение PQ двух подстановок Р и Q, состоящее в выполнении сначала Р, а затем Q: i ->- ip(? = (ip)Q.

Число всех возможных подстановок равно факториалу п,

п! = 1.2...л,

и все вместе они образуют симметрическую группу подстановок 2Л. Всякая подсистема G с: 2Л, удовлетворяющая двум условиям:

(28:А:а*) In£G,

(28:А:Ь*) PQ£G, если P£G и <?£G,

является группой подстановок.

Подстановка Р переводит всякое подмножество S с:. I = (1, . . . , п) в другое подмножество SP2).

Замечание. Серьезное и развернутое изложение теории групп можно найти в следующих книгах: L. С. Mathewson, Elementary Theory of Finite Groups, Boston, 1930; W. Burnside, Theory of Groups of Finite Order, 2nd Ed., Cambridge, 1911; A. S p e i s e r, Theorie der Gruppen von endlicher Ordnung, 3rd Ed., Berlin, 1937.

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

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

Для ознакомления с более полным изложением связи между симметрией итеорией групп см. Н. Weyl, Symmetry, Journ. Washington Acad, of Sciences, vol. XXVIII (1938), pp. 253ff.

28.1.2. После этих общих и подготовительных замечаний мы приступаем теперь к применению введенных понятий к произвольной игре п лиц Г.

Выполним подстановку Р над символами 1, . . ., п, обозначающими игроков игры Г. Другими словами, обозначим игрока к = 1, . . ., п через кр вместо к; это преобразует игру Г в другую игру Гр. Замена игры Г на игру должна оказать свое влияние в двух отношениях: на действие, которое каждый игрок совершает в течение партии, т. е. на индекс к переменной %k, которую каждый игрок выбирает; и на исход

(1 2 \ 2 Л • Тожде-

v , /1, 2, . . ., л\

ственнои (см. ниже) является подстановка in = I

2) Если S = (ки . . ., кр), то SP = (kf, . . .,

партии для него, т. е. на индекс к функции &Ск, которая этот исход выражает *). Таким образом, игра Гр также оказывается игрой в нормальной форме, с функциями выигрыша Жр(хи • . к= 1, . . ., п. Выра-

жая функцию ЖР{хх, . . ., хп) через &Ch (хи . . ., тл), мы должны помнить, что игрок к в игре Г имел теперь же он является игроком кр в игре Гр и, следовательно, имеет ЖРр. Если мы составим функцию

е/ТР от переменных т4, . . ., тп, то мы выразим исход партии в игре Гр, когда игрок, имеющий номер к в игре Гр, выбирает xk. Далее, игрок к в игре Г, который является игроком кр в игре Гр, выбирает xkp. Следовательно, переменными, входящими в функцию $£k, должны быть

х1р> • • • > Гпр

Поэтому мы имеем

(28:3) &СРР (т1? ..., тп) = #£А (т1Р, ..., тпр).

Замечание 1. Читатель заметит, что верхний индекс Р при индексе к для функций Ж оказывается в левой части, в то время как верхний индекс Р при индексах к переменных xk оказывается в правой. Это - правильное размещение, и довод, приведенный перед (28:3), был необходим для установления его.

Безупречность и ясность в этом пункте важны потому, что иначе мы не могли бы быть уверены, что последовательные применения верхних индексов P и Q (в таком порядке) к игре Г дадут такой же результат, как и применение верхнего индекса PQ к игре Г. Читатель может провести проверку этого факта в качестве хорошего упражнения в вычислении подстановок.

(1 2\ 2* А применение P с каждой стороны давало один и тот же

результат, следовательно, не было надобности в таких рассуждениях. См. сноску 1 на стр. 136.

Замечание 2. В игре двух лиц с нулевой суммой мы имеем Ж ~ Ж\ = - Ж 2 и, аналогично, Жр = Жр ~ - Жр. Следовательно, в этом случае (см. выше, п = 2

и P= j (28:3) превращается в Жр (т1? т2) == - Ж (т2, тл), что согласуется с формулами из пп. 14.6 и 17.11.2.

Однако такое упрощение возможно только в игре двух лиц с нулевой суммой; во всех остальных случаях мы должны опираться лишь на общую формулу (28:3).

Обозначим характеристические функции игр Г и Гр соответственно через v(S) и vp (S). Так как игроки, образующие множество Sp в игре Гр, те же, что и игроки, образующие множество S в игре Г, мы имеем

(28:4) vp(Sp)=v(S) при любом S2).

28.1.3. Если (для некоторого Р) игра Г совпадает с игрой Гр, то мы говорим, что игра Г инвариантна или симметрична по отношению к Р. В силу (28:3) это выражается в виде

(28:5) ейГлр(Ti, .. ., хп) = Жк(ъ1р, ..тпр).

Если это имеет место, то (28:4) превращается в

(28:6) v (Sp) = v (S) при любом S.

Пусть дана игра Г. Составим множество Gr всех подстановок Р, по отношению к которым игра Г симметрична. Из (28:А: а) и (28:А:Ь)

*) Подобное положение для п = 2 см. в сноске 1 на стр. 136.

2) Это концептуальное доказательство яснее и проще доказательства с помощью вычислений, которое могло бы опираться на формулы из п. 25.1.3. Последнее, однако, не вызвало бы никаких затруднений, а только потребовало бы более подробных обозначений.

ясно, что тождественная подстановка 1п принадлежит Gr и что если Р, Q £ Gr, то и PQ £ Gr. Поэтому на основании (28:А:а*) и (28:А:Ь*) Gp является группой. Назовем Gr группой инвариантности игры Г. Заметим, что (28:6) может быть записано теперь в следующем виде:

(28:7) v (S) = v (Т), если существует такая подстановка Р £ Gt>

что £р = Т, т. е. подстановка, переводящая S в Т.

Объем множества Gr, т. е. число его элементов, представляет собой некоторую характеристику того, «насколько симметрична» игра Г. Если любая подстановка Р (отличная от тождественной 1п) изменяет игру Г, то Gp состоит только из 1п и игра Г называет полностью несимметричной. Если любая подстановка Р не изменяет игру Г, то Gr содержит все подстановки Р, т. е. является симметрической группой 2Л, и игра Г называется полностью симметричной. Между этими двумя случаями имеется, конечно, много промежуточных, и точная структура симметрии игры Г (или ее отсутствия) определяется группой Gr.

28.1.4. Из условия (28:7) следует, что S и Т имеют одинаковое число элементов. Обратное утверждение, однако, не всегда верно, если группа достаточно мала, т. е. если игра Г достаточно несимметрична. Поэтому представляет интерес рассмотреть такие группы G = Gr, которые допускают обратное утверждение, т. е. для которых справедливо следующее:

(28:8) , Если множества S и Т имеют одинаковое число элементов, то существует такая подстановка Р £ G, что Sp = Т, т. е. подстановка, переводящая S в Т.

Условие (28:8), очевидно, выполняется, когда G является симметрической группой 2Л, т. е. G = Gr = 2Л для любой симметричной игры Г. Оно выполняется также для некоторых меньших групп, т. е. для некоторых игр Г, не вполне симметричных.

Замечание. При п = 2 группа 2Л содержит, кроме тождественной, только

(1 2\ 2 Л •> см- несколько предшествующих замечаний), так

что G - 2П является единственной возможностью для какой-либо симметрии.

Рассмотрим поэтому п -\ 3 и назовем группу G транзитивной на множествах, если она удовлетворяет (28:8). Вопрос о том, какие группы G Ф 2Д являются транзитивными на множествах, представляет определенный теоретико-групповой интерес, однако касаться этого в нашем изложении нет необходимости.

Для читателя, интересующегося теорией групп, мы тем не менее кое-что отметим.

Существует подгруппа группы 2Л, содержащая половину ее элементов (т. е.

у я!), называемая знакопеременной группой j£n. Эта группа имеет большое значение

в теории групп и подробно там изучается. При п Ш 3 она, как это легко видеть, также является транзитивной на множествах.

Итак, фактически вопрос состоит в том, для каких п 3 существуют транзитивные на множествах группы ОфЪп и ФУп.

Легко показать, что при п = 3, 4 таких групп нет. При п = 5, 6 они существуют. (При п = 5 существует транзитивная на множествах группа G, состоящая из 20 элементов, в то время как Е5 и Аь содержат соответственно 120 и 60 элементов. При п = 6 существует транзитивная на множествах группа G, состоящая из 120 элементов, в то время как 26 и содержат соответственно 720 и 360 элементов.) При п = 7, 8 довольно сложные теоретико-групповые рассуждения показывают, что таких групп снова нет. Для п = 9 вопрос пока открыт. Представляется вполне вероятным, что для произвольного тг > 9 таких групп не существует, однако это до сих пор для всех таких п не установлено.