UNO High School Problem of the Week Competition
Problem 1
Suppose the letters of the word "calculus" are rearranged and every unique arrangement
constitutes a valid word within a dictionary. If looking in alphabetical order, what is
the 2011th word?
Solution
Problems like this involve what is known as permutations with repeated letters. In general,
when you have n letters, with n1 copies of the 1st letter, n2 copies of the 2nd letter,
..., and nk copies of the kth letter, then the number of desired permutations is n!/n1!*n2!*...*nk!.
For simplicity, let [] denote the number of permutations. For example [calculus] = 8!/2!2!2! = 5,040.
First consider words that begin w/ the letter 'a', namely a[clculus] = 630. As 2011 is greater than 630, we know
that the 2011th does not begin with an 'a'. Now following similar logic, we get the following:
c[alculus] = 1260. 2011 is greater than 1890 (630 + 1260). 2011th word doesn't begin with 'c'.
l[caculus] = 1260. 2011 is less than 3150 (1890 + 12600). 2011th word begins with 'l'.
la[cculus] = 180. 2011 is less than 2070 (1890 + 180). 2011th word begins with 'la'.
lac[culus] = 60. 2011 is greater than 1950 (1890 + 60). 2011th word doesn't begin with 'lac'.
lal[ccuus] = 30. 2011 is greater than 1980 (1950 + 30). 2011th word doesn't begin with 'lal'.
las[ccluu] = 30. 2011 is greater than 2010 (1980 + 30). 2011th word doesn't begin with 'las'.
This process could continue a little farther. But noticing that we have accounted for the 1st 2010 words.
Therefore, the 2011th word is the 1st word beginning with 'lau'. Thus the desired word "LAUCCLSU".