Ваня обнаружил некоторую закономерность. Он записал по кругу 27 чисел, таких, что в каждой паре соседних чисел одно делится на другое. И тогда в этом круге он всегда мог найти пару и не соседних чисел с таким же свойством. Но он не уверен, что для большего количества нечётных чисел это будет верно. Докажи, что эта закономерность будет верна для любого количества нечётных чисел, удовлетворяющих условию. Доказательство: пусть числа, стоящие по кругу, будут графа. Соединим их рёбрами по кругу. Зададим направление рёбрам, от делимого к делителю. Общее количество рёбер нечётно, поэтому их направления . А значит, какие-то два соседних ребра имеют одно направление. a→b→c. Это означает, что a делится на b, а b делится на c. Отсюда следует, что . Значит, такую пару чисел можно будет найти для любого количества нечётных чисел, удовлетворяющих условию.

Чтобы понять доказательство Вани и убедиться в его справедливости для любого количества нечётных чисел, рассмотрим шаги более подробно: ### Шаг 1: Определение графа Ваня представил числа, которые находятся по кругу, в виде графа. В этом графе каждое число представляет собой вершину, а рёбра соединяют соседние числа. Если одно число делится на другое, то можно провести направленное ребро от делимого к делителю. ### Шаг 2: Направление рёбер Учитывая, что у нас 27 чисел (нечётное количество), количество графов (рёбер) по кругу также будет нечётным. Это значит, что всего рёбер нечетно. Направление рёбер зависит от того, делится ли одно число на другое. Поскольку для любого делимого числа a существует divisor b (число, на которое он делится), и наоборот, мы можем нарисовать все рёбра, связанными с этим свойством. ### Шаг 3: Применение принципа дырявой шапки Поскольку количество рёбер нечётно, то при наложении направления (от делимого к делителю) по кругу возникает ситуация, когда какое-то направление повторяется. Это следует из того, что "нечётное количество" направлений не может быть однородно распределено по "парному" принципу (если бы мы пытались сделать так, чтобы каждое направление соседнего ребра было различным). ### Шаг 4: Нахождение состояний Если два соседних ребра имеют одно направление, например, a → b и b → c, то это значит, что: - a делится на b, - b делится на c. Если b делится на a, это значит, что мы нашли пару (a, c) с соблюдением условия делимости (a делится на c). Таким образом, мы можем утверждать, что каждая такая конфигурация в круге повторяется, и мы всегда сможем найти пару чисел, которые удовлетворяют условию. ### Шаг 5: Обобщение на любое нечётное количество чисел Доказательство, основанное на структуре графа и использовании нечётного количества рёбер, говорит о том, что эта закономерность будет верна для любого количества нечётных чисел. Мы можем использовать аналогичную логику для 3, 5, 7 или любого больше числа нечётных чисел, что всегда будет приводить к образованию пар, соблюдающих условия. ### Заключение Таким образом, Ваня доказал, что если он располагает нечетным количеством чисел в круге с заданными свойствами делимости, то он всегда сможет найти пару чисел, которая будет делиться друг на друга, независимо от размера множества. Доказательство основано на графической модели и свойствах нечётности, проявляющейся в структуре направленных рёбер, что и позволяет свести проблему к базовой логике!