Задача 109513

Темы:    [ Турниры и турнирные таблицы ] [ Разбиения на пары и группы; биекции ] [ Правильные многоугольники ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Токарев С.И.

В турнире по теннису n участников хотят провести парные (двое на двое) матчи так, чтобы каждый из участников имел своим противником каждого из остальных ровно в одном матче. При каких n возможен такой турнир?

Решение

  Пусть описанный в задаче турнир проведён. Тогда все противники одного теннисиста разбиваются на пары, поэтому n нечётно. Все возможные пары противников разбиваются на четвёрки пар, игравших в одном матче. Следовательно, число  ½ n(n – 1)  этих пар кратно 4, откуда  n – 1 = 8k.
  Докажем, что при любом натуральном k указанный турнир для  n = 8k + 1  участников возможен. При  k = 1  для описания турнира поставим в соответствие теннисистам вершины правильного девятиугольника A₁A₂...A₉. На рисунке изображён матч пары  (A₁, A₂)  против пары  (A₃, A₅),  причём отрезками соединены противники.

  Поворачивая эту конструкцию из отрезков вокруг центра на углы, кратные ^2π/₉, мы получим изображения для остальных восьми матчей. При этом каждая хорда вида A_iA_j используется ровно один раз, поскольку она равна в точности одной из хорд  A₂A₃, A₁A₃, A₂A₅ и A₁A₅.
  При  k > 1  выделим одного из  8k + 1  теннисистов, а остальных разобьём на k групп по 8 человек. Присоединяя выделенного теннисиста последовательно к каждой группе, проведём в них турниры по описанной выше схеме для 9 человек. Тогда останется только провести матчи между противниками из разных групп. Для этого достаточно разбить каждую группу на четыре команды по два человека и провести все возможные матчи между командами из разных групп.

Ответ

n = 8k + 1,  где  k ∈ N.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1993
Этап
Вариант	5
класс
Класс	11
задача
Номер	93.5.11.7