Mock AIME 1 Pre 2005 Problems/Problem 14
Problem
Wally's Key Company makes and sells two types of keys. Mr. Porter buys a total of 12 keys from Wally's. Determine the number of possible arrangements of My. Porter's 12 new keys on his keychain (rotations are considered the same and any two keys of the same type are identical).
Note: The problem is meant to be interpreted so that if you cannot produce one arrangement from another by rotation, then the two arrangements are different, even if you can produce one from the other from a combination of rotation and reflection.
Solution (Burnsides Lemma)
Label the 12 positions around the keyring 
. Let 
be the set of all 
colorings of these positions by two key types (say A and B). The cyclic group 
of rotations acts on by rotating the positions; two colorings are considered the same precisely when they lie in the same orbit under this action. By Burnside's Lemma the number of distinct arrangements (orbits) is
![\[\frac{1}{|C_{12}|}\sum_{g\in C_{12}}|\operatorname{Fix}(g)|=\frac{1}{12}\sum_{r=0}^{11}|\operatorname{Fix}(\text{rotation by }r)|.\]](http://latex.artofproblemsolving.com/6/f/3/6f3aa56c748800a7c3e675b6e0699ecfec85175a.png)
A rotation by 
positions fixes exactly those colorings that are constant on each cycle of that rotation. The rotation by has 
cycles, so it fixes 
colorings. Hence
![\[\#\text{arrangements}=\frac{1}{12}\sum_{r=0}^{11}2^{\gcd(12,r)}.\]](http://latex.artofproblemsolving.com/c/5/7/c570cd7fba144a8717eacf513554bbde4ead1a6a.png)
It is convenient to evaluate this sum using the divisor–
identity for cyclic necklaces:
With 
and 
we get
![\[\#\text{arrangements}=\frac{1}{12}\sum_{d\mid 12}\varphi(d)\,2^{12/d}.\]](http://latex.artofproblemsolving.com/e/0/6/e0693751fd431a1f166f6806db8c0d7a417ea901.png)
The divisors of 
are 
with 
. Thus
![\[\#\text{arrangements}=\frac{1}{12}\big(1\cdot 2^{12}+1\cdot 2^{6}+2\cdot 2^{4}+2\cdot 2^{3}+2\cdot 2^{2}+4\cdot 2^1\big).\]](http://latex.artofproblemsolving.com/f/a/f/fafbdeddf57c98ba6857f6654fd735a8f27e347a.png)
![\[=\frac{1}{12}\big(4096+64+32+16+8+8\big)=\frac{4224}{12}=\boxed{352}.\]](http://latex.artofproblemsolving.com/4/0/8/408e11f5b32957d7facd37cbb31caf724543edfa.png)
(Note: only rotations are considered, not reflections, so we use the cyclic group .)
~NicoPlusAki_2011
See also
| Mock AIME 1 Pre 2005 (Problems, Source) | ||
| Preceded by Problem 13 |
Followed by Problem 15 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
