Question

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

Answer 1

Ответ:

501

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

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

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

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

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

Answer 2

Предположим, что ПрограМиша выбрала какую-то карточку с числом X. Чтобы удовлетворить условию задачи (чтобы ни одно число на выбранных карточках не равнялось сумме чисел на двух других выбранных карточках), она не может выбрать карточку с числом X2 (потому что это означало бы, что X + X = X2).

Аналогично, если ПрограМиша выбрала карточки с числами X и Y, то она не может выбрать карточку с числом X + Y (потому что это означало бы, что X + Y = X + Y).

Таким образом, каждая выбранная карточка исключает две другие карточки (та, которая имеет число в два раза больше, и та, которая имеет сумму чисел на двух других карточках). Исходя из этого, ПрограМиша может выбрать максимум N/3 карточек, где N - общее количество карточек (в данном случае, N = 1001).

Таким образом, максимальное количество карточек, которое ПрограМиша может выбрать, чтобы удовлетворить условию задачи, равно 1001/3 = 333 карточкам.