Question

У ПрограМиши есть 1001 карточка с числами от 1 до 1001 (все карточки с разными числами). Какое максимальное количество карточек может выбрать ПрограМиша, чтобы ни одно число на выбранных карточках не равнялось сумме чисел на двух других выбранных карточках?

Answer 1

Ответ:

501

Пошаговое объяснение:

Рассмотрим самое большое из чисел, которые написаны на выбранных карточках. Пусть оно равно N. Тогда дополнительно можно выбрать не больше N : 2 карточек.

В самом деле, все числа, меньшие N, разбиваются на пары вида (X, N - X), и в каждой паре можно взять не более одного числа, так как сумма чисел в каждой паре равна N. Если N чётное, то возникнет еще одно число, равное N : 2, его тоже можно взять.

Наибольшее число, которое может оказаться на выбранной карточке, равно 1001, тогда всего можно выбрать не более 1 + 500 = 501 карточки.

501 число можно выбрать так: просто взять все карточки с нечетными числами, сумма любых двух из них четная, а потому соответствующая карточка не выбрана.