4. По окружности расставлены n натуральных чисел. Между каждыми двумя соседними числами записывают наименьшее из них. После этого исходные числа стирают, а с оставшимися проделывают то же самое. Докажите, что через несколько шагов все числа станут равными.

Пронумеруем места по окружности и обозначим начальные числа через \(a_i\), где индексы понимаются по модулю n. После первого шага на месте между \(a_i\) и \(a_{i+1}\) будет \(\min(a_i,a_{i+1})\).

После k шагов число на соответствующем месте равно минимуму чисел в последовательном блоке из \(k+1\) исходных соседних чисел. Это следует индукцией: следующий шаг берёт минимум двух соседних значений, то есть минимум объединения соответствующих блоков.

При \(k=n-1\) каждый такой блок содержит все n чисел окружности. Поэтому на каждом месте окажется одно и то же число — минимум исходных чисел.

Ответ: не позднее чем через n − 1 шагов все числа станут равными.