Задача
COM-B2-M04-P002 Стрелки и цикл
#2
★★☆☆☆ Уровень 2 из 5
В конечном множестве точек из каждой точки проведена стрелка в одну из других точек. Докажите, что можно пройти по стрелкам и попасть в цикл.
Начните из любой точки и записывайте последовательность посещённых точек.
Начнём с произвольной точки \(v_1\) и каждый раз будем переходить по стрелке: \(v_1,v_2,v_3,\ldots\). Точек конечное число, поэтому какая-то точка повторится: \(v_i=v_j\) при \(i Тогда отрезок последовательности \(v_i,v_{i+1},\ldots,v_{j-1},v_j=v_i\) образует цикл по стрелкам. Значит, такой цикл существует.
Можно обсудить как вариант экстремального принципа: бесконечное продолжение в конечной системе невозможно без повторения.