Задача на теорию чисел Аня выписала на доску все натуральные числа от 1 до 5000, а затем Боря стёр какие-то k из них. При каком наибольшем k можно гарантировать, что среди оставшихся на доске чисел обязательно найдётся 31 число, одно из которых равно сумме тридцати остальных?

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

Предположим, что можно гарантировать нахождение такого числа, и рассмотрим следующие рассуждения.

Сумма чисел от 1 до 5000 равна 5000*5001/2 = 12502500. Так как по условию среди оставшихся чисел обязательно найдется 31 число, одно из которых равно сумме 30 остальных, то эти 31 число будут равны в сумме половине от общей суммы чисел от 1 до 5000, то есть 6251250.

Получается, что сумма оставшихся на доске чисел будет равна 6251250, и мы исключили k чисел из общего списка. Таким образом, чтобы гарантировать нахождение числа, равного сумме 30 остальных, число 31 должно быть в пределах от 1 до 5000 - k.

Если k = 31, то число 31 входит в интервал от 1 до 4969, следовательно, это наибольшее значение k, при котором можно гарантировать нахождение числа, равного сумме 30 остальных.