Логические задачи и головоломки
23 Март 2017, 10:27:40 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
Новости:
 
   Начало   Правила Помощь Поиск Войти Регистрация Чат  
Страниц: [1]   Вниз
  Печать  
Автор Тема: Добрый день. Помогите решить... Лабиринт  (Прочитано 569 раз)
0 Пользователей и 1 Гость смотрят эту тему.
maska11
Новичок
*
Offline Offline

Сообщений: 27


Просмотр профиля
« : 08 Февраль 2016, 13:17:22 »

 Лабиринт состоит из нескольких комнат, соединённых коридорами так, что из каждой комнаты можно дойти до любой другой. (Коридоры соединяют две комнаты и могут иметь разную длину.)  В каждой комнате на стене написана длина кратчайший трассы, которая начинается в этой комнате и проходит через все остальные комнаты. Докажите, что отношение длин  любых двух комнат максимально 1,5.
Записан
StrannikPiter
Ветеран
*****
Offline Offline

Сообщений: 904



Просмотр профиля
« Ответ #1 : 02 Июнь 2016, 23:41:51 »

Если каждую комнату можно посещать не более одного раза, то отношение длин маршрутов может быть любым. Если же маршрут может проходить по нескольку раз через одну и ту же комнату, то доказательство такое:
Сравним трассы для произвольных комнат A и B. Для определенности будем считать, что трасса для комнаты A короче.
Эта трасса начинается в A и заканчивается в комнате C (как частный случай, это может быть и B).
Поскольку трасса проходит через все комнаты, то значит и через В тоже, и весь маршрут можно разбить на 2 участка, от А до В и от В до С.
Обозначим короткий из этих участков - "x", а длинный - "у". (x<=y)
Тогда длина трассы для комнаты А будет равна x+y
Но для комнаты В трасса может проходить вдоль участка "x", туда и обратно, и затем вдоль участка "y". Тогда она будет иметь длину 2*x+y
отношение длин трасс тогда будет (2*x+y)/(x+y) = 1+x/(x+y)
Очевидно, что это соотношение будет максимально в том случае, когда минимально "y", а минимальное значение для "y", это "x".
При y=x отношение будет равно 1.5, что и требовалось доказать.
Записан
maska11
Новичок
*
Offline Offline

Сообщений: 27


Просмотр профиля
« Ответ #2 : 30 Сентябрь 2016, 14:16:54 »

Спасибо большое!
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  

Powered by SMF 1.1.13 | SMF © 2006-2009, Simple Machines LLC
Simple Audio Video Embedder
| Sitemap