Задача 60368

Темы:    [ Теория чисел. Делимость (прочее) ] [ Принцип Дирихле (прочее) ]

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

Условие

Докажите утверждение задачи 1.26 при помощи принципа Дирихле.

Решение

Рассмотрим n последовательностей

{1, 2, 4, 8,..., 2k,...}

{3, 6, 12, 24,..., 3 . 2k,...}

...........

{2n - 1,(2n - 1)2,(2n - 1)4,...,(2n - 1) . 2k,...}

Каждая из них имеет ровно один элемент на отрезке [n + 1;2n]. Значит, из n + 1-го выбранного числа хотя бы два окажутся в одной и той же последовательности.

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

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