ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60354
Тема:    [ Принцип Дирихле (прочее) ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .