решение задачки
Feb. 9th, 2003 10:57 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaРешение задачи про последовательность натуральных чисел.
(на самом деле![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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.
(на самом деле
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.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
no subject
Date: 2003-02-10 01:12 am (UTC)Napomnila
Date: 2003-02-10 08:53 am (UTC)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" :)