Поиск минимального значения суммы последовательности по условию (доказательство)
Задача: найдите минимальное N такое, что если из чисел 1,2,3...,N убрать любые 1000 чисел, то из оставшихся можно выбрать ровно 1000 чисел с суммой N.
Сначала хотела написать код, чтобы получить ответ, но поняла, что не представляю, как он должен выглядеть в данной ситуации.
Вручную сделала грубую оценку, получила что это число должно быть чуть больше миллиона, но не знаю, какое это число и не знаю, как доказать, что оно наименьшее.
Ответы (1 шт):
Очевидно, что требуемое N не меньше 1500500. Т.к. это минимальная сумма 1000 чисел при вычёркивании 1000 чисел от 1 до 1000.
1001 + 1002 + ... + 2000 = 1500500.
Докажем что это требуемое число. Разобьём первые 3000 чисел на пары:
1,3000;2,2999;3,2998;- …
1500,1501.
Получим 1500 пар, причём сумма чисел в каждой из пар равна 3001.
После вычёркивания 1000 чисел, у нас точно останется не менее 500 пар в которых оба числа не вычеркнуты. Сумма чисел этих 500 пар даст нам 3001 * 500 = 1500500.
QED