[math-fun] Chessboards and Wilson's Theorem
Consider a p*p chessboard, and place an arrangement of p non- attacking rooks on it. There are clearly p! ways in which this can be done. If we interpret the chessboard instead as a torus, and let translations of the board be considered equivalent, then there are fewer unique arrangements. Out of the p² symmetries, 1 (the identity) fixes p! arrangements; 2(p-1) (vertical/horizontal translations) fix no arrangements; and the remaining (p-1)² each fix p arrangements. Hence, there are [p!+p(p-1)²]/p² = [(p-1)!+(p-1)²]/p unique arrangements, up to toroidal translations of the board, by Burnside's Lemma. This must be an integer, so (p-1)! is congruent to -1 modulo p. QED. Sincerely, Adam P. Goucher
I like that, though have no idea whether it's original. I've come across similar combinatorial proofs of number theoretic results in the past; I wonder if it's occurred to anybody to attempt a comprehensive survey? WFL On 6/17/12, Adam P. Goucher <apgoucher@gmx.com> wrote:
Consider a p*p chessboard, and place an arrangement of p non- attacking rooks on it. There are clearly p! ways in which this can be done.
If we interpret the chessboard instead as a torus, and let translations of the board be considered equivalent, then there are fewer unique arrangements. Out of the p² symmetries, 1 (the identity) fixes p! arrangements; 2(p-1) (vertical/horizontal translations) fix no arrangements; and the remaining (p-1)² each fix p arrangements.
Hence, there are [p!+p(p-1)²]/p² = [(p-1)!+(p-1)²]/p unique arrangements, up to toroidal translations of the board, by Burnside's Lemma. This must be an integer, so (p-1)! is congruent to -1 modulo p.
QED.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sun, Jun 17, 2012 at 12:45 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
I like that, though have no idea whether it's original.
I've come across similar combinatorial proofs of number theoretic results in the past; I wonder if it's occurred to anybody to attempt a comprehensive survey?
One might start with George Andrews' book Number Theory<http://www.amazon.com/Number-Theory-Dover-Books-Mathematics/dp/0486682528/ref=cm_cr_pr_product_top> which as I recall uses many combinatorial proofs of basic number theoretic theorems. In fact as I recall that was his goal in writing the book.
participants (3)
-
Adam P. Goucher -
Fred lunnon -
W. Edwin Clark