Доказать, что для целых $%a_1,a_2,...,a_n$% выражение $$\prod_{1\le i< j\le n}\frac{a_j-a_i}{j-i}$$ также целое число.

В книге "Сборник задач Московских математических олимпиад" (1935-1964), стр.245, есть такая подсказка:

Докажите, что для любого целого $%k$% число разностей $%(j-i)$%, делящихся на $%k$%, не больше числа разностей $%(a_j-a_i)$%, делящихся на $%k$%. Рассмотрите сначала случай, когда $%n$% делится на $%k$%.

Подсказка мне не помогла, решил задачу иначе.

задан 10 Мар '15 11:02

изменен 10 Мар '15 12:58

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

Я пробовал несколько подходов, включая использование свойств определителей Вандермонда. Поскольку от произвольного набора целых чисел можно перейти к набору из $%n$% первых натуральных посредством серии элементарных операций -- прибавления $%\pm1$% к одному из чисел, то достаточно было проверить одно свойство. А именно, что $%V(x,\ldots)$% делится на $%V(1,2,\ldots,n)$% тогда и только тогда, когда $%V(x+1,\ldots)$% делится на то же число. Таким способом, наверное, можно что-то получить, но я в итоге пошёл по другому пути -- рассматривать максимальную степень простого числа, делящую каждое из двух произведений.

Прежде всего, рассмотрим такое вспомогательное утверждение (в духе указания из задачника). Пусть имеется произведение целых чисел $%b_1\ldots b_N$% и произведение натуральных чисел $%c_1\ldots c_N$%. Предположим, что для любого натурального $%k$% число сомножителей вида $%b_i$%, делящихся на $%k$%, не меньше числа сомножителей вида $%c_i$%, делящихся на $%k$%. Тогда утверждается, что $%b_1\ldots b_N$% делится на $%c_1\ldots c_N$%. Действительно, если первое из произведений равно нулю, то доказывать нечего, а в противном случае рассмотрим модуль первого из произведений и сравним канонические разложения. Тогда окажется, что показатель степени при простом числе $%p$% у каждого из произведений будет равен сумме $%n_p+n_{p^2}+n_{p^3}+\cdots$%, где $%n_k$% означает число сомножителей, делящихся на $%k$% (это как в известной задаче о факториалах). Получается, что у первого произведения показатель степени при $%p$% не меньше, чем у второго.

Теперь докажем само утверждение. Достаточно рассмотреть случай $%k < n$%, так как максимальное значение сомножителя в произведении чисел вида $%j-i$% равно $%n-1$%. Рассмотрим граф с $%n$% вершинами, и разобьём их на некоторое количество подмножеств, которое не превосходит $%k$%. Для каждого из подмножеств рассмотрим полный подграф на этом множестве вершин. Нас интересует случай, когда суммарное число рёбер всех подграфов окажется минимальным.

Прежде всего, можно заметить, что число компонент связности меньше $%n$%, и среди них есть такие, у которых более одной вершины. Тогда, если число компонент не равно $%k$%, можно разбить одну компоненту на две, уменьшая число рёбер.

Итак, будем считать, что компонент ровно $%k$%. Нашей целью является установление того факта, что для оптимального случая число вершин в компонентах примерно одинаково. Заметим, что если есть две вершины, валентности которых отличаются более чем на 1, то можно вершину большей валентности перевести в компоненту, которой принадлежит вершина меньшей валентности, и тогда суммарное число рёбер уменьшится. В результате таких преобразований мы придём к случаю, когда число вершин в компонентах принимает одно или два значения. Если оно одно, то примем это число за $%q$%, а если два, то меньшее примем за $%q$%, а большее за $%q+1$%. Ясно, что компонент второго вида имеется $%n-qk < k$%, то есть $%q$% однозначно определяется как неполное частное от деления $%n$% на $%k$%. Это и есть то описание, которое мы хотели получить.

Теперь применим его к нашему случаю. Числам $%a_i$% ($%1\le i\le n$%) сопоставим вершины графа, а разбиение на компоненты произведём по принципу совпадения остатков от деления на $%k$%. Рёбер тут будет столько, сколько имеется пар вида $%j > i$%, для которых $%a_j-a_i$% делится на $%k$%. Мы выяснили, в каком случае количество рёбер минимально. Теперь можно заметить, что для первых $%n$% последовательных натуральных чисел, при разбиении их на части по принципу совпадения остатков, количества оказываются как раз "примерно равными", что и соответствует минимальному количеству рёбер.

ссылка

отвечен 10 Мар '15 22:25

Красивое решение!

(11 Мар '15 0:01) EdwardTurJ
10|600 символов нужно символов осталось
2

Можно считать, что все числа $%a_1,a_2,...,a_n$% натуральные (это достигается простым сдвигом). $$\prod_{1\le i< j\le n}\frac{a_j-a_i}{j-i}=\frac1{1!\cdot2!\cdot...\cdot(n-1)!}\begin{vmatrix} 1& a_1& a_1^2& ...& a_1^{n-1}\\ 1& a_2& a_2^2& ...& a_2^{n-1}\\ ...& ...& ...& ...& ...\\ 1& a_n& a_n^2& ...& a_n^{n-1}\\ \end{vmatrix}=$$ $$=\begin{vmatrix} 1& \frac{a_1}{1!}& \frac{a_1^2}{2!}& ...& \frac{a_1^{n-1}}{(n-1)!}\\ 1& \frac{a_2}{1!}& \frac{a_2^2}{2!}& ...& \frac{a_2^{n-1}}{(n-1)!}\\ ...& ...& ...& ...& ...\\ 1& \frac{a_n}{1!}& \frac{a_n^2}{2!}& ...& \frac{a_n^{n-1}}{(n-1)!}\\ \end{vmatrix}= \begin{vmatrix} C_{a_1}^0& C_{a_1}^1& C_{a_1}^2& ...& C_{a_1}^{n-1}\\ C_{a_2}^0& C_{a_2}^1& C_{a_2}^2& ...& C_{a_2}^{n-1}\\ ...& ...& ...& ...& ...\\ C_{a_n}^0& C_{a_n}^1& C_{a_n}^2& ...& C_{a_n}^{n-1}\\ \end{vmatrix}\in\mathbb Z.$$ Последнее равенство следует из того, что $%C_{a_k}^l$% можно представить как $%\frac{a_k^l}{l!}$% плюс линейная комбинация с целыми коэффициентами от $%1,\frac{a_k}{1!},...,\frac{a_k^{l-1}}{(l-1)!}$%.

ссылка

отвечен 10 Мар '15 23:32

изменен 10 Мар '15 23:47

1

Да, это довольно симпатичный способ рассуждения. Это, конечно, проще, чем рассуждение с участием $%x$%, где тоже была идея как-то разложить по сочетаниям. Здесь заодно и явный ответ для частного получается.

(10 Мар '15 23:55) falcao
1

@falcao: Можно также поставить обратную задачу - вычислить последний определитель.

(11 Мар '15 20:01) EdwardTurJ
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×275
×216

задан
10 Мар '15 11:02

показан
9861 раз

обновлен
11 Мар '15 20:01

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

по почте:

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

по RSS:

Ответы

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

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