Оценка + пример

Подсказка 1:

Хочется получить сначала хотя бы какую-то оценку, чтоб понимать, в каком направлении двигаться. Какая самая простая ситуация, когда на столе не "много камней"?

Подсказка 2:

Когда на столе просто нет 50 кучек, то есть их ≤ 49. Сколько камней необходимо удалить, чтоб осталось ≤ 49 кучек?

Подсказка 3:

51 * 100 = 5100, то есть имеем оценку на 5099. Пока что остановимся. Подумаем, как вообще можно доказать, что существует требуемая нумерация кучек?

Подсказка 4:

Пока что не особо ясно. Можно попробовать ввести обозначения, хуже точно не будет) Пусть 0 ≤ a₁ ≤ a₂ ≤ ... ≤ a₉₉ ≤ a₁₀₀ ≤ 100 — количество камней в кучках после удаления какого-то количества камней. Как проверить много ли камней на столе?

Подсказка 5:

Проверить, подходят ли кучки a₅₁, ..., a₁₀₀ под нумерацию (осознайте)? То есть хотим доказать, что a₅₁ ≥ 1, a₅₂ ≥ 2, ..., a₁₀₀ ≥ 50 или же a₅₀₊ᵢ ≥ i. Доказывать, что можно, хотя мы ещё до конца не знаем оценку — так себе идея. Как нужно поменять логику рассуждений?

Подсказка 6:

Необходимо предположить противное и понять, при каком минимальном количестве удалённых камней нельзя выполнить нумерацию. Тогда наша итоговая оценка будет зажата в промежутке. Итак, предположим противное, что получаем?

Подсказка 7:

Для некоторого i a₅₀₊ᵢ ≤ i − 1. Как это влияет на предыдущие кучки?

Подсказка 8:

Во всех предыдущих кучках ≤ i − 1 камней. То есть всего в них ≤ (50 + i) * (i − 1). Сколько же тогда в них отсутствует камней?

Подсказка 9:

Осознайте самостоятельно, что удалено ≥ 5100 камней. Кажется, осталось сделать совсем немного. Мы в Вас верим!