С натуральным числом, написанным на доске, разрешается проделать такую операцию: умножить его на выражение $%(p-1)^2/p$%, где $%p$% - его простой делитель, и записать результат вместо исходного числа. Докажите, что, какое бы исходное число мы ни взяли и как бы мы ни проделывали описанные операции, на доске рано или поздно появится число $%1$%.

задан 29 Апр '16 21:13

10|600 символов нужно символов осталось
1

Число p-1 раскладывается на простые множители, каждый из которых строго меньше p. В итоге мы на каждом шаге заменяем один из множителей на некоторое множество меньших, а p=2 вообще исчезает. Можно разрешить более общее преобразование, позволяющее заменять любое простое p на произведение меньших простых чисел в любом количестве. Хотя общее число сомножителей при этом может увеличиваться, результатом всё равно будет 1 через конечное число шагов. Такое более общее утверждение и будем доказывать.

Представим себе этот же процесс в несколько ином виде. Пусть число равно $%2^{k_1}3^{k_2}5^{k_3}...p_n^{k_n}$% для некоторых $%k_i\ge0$%, где $%p_i$% обозначает $%i$%-е простое число. Вместо такого числа можно рассматривать набор показателей: $%(k_1,k_2,...,k_n)$%. За один ход можно уменьшить на 1 одно из положительных чисел этого набора, а предыдущие числа как угодно изменить. Например, вместо набора (7,1,0,0,2,3) можно рассмотреть набор (2016,100,5555,999,1,3), уменьшая 2 на единицу. Такой процесс может продолжаться очень долго, но он не может длиться бесконечно. Докажем, что любой набор за конечное число шагов станет нулевым, и процесс на этом окончится.

Будем применять индукцию по длине набора, а при фиксированной длине $%n$% -- по последнему числу $%k_n > 0$%. При $%n=1$% у нас всего одно число, которое разрешается уменьшать на 1, и при этом ничего не увеличивается, потому что предыдущих чисел нет. Такой процесс окончится ровно через $%k_1$% ходов.

Теперь пусть $%n > 1$%, где $%k_n > 0$%. Длина набора не увеличивается, и если мы на каком-то шаге уменьшим $%k_n$%, то далее по предположению индукции число шагов процесса будет конечным. Действительно, у нас или уменьшится длина набора (при $%k_n=1$%), либо длина останется прежней, но уменьшится само число $%k_n$%.

Если же $%k_n$% ни на каком шаге не уменьшается, то мы фактически работаем с набором меньшей длины. Тогда по предположению индукции набор $%(k_1,...,k_{n-1})$% рано или поздно станет нулевым, и нам ничего не останется кроме как начать уменьшать $%k_n$%, что было разобрано выше.

Задача мне по своему характеру напомнила известную задача про Геркулеса и гидру, где речь также идёт об оканчивающемся за конечное число шагов процессе. Но там решение существенно более сложное.

ссылка

отвечен 30 Апр '16 0:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×245

задан
29 Апр '16 21:13

показан
876 раз

обновлен
30 Апр '16 0:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru