В стране гномов есть 200 пещер, некоторые из них соединены тоннелями. Начиная с 1 января 2019 года, гномы засыпают все старые тоннели и роют новые между каждой парой пещер, с которых накануне выходило одинаковое количество тоннелей. В некоторых N пещерах живет по одному супергному. При каком самом маленьком N некоторые два из них когда-либо смогут встретиться?

Предыдущий
вопрос Следующий
вопрос

Сначала заметим, что количество новых тоннелей, которые роют гномы каждый день, равно сумме 1 + 2 + ... + 199 = 19900. Так как каждый новый тоннель соединяет две пещеры, и все пещеры должны быть соединены, то общее количество пещер должно быть равно сумме арифметической прогрессии 1 + 2 + ... + n, где n - количество пещер.

Эту сумму можно найти по формуле Sn = n(n+1)/2. Таким образом, n(n+1)/2 = 19900, откуда n^2 + n - 39800 = 0. Решив это квадратное уравнение, получаем n ≈ 199.68.

То есть самое маленькое целое значение N, при котором два супергнома когда-либо встретятся, равно 200.