Problem 3

Let

p\ge5

be a prime. Let

r

be the number of ways of placing

p

identical checkers on a

p\times p

checkerboard so that not all checkers are in the same row (they may all be in the same column). Show that

r

is divisible by

p^5

Step 3 of 5: Evaluate the polynomial at p

Previous step Next step

f(p)=(p-1)!=s_{p-2}p^{p-2}+\cdots+s_1p+s_0

Detailed analysis

Because $s_0=(p-1)!$ exactly, evaluating at $x=p$ and cancelling $s_0$ gives $p^{p-1}+s_{p-2}p^{p-2}+\cdots+s_2p^2=-s_1p$ . Since $p\ge5$ and $p\mid s_i$ for $i\ge1$ , all terms on the left after division by $p$ are divisible by $p^2$ except possibly $-s_1$ ; hence $p^2\mid s_1$ .