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 1 of 5: Count all allowed placements

Previous step Next step

r=\binom{p^2}{p}-p=p\left(\frac{(p^2-1)\cdots(p^2-(p-1))}{(p-1)!}-1\right)

Detailed analysis

Choosing $p$ distinct squares gives $\binom{p^2}{p}$ placements. Exactly $p$ of them put one checker in every column of a single row, so they are excluded. Hence $r=\binom{p^2}{p}-p$ , and it is enough to prove $\frac{(p^2-1)\cdots(p^2-(p-1))}{(p-1)!}-1$ is divisible by $p^4$ .