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 $1,2,\dots,12$ . Let $X$ be the set of all $2^{12}$ colorings of these positions by two key types (say A and B). The cyclic group $C_{12}$ of rotations acts on $X$ 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)|.$

A rotation by $r$ positions fixes exactly those colorings that are constant on each cycle of that rotation. The rotation by $r$ has $\gcd(12,r)$ cycles, so it fixes $2^{\gcd(12,r)}$ colorings. Hence $\#\text{arrangements}=\frac{1}{12}\sum_{r=0}^{11}2^{\gcd(12,r)}.$

It is convenient to evaluate this sum using the divisor– $\varphi$ identity for cyclic necklaces: $\frac{1}{n}\sum_{r=0}^{n-1}k^{\gcd(n,r)}=\frac{1}{n}\sum_{d\mid n}\varphi(d)\,k^{n/d}.$ With $n=12$ and $k=2$ we get $\#\text{arrangements}=\frac{1}{12}\sum_{d\mid 12}\varphi(d)\,2^{12/d}.$

The divisors of $12$ are $1,2,3,4,6,12$ with $\varphi(1)=1,\ \varphi(2)=1,\ \varphi(3)=2,\ \varphi(4)=2,\ \varphi(6)=2,\ \varphi(12)=4$ . 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).$

$=\frac{1}{12}\big(4096+64+32+16+8+8\big)=\frac{4224}{12}=352.$

$\boxed{352}$

$\square$

(Note: only rotations are considered, not reflections, so we use the cyclic group $C_{12}$ .)

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

Page

Toolbox

Search

Mock AIME 1 Pre 2005 Problems/Problem 14

Problem

Solution (Burnsides Lemma)

See also