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

---

Из набора гирь весом 1, 2, ..., 26 выделить шесть гирь так, чтобы среди них не было выбрать двух кучек равного веса.
Доказать, что нельзя выбрать семь гирь, обладающих тем же свойством.

   Решение

Темы:    [ Степень вершины ] [ Четность и нечетность ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 8,9

Прислать комментарий

Условие

В системе связи, состоящей из 2001 абонентов, каждый абонент связан ровно с n другими. Определите все возможные значения n.

Подсказка

Посчитайте количество пар связанных абонентов и покажите, что n чётно.

Решение

  Так как каждый из 2001 абонентов связан ровно с n другими, то общее число направлений связи равно 2001n. Отсюда общее число связанных пар абонентов равно  2001n : 2,  так как каждая связанная пара имеет ровно два направления связи. Поскольку это число должно быть целым, то число n должно быть чётным.
  Докажем, что для каждого  n = 2t  (t = 0, 1, ..., 1000)  существует система связи из 2001 абонентов, в которой каждый связан ровно с n другими. В самом деле, расположив всех абонентов на окружности и связав каждого из них с t ближайшими к нему по часовой стрелке и с t ближайшими к нему против часовой стрелки, получим пример такой сети связи.

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