Информация о задаче

Задача 78269

Темы:	[	Последовательности (прочее)	]
Темы:	[	Принцип крайнего (прочее)	]

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

Прислать комментарий

Условие

Доказать, что для любых трёх бесконечных последовательностей натуральных чисел

a₁...	a_n	...
b₁...	b_n	...
c₁...	c_n	...

найдутся такие номера p и q, что

a_p $\displaystyle \ge$ a_q, b_p $\displaystyle \ge$ b_q, c_p $\displaystyle \ge$ c_q.

Решение

Докажем сперва, что из любой последовательности натуральных чисел можно выбрать неубывающую подпоследовательность, т. е. такую, что каждый её член не меньше предыдущего. Пусть x₁, x₂,..., x_n, ... — произвольная последовательность натуральных чисел. Так как все члены последовательности неотрицательны, то среди них существует наименьший — пусть это будет х_р. Если среди членов х_{р + 1}, x_{p + 2},..., следующих за х_р, число, равное х_р, встречается бесконечно много раз, то, выбрав все такие члены, мы уже получим требуемую подпоследовательность. Если же таких членов лишь конечное число, то выберем их все. Из идущей после последнего выбранного члена (равного х_р) части последовательности снова выберем наименьшее число x_p₁ (оно, очевидно, будет больше х_р) и все члены, равные x_p₁, и так далее; получим неубывающую последовательность:

x_p, x_p,..., x_p, x_p₁, x_p₁,..., x_p₁, x_p₂,....

Перейдём к решению задачи. Выберем из последовательности a₁, a₂,..., a_n,... неубывающую подпоследовательность:

a^'₁, a^'₂,..., a^'_n,....

Из соответствующей последовательности b^'₁, b^'₂,..., b^'_n,...:

$\displaystyle \begin{matrix}a_{1}, &a_{2},&\dots, &a^{'}_{1}, &\dots, &a^{'}_{... ...&\dots, &b^{'}_{1}, &\dots, &b^{'}_{2},&\dots,&b^{'}_{n}, & \dots \end{matrix}$

в свою очередь выберем неубывающую подпоследовательность:

b^''₁, b^''₂,..., b^''_n,...

Наконец, выберем неубывающую подпоследовательность из соответствующей последовательности c^''₁, c^''₂,..., c^''_n,...:

c^'''₁, c^'''₂, l..., c^'''_n,....

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

$\displaystyle \begin{matrix} a^{'''}_{1},& a^{'''}_{2},&\ldots,&a^{'''}_{n}, &... ...,\\ c^{'''}_{1},& c^{'''}_{2},&\ldots,&c^{'''}_{n}, & \ldots . \end{matrix}$

Все они не убывают (по построению) и, значит, для любых p, q (р > q) имеют место неравенства:

a^'''_p $\displaystyle \ge$ a^'''_q, b^'''_p $\displaystyle \ge$ b^'''_q, c^'''_p $\displaystyle \ge$ c^'''_q.

Мы, таким образом, доказали даже больше, чем требовалось в задаче.

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


олимпиада
Название	Московская математическая олимпиада
год
Номер	24
Год	1961
вариант
	1
Класс	10
Тур	2
задача
Номер	1