Версия для печати
Убрать все задачи

---

Найдите точку минимума функции y = (21-x)e21-x .

   Решение

---

Сколько существует разных способов разбить число 2004 на натуральные слагаемые, которые приблизительно равны? Слагаемых может быть одно или несколько. Числа называются приблизительно равными, если их разность не больше 1. Способы, отличающиеся только порядком слагаемых, считаются одинаковыми.

   Решение

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

Сложность: 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.

Ответ

Можно.

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