Задача 64639

Темы:    [ Обход графов ] [ Примеры и контрпримеры. Конструкции ]

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

Условие

Автор: Жуков Г.

Можно ли n раз рассадить  2n + 1  человек за круглым столом, чтобы никакие двое не сидели рядом более одного раза, если
 а)  n = 5;  б)  n = 4;  в) n – произвольное натуральное число?

Решение

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

  а) На рисунке показано, как разбить на три цикла рёбра полного 7-вершинного графа: каждый цикл содержит все диагонали (или стороны) фиксированной длины правильного семиугольника.

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

  б) Реализуем 9-вершинный граф на вершинах и рёбрах правильной восьмиугольной пирамиды. Вершины остнования соединим ломаной, как показано на рисунке.

  Завершим цикл, соединив концы ломаной боковыми рёбрами с вершиной пирамиды. Остальные три цикла получаются из этого поворотами на 45°, 90° и 135°.

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

Ответ

Можно.

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

журнал
Название	"Квант"
год
Год	1992
выпуск
Номер	9
Задача
Номер	М1363