Олимпиада 7 класс

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

Для решения данной задачи мы можем воспользоваться свойством двудольных графов.

Определение задачи

Мы имеем магический замок с миллионом комнат, каждая из которых соединена с другими комнатами с помощью лестниц и порталов. Каждая комната имеет ровно одну лестницу и один портал, что означает, что каждая комната связана с двумя другими комнатами: одна через лестницу и одна через портал.

Модель графа

Мы можем представить комнаты как вершины графа, а лестницы и порталы как ребра. Поскольку в каждой комнате есть ровно одна лестница и один портал, то:

- Лестницы образуют один набор рёбер (граф).
- Порталы образуют другой набор рёбер (граф).

Таким образом, мы имеем два различных графа: один, состоящий из рёбер лестниц, и другой — из рёбер порталов.

Доказательство двудольности

Шаг 1: Построение графа

Пусть G_L — граф, представляющий комнаты и лестницы, а G_P — граф, представляющий комнаты и порталы. Каждый из этих графов является циклическим или деревом, поскольку каждая комната соединена с двумя другими.

Шаг 2: Двудольность графов

Графы G_L и G_P можно раскрасить в два цвета следующим образом:

1. Цвета: Назовем два цвета "черный" и "белый".
2. Раскраска:
- Начнем с произвольной комнаты (вершины) и раскрасим её черным.
- Все комнаты, связанные с ней лестницей (через рёбра G_L ), будут раскрашены в белый.
- Все комнаты, связанные с белыми комнатами через порталы (через рёбра G_P ), будут снова черными.
- Продолжим этот процесс до тех пор, пока не раскрасим все комнаты.

Шаг 3: Проверка условия

При таком раскрашивании:
- Комнаты одного цвета будут соединены только через ребра другого цвета. Это значит, что для перехода из одной комнаты в другую одной и той же окраски необходимо будет пройти через комнату другого цвета.
- Следовательно, нельзя попасть в комнату того же цвета без посещения другой комнаты.

Заключение

Таким образом, мы доказали, что комнаты в магическом замке можно раскрасить в два цвета так, чтобы ни из одной комнаты нельзя было попасть в комнату того же цвета, не посетив другую. Это достигается благодаря тому, что графы лестниц и порталов являются двудольными.