?

Log in

No account? Create an account
решение задачки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

решение задачки [фев. 9, 2003|10:57 pm]
Anatoly Vorobey
Решение задачи про последовательность натуральных чисел.

(на самом деле abys дал там в комментах работающее решение, но я сейчас за элжекатом приведу более лёгкое, или более простое для понимания, точнее).



Итак, у нас есть последовательность натуральных чисел nk, так, что nk+1 > nnk для всех k, и мы хотим доказать, что nk=k для всех k.

Предположим сначала, что мы уже знаем, что наша последовательность монотонно возрастает, т.е. каждый следующий член строго больше предыдущего. Тогда, с одной стороны, будет выполняться nk >= k (т.к. последовательность начинается с числа >=1 и увеличивается как минимум на 1 на каждом шаге). С другой стороны мы знаем, что nnk < nk+1 по условию, но из неравенства этих членов следует неравенство индексов (опять-таки ввиду монотонности), то есть nk < k+1 . Но тогда nk может быть равным только k, что и требовалось доказать.

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

Докажем теперь, что n1 меньше всех остальных членов последовательности. Это просто: любой другой член последовательности имеет форму nk+1, и поэтому есть кто-то меньше его -- а именно, nnk, по условию. Поэтому наименьшим может быть только n1, и он тогда строго наименьший.

Теперь выбросим n1 из последовательности, а все оставшиеся члены уменьшим на 1. Покажем, что получившаяся последовательность n2-1, n3-1, ... выполняет те же условия, что и первоначальная. Она всё ещё состоит из натуральных чисел, т.к. все nk+1 были строго больше n1, а значит и больше 1. И если мы обозначим члены этой новой последовательности через m1,m2,... , то будет выполняться условие mmk < mk+1: в терминах первоначальной последовательности это неравенство выглядит как n(nk+1-1)+1-1 < nk+2-1, т.е. nnk+1 < nk+2, т.е. следует из первоначального условия.

Но тогда мы сразу видим, что мы можем и в этой последовательности показать, что первый член меньше всех остальных, из чего следует, что n2 < nk для всех k>2; затем, убрав ещё раз первый член и уменьшив всех на 1, получаем опять последовательность, выполняющую первоначальные условия итп. Продолжая по индукции, видим, что каждый член последовательности nk меньше всех следующих, что и даёт нам желанную монотонность, из которой следует nk=k.
СсылкаОтветить

Comments:
[User Picture]From: princeska
2003-02-09 01:33 pm

Прикол какой :))
(Ответить) (Thread)
From: finger6
2003-02-10 01:12 am
круто
(Ответить) (Thread)
[User Picture]From: flaass
2003-02-10 08:53 am

Napomnila

ona mne odnu klassicheskuju zadachku, chudo kak krasivuju.

a,b - polozhitel'nye irracional'nye chisla,
1/a+1/b=1.
Dokazat', chto ljuboe natural'noe chislo ravno libo [na], libo [nb] (dlja kakogo-to natural'nogo n).
[] - eto celaja chast'.
A "libo..., libo..." - eto iskljuchajushhee "ili" :)
(Ответить) (Thread)