У ПрограМиши есть 1001 карточка с числами от 1 до 1001 (все карточки с разными числами). Какое максимальное количество карточек может выбрать ПрограМиша, чтобы ни одно число на выбранных карточках не равнялось сумме чисел на двух других выбранных карточках?
Ответы
Ответ дал:
0
Ответ:
501
Пошаговое объяснение:
Рассмотрим самое большое из чисел, которые написаны на выбранных карточках. Пусть оно равно N. Тогда дополнительно можно выбрать не больше N : 2 карточек.
В самом деле, все числа, меньшие N, разбиваются на пары вида (X, N - X), и в каждой паре можно взять не более одного числа, так как сумма чисел в каждой паре равна N. Если N чётное, то возникнет еще одно число, равное N : 2, его тоже можно взять.
Наибольшее число, которое может оказаться на выбранной карточке, равно 1001, тогда всего можно выбрать не более 1 + 500 = 501 карточки.
501 число можно выбрать так: просто взять все карточки с нечетными числами, сумма любых двух из них четная, а потому соответствующая карточка не выбрана.
Вас заинтересует
1 год назад
6 лет назад
6 лет назад