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

задан 1 Апр '18 4:57

Ни у кого нет идей? :(

(1 Апр '18 19:03) Hector

@Hector: у меня какие-то соображения были, но я не до конца понимаю условие. Было бы хорошо формализовать его. Какими свойствами должен обладать граф, на котором всё происходит? Может ли он быть сферическим или торическим, например? Неоднозначность несколько сбивает с толку.

Для случая движения по клетчатой бумаге я знаю решение, но тут случай явно более общий.

(1 Апр '18 19:53) falcao

@falcao, я думаю тут имеется случай на клетчатой бумаге, поскольку мы не изучали сферические и торические графы. Не могли бы Вы, пожалуйста, объяснить этот случай?

(1 Апр '18 20:29) Hector

@Hector: я бы на это в первую очередь и подумал, если бы не замечание, что улицы не обязательно прямые. В принципе, могу хоть сейчас написать решение для "клетчатого" случая.

(1 Апр '18 20:33) falcao

@falcao, тогда не могли бы Вы написать решение для этого случая, пожалуйста?

(1 Апр '18 21:00) Hector
10|600 символов нужно символов осталось
1

Для клетчатой бумаги решение такое. Раскрасим узлы в шахматном порядке. Пусть мы проехали по горизонтальной улице от красного узла к синему. Тогда после поворота мы едем по вертикальной улице от синего узла к красному, и так далее.

Рассуждая от противного, рассмотрим первый момент, когда мы должны проехать какой-то отрезок в обратном направлении. Мы ехали от A к B, скажем, вверх. Потом повернули направо от B к C (это не ограничивает общности). В какой-то момент приехали снова в B, и после поворота готовы ехать от B к A. Получается, что мы приехали к B слева (если рассуждать относительно карты, где всё изображено). Но вершина B красная (так как к ней от A ехали вертикально), поэтому горизонтально мы к ней подъехать не могли. Противоречие.

Для общего случая соображения должны быть какие-то похожие, скорее всего. Но тогда надо знать точную формулировку.

ссылка

отвечен 1 Апр '18 21:17

Спасибо большое!

(1 Апр '18 21:27) Hector
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×310

задан
1 Апр '18 4:57

показан
287 раз

обновлен
1 Апр '18 21:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru