Математикадан республикалық олимпиада, 2010-2011 оқу жылы, 11 сынып

Тақ, натурал $m > 1,k$ сандары және $p > mk+1$ болатын $p$ жай саны берілген. Келесі тұжырымды дәлелде: ${{(C_{k}^{k})}^{m}}+{{(C_{k+1}^{k})}^{m}}+\ldots +{{(C_{p-1}^{k})}^{m}}$ қосындысы ${{p}^{2}}$ санына бөлінеді. Мұнда $C_{n}^{k}=\frac{n!}{k!(n-k)!}$ — биномиалдық коэффициент. ( Д. Елиусизов )

Комментарий/решение

Решение: Поскольку $gcd(p,k!)=1,$ то достаточно доказать делимость

$$p^2\mid P(k)^m+\ldots+P(p-1)^m,$$

где $P(n)=n(n-1)\cdots(n-k+1)$ $-$ многочлен степени $k.$ Определим многочлен $Q\in\mathbb Z[x]$ след. образом

$$Q(x)=P(x)+P(p+k-x-1).$$

Свойство: Все коэффициенты $Q$ кратны $p.$

Доказательство: Здесь будем рассматривать многочлены над полем $\mathbb F_p.$

Легко понять, что

$Q(x)=P(x)+P(p+k-1-x)=P(x)+P(k-1-x)=0$ для $\forall x\in \mathbb Z.$

Отсюда легко видеть, что все коэффициенты $Q$ кратны $p,$ то есть $Q(x)=pQ_1(x),$ где $Q_1\in\mathbb Z[x].\quad\blacksquare$

Заметим, что

$$P(x)^m+P(p+k-1-x)^m=\bigg(P(x)+P(p+k-1-x)\bigg)Q_2(x)=Q(x)Q_2(x)=pR(x),$$

где $R=Q_1Q_2\in\mathbb Z[x],$ при этом $deg (R) \le mk < p-1.$ Откуда

$$2\sum_{x=k}^{p-1} P(x)^m = p\sum_{x=k}^{p-1}R(x),$$

поэтому достаточно доказать, что $p\mid\sum_{x=k}^{p-1}R(x).$ Заметим, что $p\mid P(p+k-1-x)$ и $P(x)=0,$ следовательно $p\mid R(x),$ для $\forall x\in\{1,\ldots,k-1\}.$

Осталось доказать, что $$p\mid\sum_{x=1}^{p-1}R(x),$$ что верно, так как $deg(R)<p-1.$