Page 279 - 1975_matematika-izium
P. 279
Таким образом, произвол в составлеНIПI расписания сводится ЛIlШЬ
К перестаиовкам внутри столбцов матриц второго, третьего и чет
вертого туров (кроме nepBoro столбl\а, который уже зафиксиро
ван). Это вполне соответствует процедуре, при меняемой автором,
и иужно лишь объяснить, почему им были выбраны Р , Рэ. Р4, а не
2
какие-нибудь иные перестановки. В дальнейшем мы будем обозна
чать одной и той же буквой как перестановку HeKoToporo фиксиро
ванного набора элементов, например et= ( G, Н , Е, F), �= (Н, G, F, Е),
V = (F, Е, Н, О) суть перестановки четверки (Е, F, G, Н , так и опера
)
цию, которой эта перестановка осуществляется, причем эту опера
ЦllЮ можно применять к раЗЛИ1.jllЫМ наборам элементов: et ( I , 2, 3, 4) =
= (3. 4, 1, 2), � ( /, J, K, L) = (L, K, /, /), V ( I , 2, 3, 4) = ( 2, 1 , 3 , 4) .
Рассмотрим вторые столбцы матрнц второго - четвертого ту
ров. Они получаlОТСЯ из BToporo столбца матрицы nepBoro тура, то
есть ИЗ букв (Е, F, G, Н) (для удобства я пишу здесь и далее стол
бец в строчку), тройкой перестановок, которая ДО.'1жна обладать
следующим свойством: при каждой перестановке ни одна из букв
ие остается на том же месте, что и в исходном столбце, и каждая
буква непременно должна побывать на всех остальных трех местах.
Существуют четыре тройки перестановок, УДОВ.'1еТВОРЯЮЩllе этому
УСЛОВIlЮ:
Id / 1 ) а � '\' I 2) а 8 '\' I 3) fJ � е I 4) а � ох
.1 3 4 2 3 4 2 3 4 2 3 4 2
2 4 3 1 4 3 ] 1 3 4 4 I 3
3 1 2 4 2 1 4 4 2 I 1 2 4
4 2 1 3 ] 2 3 2 1 3 2 3 1
)
(Id означает тождественную перестановку .
Те же рассуждения llрименимы ({ третьнм и четвертым столб
цам матриц BToporo - четвертого туров, и они также должны по.'1У
чаться нз сто.'1бцов (1, /, К, L) 11 (М, N, О, Р) одной ИЗ этих троек
перестановок, например 8(1, /, К, L) = (L, К, 1, /) и т. Д.
Теперь рассмотрим второй - четвертый столбцы одной н той же
матрицы любого из BToporo - четвертого туров. анн снова полу
чаются из соответствующих СТО.'1бцов матрицы nepBoro тура тройкой
перестановок, и нетрудно заметить, что эта тройка должна об.'1а
дать тем же характерным свойством, что и выше, поскольку ИГРОЮI
из одной четверЮI nepBoro тура должны быть рассеяны по всем
четверкам в любом нз остальных туров. Следовате.'1ЫIО, это опять
ДО.'lЖна быть одна из четырех выписанных выше троек перестано
вок.
Докажем, что тройка перестановок, отвечающая столбцам i-й
маТРIЩЫ, и тройка перестановок, отвечающая k-M столбцам всех
трех матриц, СОDпадают при любом выборе i, k. Отсюда следует.
что это будет одна и та же тройка при всех i и k.
Пусть, например, i = k = 2. Если тройки не совпадают, то пе
рестановкой, отвечающей второму столбцу матрицы BToporo тура,
может быть только <Х, � илн '\' (другие перестановки входят лишь
в одну из троек) . Все три случая идентичны, так что пусть это бу
дет et. Сначала рассмотрим случай, когда тройка матрнцы BToporo
тура есть (et, �, -у). Тогда второму столбцу третьей ИЛII четвертой
матрицы отвечает �. Следовате.'lЫIO, третьему или четвертому
282