MathLabs

第3题

设 p≥5p\ge5 为素数。令 rr 为在 p×pp\times p 棋盘上放置 pp 个相同棋子的方式数，要求棋子不全在同一行（但可以全在同一列）。证明 rr 被 p5p^5 整除。
第 1/5 步：计算允许的放置数
上一步下一步
r=(p2p)−p=p((p2−1)⋯(p2−(p−1))(p−1)!−1)r=\binom{p^2}{p}-p=p\left(\frac{(p^2-1)\cdots(p^2-(p-1))}{(p-1)!}-1\right)
详细分析

选择 pp 个不同棋盘格有 (p2p)\binom{p^2}{p} 种。把所有棋子放在同一行的方式有 pp 种，应予排除。因此 r=(p2p)−pr=\binom{p^2}{p}-p，只需证明 (p2−1)⋯(p2−(p−1))(p−1)!−1\frac{(p^2-1)\cdots(p^2-(p-1))}{(p-1)!}-1 被 p4p^4 整除。