Здравствуйте, товарищи.
Задача звучит следующим образом:
Есть 14 команд.
Каждая команда должна сыграть с каждой один раз.
Получается 13 туров по 7 игр.
Например, первый тур может выглядеть так:
1-2
3-4
5-6
7-8
9-10
11-12
13-14
Соответственно, следующий тур должен так же состоять из 7 пар, при этом не должно быть повторов.
Мне удалось создать 7 туров. Подробности в конце сообщения.
Внимание вопросы:
Есть ли решение у этой задачи?
И, если есть, как оно выглядит?
P.S.:
Удалось построить 8 туров. Алгоритм следующий.
1. Первый тур:
1-2
3-4
5-6
7-8
9-10
11-12
13-14
2. Второй тур рассчитывается следующим образом.
а). Самую верхнюю пару переворачиваем, т.е. было 1-2, стало 2-1.
б). Сдвигаем правую колонку на один пункт вверх. Т.е. должно получиться следующее:
-
1
2-4
3-6
5-8 -> Далее свободную верхнюю цифру (в данном случае Единица) ставим в пару с числом 13.
7-10
9-12
11-14
13-
в). Получаем такой столбец:
2-4
3-6
5-
8
7-10
9-12
11-14
13-1
г). И последний шаг. По диагонали строим пары, получаем второй тур, т.е.:
2-6
3-8
5-
10
7-12
9-14
11-1
13-4
д). Для рассчёта третьего тура начать с пункта а).
Используя данный алгоритм, мы получим следующий результат:
I | II | III | IV | V | VI | VII | VIII X
1-2 | 2-6 | 6-10 | 10-14 | 14-4 | 4-8 | 8-12 | 12-1
3-4 | 3-8 | 3-12 | 3-1 | 3-2 | 3-6 | 3-10 | 3-14
5-6 | 5-10 | 5-14 | 5-4 | 5-8 | 5-12 | 5-1 | 5-2
7-8 | 7-12 | 7-1 | 7-2 | 7-6 | 7-10 | 7-14 | 7-4
9-10 | 9-14 | 9-4 | 9-8 | 9-12 | 9-1 | 9-2 | 9-6
11-12 | 11-1 | 11-2 | 11-6 | 11-10 | 11-14 | 11-4 | 11-8
13-14 | 13-4 | 13-8 | 13-12 | 13-1 | 13-2 | 13-6 | 13-10
Далее алгоритм не работает.
Здравствуйте, Andrey_Sergeevich, Вы писали:
A_S>Здравствуйте, товарищи.
A_S>Задача звучит следующим образом:
A_S>Есть 14 команд.
A_S>Каждая команда должна сыграть с каждой один раз.
A_S>Получается 13 туров по 7 игр.
В старые добрые времена, когда расписание составлялось вручную, за 5 минут между турами, применялась следующая схема (в примере будут 6 игроков)
В первом туре спаривают игроков вдоль побочной диагонали (с северо-востока на юго-запад):
1 2 3 4 5 6
+-+-+-+-+-+-+
1|X| | | | |*|
+-+-+-+-+-+-+
2| |X| | |*| |
+-+-+-+-+-+-+
3| | |X|*| | |
+-+-+-+-+-+-+
4| | |*|X| | |
+-+-+-+-+-+-+
5| |*| | |X| |
+-+-+-+-+-+-+
6|*| | | | |X|
+-+-+-+-+-+-+
Для второго тура диагональ смещают на одну позицию влево; там, где она пересеклась с главной диагональю, игрока спаривают с последним (при нечетном количестве у такого игрока выходной):
1 2 3 4 5 6
+-+-+-+-+-+-+
1|X| | | |*| |
+-+-+-+-+-+-+
2| |X| |*| | |
+-+-+-+-+-+-+
3| | |X| | |*|
+-+-+-+-+-+-+
4| |*| |X| | |
+-+-+-+-+-+-+
5|*| | | |X| |
+-+-+-+-+-+-+
6| | |*| | |X|
+-+-+-+-+-+-+
Для третьего тура сдвигают еще раз:
1 2 3 4 5 6
+-+-+-+-+-+-+
1|X| | |*| | |
+-+-+-+-+-+-+
2| |X|*| | | |
+-+-+-+-+-+-+
3| |*|X| | | |
+-+-+-+-+-+-+
4|*| | |X| | |
+-+-+-+-+-+-+
5| | | | |X|*|
+-+-+-+-+-+-+
6| | | | |*|X|
+-+-+-+-+-+-+
И так далее.
Выстраиваем в две строки, играют пары в столбцах. Если нечетное количество — добавляем пустышку (ее соперник отдыхает)
A B C
E F G
Далее на каждом шаге делаем циклическую ротацию всех, кроме A, стоящего на фиксированной позиции
A E B
F G C
-----
A F E
G C B
-----
A G F
C B E
-----
A C G
B E F
Здравствуйте, VsevolodC, Вы писали:
VC>http://en.wikipedia.org/wiki/Round-robin_tournament
VC>там и ссылка на генератор есть..
О, какая простая идея!
А я, когда реальный турнир составлял, помнится, намучился с шахматкой.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Хотя
здесьАвтор: VsevolodC
Дата: 01.10.08
уже привели одно из решений, выдвину свое.
Будем рассматривать общий случай, когда имеем N игроков, между которыми надо провести 1-круговой турнир. Соответственно в турнире будет N-1 тур.
Утверждение 1.
Можно считать, что N — четное число. В противном случае добавляем фиктивного игрока и решаем задачу в случае N+1. Если кому то выпадает играть с фиктивном игроком, то считаем, что он в этом туре не играет.
Всюду далее будем считать, что N — четное число
Утверждение 2.
Занумеруем игроков от 1 до N. Тогда каждому расписанию соответствует матрица A = { a_i,j }, где
если i != j, то a_i,j — номер тура, в котором между собой сыграли команды i и j
если i == j, то a_i,j = N
Заметим, что матрица A обладает двумя свойствами
2.1 Она симметрична
2.2 В каждой строчке и каждом столбце встречается каждое число от 1 до N и ровно один раз
Верно также и обратное. Каждой матрице A со свойствами 2.1 и 2.2 соответствует расписание. Таким образом имеем биекцию между расписаниями и матрицами
Утверждение 3.
Рассмотрим коммутативнуй группу G порядка 2 из N элементов. Порядка 2 означает, что любой элемент группы G имеет порядок 2, то есть a*a = 1 для любого элемента a группы G
Рассмотрим таблицу Келли для группы G. Таблица Келли для группы — это квадратная матрица размера равного числу элементов группы, у которой в i-й строке и j-м столбце стоит произведение i-го и j-го элемента группы. Получается, что таблица Келли для группы G обладает свойствами 2.1 и 2.2
Таким образом доказано утверждение: Существует биекция между искомыми расписаниями турнира и коммутативными группами порядка 2 из N элементов
Утверждение 4.
В случае, когда N = 7, можно описать все возможные расписания, так как соответствующие группы леко найти.
Мы ищем коммутативные группы порядка 2 из 8-ми элементов.
Обозначим эти элементы как: 1, a, b, c, d, e, f, g — где 1 — единичный элемент группы
Так как группа порядка 2 то имеем соотношение
4.1) a*a = 1, b*b = 1, ..., g*g = 1
Так как a != 1 b != 1, то a*b может быть элементом из множества {c, d, e, f, g} Без ограничения общности можно считать, что выполнено соотношение
4.2) a*b = c
Из свойств 4.1 и 4.2 и коммутативности группые легко получается, что a*c = b, b*c = a.
Также легко видеть, что множества {a*d, b*d, c*d } равно множеству {e, f, g}
Без ограничения общности можно считать, что выполненно соотношение
4.3) a*d = e, b*d = f, c*d = g
Соотношения 4.1, 4.2 и 4.3 полностью определяют группу G. Таким образом мы получили, что данная группа всего одна с точностью до изоморфизма.
Таким образом для 7-ми человек каждое расписание будет иметь одинаковую структуру.
Сколько же всего их будет?
При формировании условия 4.2 элемент c можно выбрать 5-ю различными способами.
При формировании условия 4.3 соответствие между двумя множествами из 3-х элементов можно установить 6-ю способами
Таким образом всего имеем 30 различных расписаний. Более того, имеем также легкий алгоритм для получения всех таких расписаний
Перекуём баги на фичи!
