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

Проект МЦНМО
при участии
школы 57
Задача 32996
Тема:    [ Теория графов (прочее) ]
Сложность: 2
Классы: 8
В корзину
Прислать комментарий

Условие

Несколько Совершенно Секретных Объектов соединены подземной железной дорогой таким образом, что каждый Объект напрямую соединён не более чем с тремя другими и от каждого Объекта можно добраться под землей до любого другого, сделав не более одной пересадки. Каково максимальное число Совершенно Секретных Объектов?


Решение

  Оценка. Из данного Объекта можно добраться за один "ход" до трёх Объектов, а с пересадкой – еще до  2·3 = 6  Объектов. Следовательно, Объектов не больше 10.
  Пример с 10 Объектами изображен на рисунке.


Ответ

10.

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

Кружок
Название ВМШ 57 школы
класс
Класс 8
год
Год 1997/98
Место проведения 57 школа
занятие
Номер 9
Название Графы
Тема Неизвестная тема
задача
Номер 06

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

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