Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа

$k$ санының қандай ең кіші мәнінде, 1-ден 100-ге дейінгі кез келген натурал $n$ саны үшін, ара-қашықтығы $2^n$-не тең болатын екі нүкте табылатындай, сандық өсте $k$ нүктені белгілей аламыз? ( И. Рубанов )

Комментарий/решение

Пример. Прик k = 101 можно отметить точки 2, 22, 2101: для каждого п от 1 до 100 расстояние от 2 до 2 ^ (n + 1) равно 2".

Оценка. Пусть отмечено k < 101 точек. Для каждого п от 1 до 100 соединим ниткой две точки на расстоянии 2^n. Если есть точка, из которой выходит ровно одна нитка, удалим ее вместе с ниткой и будем делать так до тех пор, пока это возможно. Таким путем мы сможем удалить не больше 99 вершин, а, значит, и ниток. Поэтому, когда процесс удаления закончится, из каждой точки либо не будет выходить ниток, либо будет выходить не меньше двух ниток. Возьмем точку, из которой выходит хотя бы две нитки, и пойдем из нее по ниткам, идя каждый раз в точку, где мы еще не были, пока это возможно. Когда мы попадаем в еще не пройденную точку, мы можем идти дальше, так как из нее выходит еще хотя бы одна нитка. Так как точек конечное число, когда-то мы придем в точку, где уже были, и получим замкнутый маршрут. Возьмем в нем самую длинную нитку. Так как 2^k > 2^(k - 1) + 2^(k - 2) +...+2^1 , эта нитка длиннее суммы всех остальных пройденных. Но тогда мы, выйдя из одного ее конца, не сможем прийти по остальным ниткам маршрута в другой. Получили противоречие с замкнутостью маршрута, доказывающее, что k >= 101

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