Азия-тынық мұхит математикалық олимпиадасы, 2006 жыл

$p\ge 5$ жай сан болсын және $p$ тастардың, барлығы бір жолда жатпайтындай(барлығы бір бағанда болуы мүмкін), $p\times p$ шахмат тақтасынадағы әртүрлі барлық мүмкін орналасу саны $r$ болсын. $r$ саны $p^5$-не бөлінетіндігін дәлелденіз. Бұл жерде барлық тастар бірдей деп есептейміз.

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

Учитывая количество всех возможных расстановок, это будет $C_{p^{2}}^{p}$. У нас $p$ «плохие» договоренности.

Итак, мы должны доказать, что:

$C_{p^{2}}^{p}-p \vdots p^{5} \Leftrightarrow$

$\frac{p^{2}\cdot(p^{2}-1)\cdot\ldots(p^{2}-p+1)}{p!}-p \vdots p^{5}\ Влевовправострелка$

$\frac{p^{2}\cdot(p^{2}-1)\cdot\ldots(p^{2}-p+1)-p\cdot p!}{p!}$ $\vdots$ $p^{5}\Leftrightarrow$

$\frac{p(p^{2}-1)(p^{2}-2)\ldots (p^{2}-(p-1))-p!}{(p-1)!}$ $\vdots$ $p^{5}$. Поскольку $p$ — простое число, мы игнорируем $(p-1)!$. Разделив на $p$, мы должны доказать, что:

$(p^{2}-1)\ldots (p^{2}-p+1)-(p-1)!$ $\vdots$ $p^{4}$.

Если в процессе раскрытия скобок мы выберем 2 $p^{2}$, то все произведение будет делиться на $p^{4}$.

Итак, мы должны доказать, что:

$p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p- 1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$.

Поскольку $(-1)^{p-1}=1$, то достаточно доказать, что:

$\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1}$ $\vdots$ $p^{2}\Leftrightarrow$

$(p-1)!\cdot(1+\frac{1}{2}+\ldots+\frac{1}{p-1})$ $\vdots$ $p^{2}$

Последнее непосредственно следует из теоремы Вольстенхолма. $p^{5}\Leftrightarrow$

$\frac{p(p^{2}-1)(p^{2}-2)\ldots (p^{2}-(p-1))-p!}{(p-1)!}$ $\vdots$ $p^{5}$. Since $p$ is a prime number, we ignore $(p-1)!$. Dividing by $p$, we must prove that:

$(p^{2}-1)\ldots (p^{2}-p+1)-(p-1)!$ $\vdots$ $p^{4}$.

In the process of opening the brakets, if we select 2 $p^{2}$'s, then the whole product will be divisible by $p^{4}$.

So, we must prove that:

$p^{2}(\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1})+(-1)^{p-1}(p-1)!-(p-1)!$ $\vdots$ $p^{4}$.

Since $(-1)^{p-1}=1$, then it suffices to prove that:

$\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\ldots \frac{(p-1)!}{p-1}$ $\vdots$ $p^{2}\Leftrightarrow$

$(p-1)!\cdot(1+\frac{1}{2}+\ldots+\frac{1}{p-1})$ $\vdots$ $p^{2}$

The last follows immediately from Wolstenholme's Theorem.