16

Задача: найдите минимальное N такое, что если из чисел 1,2,3...,N убрать любые 1000 чисел, то из оставшихся можно выбрать ровно 1000 чисел с суммой N.

Сначала хотела написать код, чтобы получить ответ, но поняла, что не представляю, как он должен выглядеть в данной ситуации.

Вручную сделала грубую оценку, получила что это число должно быть чуть больше миллиона, но не знаю, какое это число и не знаю, как доказать, что оно наименьшее.

9
  • 13
    Не понимаю закрывающих... 3 голоса за "надо конкретизировать". Что вам непонятно? Задача-то интересная, обидно будет, если вопрос будет закрыт... Кстати, мне кажется, что ответ 1500500, но вот как это доказать?
    – Harry
    12 мар 2023 в 10:23
  • 1
    Грубая оценка всё же больше полутора миллионов. Сумма чисел от 1001 до 2000.
    – Alexey Ten
    12 мар 2023 в 10:30
  • 1
    @AlexeyTen Она и есть 1500500. И ощущение, что она и есть ответ. Нет?
    – Harry
    12 мар 2023 в 10:35
  • Да, похоже. Но строгое доказательство пока не сочиняется
    – Alexey Ten
    12 мар 2023 в 10:48
  • @AlexeyTen Отож... вроде какое число из этой суммы не вычеркни — а можно подобрать ему пару так, что эта же сумма получится другой парой... Но, увы, это так, рассуждения, но не строгое доказательство.
    – Harry
    12 мар 2023 в 10:51

1 ответ 1

24

Очевидно, что требуемое 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

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.