Как решать задачу на делимость

Irbis-S

Подскажите плз общую идею как сделать.
По индукции никак что-то не получается
Доказать, что произведение N любых последовательных натуральных чисел делится на N! (N-факториал)

sverum

С_n^k = n!/(k!*(n-k)!) = n - k + 1)*...*n)/k!
В числителе k последовательных чисел.

seeknote

del

Irbis-S

а как тут применить сочетания ?
в двух словах, если можно

sverum

Если непонятно, то подожди, сейчас придет FrauSoboleva и придумает более изящное решение :)

mab1

куда уж изящнее?

Irbis-S

Ага, все понял.
И в самом деле, очень просто.
Спасибо.

fatality

очень элегантно. но результат очевиден и сам по себе - ближайшие друг к другу целые, делящиеся на k, отличаются друг от друга на k (и поэтому кратные всех k от 1 до n, входящих в факториал, представлены в произведении из n последовательных целых).

DarkDimazzz

Но из делимости на 2, 3...n не следует делимость на n! (например, делимость на 2, 3 и 4 равносильна делимости на 12, откуда, очевидно, не следует делимость на 4!=24).

Sergey79

Мне кажется, здесь речь не о делимости всего произведения, а о делимости множителей произведения на множители факториала.

fatality

да, конечно, вместо делимости на n! я доказал делимость на все его сомножители (от 1 до n) - к моменту написания ответа ступил/забыл про условие. в качестве кратных различных степеней (простого) р, являющихся сомножителями n!, очевидно, можно выбирать попарно различные сомножители в нашем произведении. обоснование возможности такого выбора для сомножителей n!, содержащих p и не являющихся такими степенями, вроде бы несложно из тех же соображений (см пример) :)
n! = 8! = 1*(2)*3*(2^2)*5*(2*3)*7*(2^3)
П = 10*11*12*13*14*15*16*17
10 = 2*5
12 = (2^2)*3
14=2*7
16= (2^3)*2
То есть р входит в n последовательных натуральных в тех же степенях и таким же образом, что и в последовательность 1..n (с точностью до сдвига начала)

toxin

Можно доказать по индукции. Если верно для n-1, то доказываем для n индукцией по первому числу в произведении. Соседние произведения отличаются на n*произведение последовательных n-1 чисел, что делится на n! по предположению индукции, а поскольку первое из них равно n!, то и все они делятся на n!.
Оставить комментарий
Имя или ник:
Комментарий: