Пусть [n] - число из n единиц. Тогда произведение k идущих подряд чисел из этой последовательности делится на произведение первых k членов этой последовательности.

задан 22 Сен '15 2:37

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

Давайте вместо $%[a]$% рассматривать число $%9[a]=10^a-1$%. Поскольку при делении девяток в числителе и знаменателе будет поровну, то все они сократятся. Итак, нам нужно доказать, что произведение $%(10^{m+1}-1)...(10^{m+k}-1)$% при каждом $%k$% делится на аналогичное произведение при $%m=0$%.

Доказываем делимость по индукции. База при $%m=0$% очевидна, так как частное равно 1. Пусть мы уже всё доказали для всех меньших $%k$% и для всех меньших $%m$%.

В частности, $%A=(10^{m}-1)...(10^{m+k-1}-1)$% делится на $%a=(10^{1}-1)...(10^{k}-1)$% и $%B=(10^{m+1}-1)...(10^{m+k-1}-1)$% делится на $%b=(10^{1}-1)...(10^{k-1}-1)$%.

Тогда $$A' - A = (10^{m+1} - 1)\dots(10^{m+k} - 1) - (10^{m} - 1)\dots(10^{m+k-1} - 1) = $$ $$=B(10^{m+k}-1) - B(10^m - 1) =10^m B(10^k - 1)$$ делится на $%a=(10^k-1)b$%, потому что $%B$% делится на $%b$%, а множитель $%10^k-1$% сам на себя. Но так как $%A$% делится на $%a$%, то и $%A'$% делится на $%a$%, что и доказывает справедливость индукционного перехода.

ссылка

отвечен 22 Сен '15 17:29

@knop: очень красиво получилось! Фактически, доказан более общий факт насчёт делимости многочленов.

(22 Сен '15 17:49) falcao
1

@falcao, и даже не только многочленов. Фактически всё, что мне от функции (которая в данном случае $%[x]$% или $%10^x-1$%) нужно, - это

а) f(x) делится на f(1)

б) f(x+y)-f(y) делится на f(x).

(23 Сен '15 0:47) knop
1

Также см. решение задачи М2166 на стр. 22-23 вот тут http://kvant.mccme.ru/pdf/2010/2010-04.pdf

(24 Сен '15 16:42) knop
10|600 символов нужно символов осталось
1

Не знаю на сколько предложенное будет полным решением, но мысль такая...

Очевидно, что $%[k\cdot n]$% делится на $%[n]$% ... заметим, что среди чисел $%N+1,\ldots , N+k$% всегда есть число, кратное $%n \in \{1,\ldots , k\}$% ... то есть в произведении $%[N+1]\cdot\ldots\cdot[N+k]$% всегда есть число, которое делится на один из множителей произведения $%[1]\cdot\ldots\cdot[k]$%...
Ну, и видимо для соответствия между множителями этих произведений нужно показать, что для взаимно простых $%n_1$% и $%n_2$% число $%[n_1\cdot n_2]$% делится на $%[n_1]\cdot[n_2]$% ...

ссылка

отвечен 22 Сен '15 3:57

Про взаимную простоту полезно вспомнить раньше. А именно, сказать, что если $%НОД(a,b)=1$%, то $%НОД([a],[b])=НОД(10^a-1,10^b-1)/9 = 1$%. Последнее вроде достаточно известный факт.

(22 Сен '15 9:20) knop

@all_exist: я пытался рассуждать примерно таким же образом, но пока не могу довести идею до конца. Рассмотрим такой пример: произведение чисел от 21 до 26 делится на произведение чисел от 1 до 6. При этом из верхнего списка только 24 делится и на 4, и на 6. Поэтому мы не может устроить такое соответствие, где множители оказались бы взаимно простыми. В частности, число из 24 единиц не делится на произведение числа из 6 единиц и числа из 4 единиц. То есть тут необходимо какое-то усиление.

(22 Сен '15 16:56) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×590

задан
22 Сен '15 2:37

показан
291 раз

обновлен
24 Сен '15 16:42

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

по почте:

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

по RSS:

Ответы

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

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