Карточки с числами, выбрать максимальное количество...

[Katrin_M]

Имеется 2011 карточек, занумерованных числами от 1 до 2011. Какое наибольшее число карточек можно выбрать так, чтобы ни один из извлеченных номеров не был равен сумме двух других извлеченных номеров?

Взять 1006 карточек можно как минимум двумя способами - либо взять все нечетные карточки (а ни одно нечетное число не равно сумме двух нечетных), либо взять карточки 1006, 1007, 1008, ... , 2011 (тогда сумма любых двух не меньше 1013).

Можно ли доказать, что больше нельзя? А может можно больше?

[Sonic86]

Пусть дано множество $M = \{ 1;2;...;2n+1\}$, содержащее $2n+1$ чисел. Возьмем $a,b \in M$. Мы уже знаем, что можем выбрать искомое множество $N$, содержащее $n+1$ элементов из $M$ так, что для любых $x,y \in M x+y \not \in M$. Далее возможны 2 варианта:
1. Для всех $a,b \in M$ сумма $a+b>2n+1$.
2. Существует пара $a,b \in M$ такая, что $a+b \leqslant 2n+1$.
Теперь можно попытаться сделать так: разобрать случай 1. В случае 2 рассмотреть сумму $s=a+b$. Ответить на вопрос: для любого $k: k \geqslant 0, s-k \geqslant 0$ возможно ли $\{ k;s-k \} \subset N$? Как ответ связан с оценкой $|M|$? Каково $\min\limits_{N \subset M, |N|=n+1} \max\limits_{a,b \in N}a+b$? Что можно отсюда вывести.
Но я пока не уверен - у меня еще у самого толком не получилось. Может это наведет Вас на какие-то мысли.

[Shadow]

Доказать, что n-наибольшее число елементов, удолв. условие для интервала $(1;2n-1)$
По моему нужно доказать, что среди n чисел в интервале (любых, даже не удолветворяющие условие) найдется сумма или 2n, или 2n+1. Ну кроме ряда 1,2,3....n. И тогда по индукции, при увеличении интервала с 2, оба елемента 2n и 2n+1, не могут попасть одновременно в M, может только один.

[Cash]

Цитата:

Доказать, что n-наибольшее число елементов, удолв. условие для интервала
По моему нужно доказать, что среди n чисел в интервале (любых, даже не удолветворяющие условие) найдется сумма или 2n, или 2n+1. Ну кроме ряда 1,2,3....n. И тогда по индукции, при увеличении интервала с 2, оба елемента 2n и 2n+1, не могут попасть одновременно в M, может только один.

Это неверно. Можно взять числа $6k+2, 6k+3, 6k+4$

Хотя нет. Наврал. $4+10=6\cdot 2+2$

[Shadow]

Cash в сообщении #489844 писал(а):

Это неверно. Можно взять числа $6k+2, 6k+3, 6k+4$

Простите, можно конкретыми числами дать пример. Так легче пойму в чем моя ошибка

[Cash]

Мне показалось что помимо нечетных чисел можно взять другую конструкцию с остатками по некоторому другому числу (я хотел по 6)

-- Ср окт 05, 2011 22:33:26 --

Получается примерно так.
Пусть $2k$ - наибольшее четное число данного множества. Тогда менее его во множестве не более $k$ чисел, иначе разбиваем на пары $(i,2k-i) и применяем принцип Дирихле. А свыше $2k$ - только нечетные. И если я опять не ошибся, то получим требуемую оценку.

[Cash]

И конечно же ошибся. На 1 больше получается. А вот если взять наибольшее нечетное число и провести те же рассуждения, то всё срастается.
Но можно ещё проще. Берем наибольшее число из множества - $k$, и видим, что множеству помимо него принадлежит не более $[k/2]$ чисел. Откуда и получаем требуемое.

[Shadow]

Все таки думаю, сама по себе задача интересная:
Доказать, что среди любых n различных натуралных числел в интервале $[1;2n-1]$, кроме $1,2,3...n$, всегда найдется пара, сумма которой либо $2n$, либо $2n+1$.
Доказательство от противного. Разделим чисел на маленьких $1,2,...n$ и больших $n+1,n+2,...2n-1$. Множество маленьких удовл. условие. Запишем для удобство множества так:
$n, n-1,n-2,....1$ маленькие
...$n+1,n+2,....2n-1$ большие
Включение любого большого числа исключает соответвуще ему маленькое по остатку, иначе получится сумма $2n$. n должно остаться, потому что не с чем его заменить. Следующее не может быть n+1, т.к получится сумма 2n+1. Должно быть n-1. Что исключает n+2...и т.д исключются все большие.
И к задаче ТС.
Рассмотрим интервал $[1;2n+1]$.
$2n,2n+1$ и еще n чисел не могут одновременно принадлежать M - доказано.
Т.е, если для интервала $[1;2n-1]$ в М могут входить не больше n, то для $[1;2n+1]$ в М могут входить не больше n+1.