Задача 60354

Тема:    [ Принцип Дирихле (прочее) ]

Сложность: 4- Классы: 8,9,10

Условие

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

Решение

Если взять все карточки с нечётными номерами (их  k + 1) , то условие будет выполнено. Если взять  k + 2  карточки, то, вычитая из наибольшего их номера N все остальные, мы получим  k + 1  различное число. Все эти числа не превышают  2k, поэтому хотя бы два из них совпадут с номерами на
 k + 2  выбранных карточках. По крайней мере один из этих двух номеров не равен ^N/₂.

Ответ

k + 1  карточку.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	2
Название	Принцип Дирихле
Тема	Принцип Дирихле (прочее)
задача
Номер	02.020