ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .