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

Проект МЦНМО
при участии
школы 57
Задача 108739
Темы:    [ Задачи с ограничениями ]
[ Перебор случаев ]
Сложность: 4
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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


Решение

  Порядок, в котором могут связываться по радио четыре станции:  AB, CD, BD, AC, AD, BC.
  Докажем, что пять станций не могут общаться указанным в задаче способом. Пусть станции находятся в вершинах пятиугольника ABCDE. Заметим, что первыми могут поговорить только две соседние станции. Более того, каждая станция, когда впервые выходит на связь, говорит с одной из соседних с ней. Пусть первый сеанс связи был между станциями A и B. Для следующего разговора есть всего два варианта: D с E и C с D (остальные разговоры невозможны согласно вышеизложенному). А третий разговор уже невозможен.
  Допустим,  n > 5.  Посмотрим на какие-нибудь пять станций из этих n. Эти станции говорили между собой способом, удовлетворяющим условию, что невозможно.


Ответ

n = 4.

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

олимпиада
Название Турнир им.Ломоносова
год/номер
Номер 29
Дата 2006
задача
Номер 6

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

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