Высшая проба 2024, 11 класс, задача 5
( баллов) Деревни некоторой языческой страны соединены дорогами так, что от любой деревни можно добраться до любой другой не проходя ни через какую деревню дважды, причём сделать это можно единственным способом. В каждой деревне живёт своё племя туземцев. Каждое племя поклоняется одному из трёх идолов: Камню, Ножницам или Бумаге. Известно, что Камень сильнее Ножниц, Ножницы сильнее Бумаги, а Бумага сильнее Камня. Каждое племя желает, чтобы их идол был не слабее, чем идол любого из соседствующих с ними племён. С этой целью каждый вечер ровно в каждое племя смотрит на своих соседей и, если обнаруживает соседа с более сильным идолом, меняет свои верования, начиная поклоняться этому более сильному идолу. Верно ли, что рано или поздно все племена начнут верить в одного и того же идола?
Решение.
Верно. Рассмотрим граф, вершины которого отвечают племенам, а рёбра проводятся между вершинами, которые отвечают соседним племенам. Согласно условию, этот граф является деревом. Докажем утверждение задачи индукцией по — количеству вершин в дереве. База индукции при очевидна, так как в этой ситуации вообще не происходит смен вероисповедания единственного существующего племени.
Предположим, что мы уже доказали утверждение задачи для любого -вершинного дерева, покажем, что тогда оно верно и для любого -вершинного дерева . Пусть — произвольная висячая вершина дерева , и пусть она соединена с вершиной . Покажем, что ситуация, в которой идол сильнее идола , произойдёт не более чем один раз.
Действительно, пусть в какой-то момент произошла указанная ситуация. Тогда прямо после этого идол стал таким же, как идол . После этой ситуации идол менялся тогда и только тогда, когда идол становился сильнее него. При этом при изменении идола идол либо оставался неизменным, либо становился сильнее уже нового идола . Итак, в каждый момент времени будет происходить одна из двух ситуаций: либо у и одинаковый идол, либо идол слабее идола .
Значит, найдётся такой момент времени, после которого вершина вообще никак не влияет на то, как меняются идолы у остальных вершин, причём идол не сильнее идола . Тогда, согласно индукционному предположению, рано или поздно все вершины, кроме, быть может, , будут верить в одного и того же идола. В этот же момент времени идол не сильнее идола , потому на следующий день идолы у всех племён гарантированно будут одинаковыми
нет ничего кроме переформулировки на языке графов; неразвитой идеи индукции; неразвитой идеи рассматривать висячую вершину; верного ответа.