Задача по олимпиадной математике: Сидение людей за круглым столом

  Задачу эквивалентна следующей:

    можно ли в полном графе с  2n + 1  вершиной провести n гамильтоновых циклов, не имеющих общих рёбер?

  Действительно, обход такого цикла задает порядок рассадки за круглым столом – в порядке обхода вершин. В цикл входит  2n + 1  ребро, а всего рёбер  n(2n + 1),  поэтому при положительном ответе все рёбра будут задействованы в циклах по одному разу.   а) На рисунке показано, как разбить на три цикла рёбра полного 7-вершинного графа: каждый цикл содержит все диагонали (или стороны) фиксированной длины правильного семиугольника.

  Очевидно, подобная конструкция годится для любого правильного (2n+1)-угольника, где  2n+ 1  – простое число. В частности. для 11-угольника  (n= 5)  ответ положительный.   б) Реализуем 9-вершинный граф на вершинах и рёбрах правильной восьмиугольной пирамиды. Вершины остнования соединим ломаной, как показано на рисунке.

  Завершим цикл, соединив концы ломаной боковыми рёбрами с вершиной пирамиды. Остальные три цикла получаются из этого поворотами на 45°, 90° и 135°.   в) Конструкция из б) обобщается заменой 8-угольной пирамиды на 2n-угольную. Циклы получаются друг из друга поворотами на ^180°/_n.