Домашка на 5 июня

Минотавр живет и работает в лабиринте. В каждой комнате лабиринта соединяются ровно три коридора. Минотавр начал обходить лабиринт из главной комнаты, руководствуясь следующим правилом: если в предыдущей комнате поворачивал налево, то в этой – направо, и наоборот. Докажите, что когда-нибудь минотавр снова окажется в главной комнате.

Задача несколько открытая. Придется делать предположения и при этих предположениях решать (например, главная комната не должна короткой петлей замыкаться сама на себя и т.д.)

==========================================

В стране N городов, некоторые города соединены дорогами, причём из каждого города выходит ровно 3 дороги. Известно, что по дорогам страны можно добраться из любого города в любой другой город этой страны, заезжая по пути не более чем в 1 другой город. Какое наибольшее количество городов может быть в этой стране?

Ответ задачи говорит, что 10. Я смог найти реализацию графа из 8 городов. Из 10-ти найти не смог... Мне кажется, что в ответе ошибка. Но тогда надо доказать...

Последнее изменение: Воскресенье, 29 мая 2022, 10:00