Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

решение задачки

Решение задачи про последовательность натуральных чисел.

(на самом деле 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.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments