партии для него, т. е. на индекс к функции &Ск, которая этот исход выражает *). Таким образом, игра Гр также оказывается игрой в нормальной форме, с функциями выигрыша Жр(хи . к= 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 таких групп не существует, однако это до сих пор для всех таких п не установлено.

х) Как в утверждении, так и в условии!

2) Эти неравенства заменяют первоначальное р + q п\ они, очевидно, более сильные. Так как из них следует Зр р + 2q п и 1 + 2q р + 2q п, мы имеем п п- 1

3) По определению v = v ((1)) = -v ((2)). При п = 2 в утверждении (28:9) (которое эквивалентно свойству (28:10)) существенным является только v ((1)) = = v ((2)). На основании сказанного выше это означает, что v = -v, т. е. что v = 0.

28.2. Симметрия и безобидность

28.2.1. Как бы то ни было, если (28:8) выполняется для G = С?г, то из (28:7) следует:

(28:9) v (а?) зависит только от числа элементов в S.

Иначе говоря:

(28:10) . v(S)=vp,

где р - число элементов множества S (р = 0, 1, . . ., п).

Рассмотрим условия (25:3:а) - (25:3:с) из п. 25.3.1, которые дают исчерпывающее описание характеристических функций v(S). Легко переписать их для vp, если выполняется (28:10):

(28:11:а) v0 = 0,

(28:11:Ь) vp=-vp,

(28:11:с) vp+gvp + v для p + qn.

Очевидно,- (27:3) из п. 27.1.4 является следствием (28:10) (т. е. (28:9)), так что такая функция \(S) автоматически оказывается редуцированной, причем у = - Vi. Поэтому, в частности, мы имеем (27:7), (27:7*), (27:7**) из п. 27.2, т. е. условия рис. 30.

Условие (28:11:с) может быть переписано аналогично (25:А) из п. 25.4.2.

Положим r=n - p - q; тогда свойство (28:11:Ь) позволяет записать свойство (28:11 :с) следующим образом:

(28:11:с*) Vp + Vg-f-vr<; 0, если p + q + r = n.

Теперь свойство (28:11:с*) является симметричным относительно р, q, г *), следовательно, мы можем, используя соответствующую подстановку, принять, что р q г. Кроме того, когда р = 0 (и, следовательно, когда г = п - q), (28:11:с*) (и притом даже со знаком =) следует из (28:11:а) и (28:11:Ь). Значит, можно предполагать, что р Ф 0. Итак, нам необходимо потребовать выполнения (28:11:с*) только для 1 < р < q г, и поэтому, то же самое верно и для (28:11:с). Отметим, наконец, что, так как г = п - р - д, неравенство q г означает р -\- 2q п. Сформулируем сказанное.

(28:12) Выполнения (28:11:с) достаточно требовать только при lpq, p + 2qn*).

28.2.2. Свойство (28:10) характеристической функции является следствием симметрии, но оно важно также и само по себе. Это становится ясным, если мы рассмотрим его в наиболее простом частном случае: при п = 2.

В самом деле, при п = 2 свойство (28:10) просто означает, что v из п. 17.8.1 обращается в нуль 3).