Автор Тема: Добрый день. Помогите решить... Лабиринт  (Прочитано 680 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн maska11

  • Новичок
  • *
  • Сообщений: 27
    • Просмотр профиля
 Лабиринт состоит из нескольких комнат, соединённых коридорами так, что из каждой комнаты можно дойти до любой другой. (Коридоры соединяют две комнаты и могут иметь разную длину.)  В каждой комнате на стене написана длина кратчайший трассы, которая начинается в этой комнате и проходит через все остальные комнаты. Докажите, что отношение длин  любых двух комнат максимально 1,5.

Оффлайн StrannikPiter

  • Эксперт
  • ******
  • Сообщений: 1148
    • Просмотр профиля
Re: Добрый день. Помогите решить... Лабиринт
« Ответ #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

  • Новичок
  • *
  • Сообщений: 27
    • Просмотр профиля
Re: Добрый день. Помогите решить... Лабиринт
« Ответ #2 : 30 Сентябрь 2016, 14:16:54 »
Спасибо большое!