|
Пусть [n] - число из n единиц. Тогда произведение k идущих подряд чисел из этой последовательности делится на произведение первых k членов этой последовательности. задан 22 Сен '15 2:37 
sapere aude |
|
Давайте вместо $%[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 @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
|
|
Не знаю на сколько предложенное будет полным решением, но мысль такая... Очевидно, что $%[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]$%... отвечен 22 Сен '15 3:57 
all_exist Про взаимную простоту полезно вспомнить раньше. А именно, сказать, что если $%НОД(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
|