Азиатско-Тихоокеанская математическая олимпиада, 2006 год

Пусть $p\geq 5$ является простым числом и пусть $r$ есть число всевозможных различных способов размещения p шашек на шахматной доске размера $p\times p$ таким образом, что не все шашки лежат на одной строке (но все они могут находиться в одном столбце). Докажите, что $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.