2008 Hunt puzzle: All Geared Up 
[Jan. 21st, 200808:15 pm]
devjoe

I have decided to start writing my solutions here, to be integrated into the MIT Mystery Hunt web site as time allows.
All Geared Up was solved by 23 teams, first by the Evil Midnight Bombers at 2:26 PM Friday and last by Burton45 at 7:10 PM Sunday. Manic Sages solved it fastest, only 25 minutes and 6 seconds after getting access to it.
It should be apparent upon analyzing the picture that there are two groups of gears here. The six small gears in a straight line at the top have mixed letters of the alphabet on them, while the 10 larger gears crammed into the rest of the image have all the letters in alphabetical order, without skipping any on most gears, and only skipping some of the more difficult letters on the smaller ones of these gears. Consider the small gears first. Most of the letters are difficult ones and there are few vowels available, and as a result there is only one word that can be spelled across them: ANSWER. You can confirm this with word lists or get it from the flavor text.
How far do you have to turn the gears to make them spell out ANSWER? Turning the first gear in the direction of the arrow, you need to turn it 4 notches to bring the A up to the mark. But the rest of the word won't be spelled out, so you will need 4 plus some multiple of 13 to get A on top another time. The second gear will turn in the opposite direction, so you need to rotate it 1 notch plus a multiple of 11. And so you need to solve for X such that: X = 4 mod 13 X = 1 mod 11 X = 2 mod 9 X = 7 mod 8 X = 3 mod 7 X = 2 mod 5
The Chinese Remainder Theorem solves problems of exactly this type. Writing the set of equations as X = ai mod ni, and letting N be the product of the relatively prime ni, solve for some ri and si such that ri ni + si N/ni = 1. This is solved with the extended Euclidean algorithm. Then let ei = siN/ni, and the desired solution is the sum of the ai ei. There will be multiple solutions, but they will all be congruent modulo N. If you get a number larger than this, take it modulo N (which is 360360).
Or, if you can't figure out all that math, you could just write a program to iterate through the integers 1 to 360360 and print out the one where the equations are all true. It is 248447.
Given this number, you can now solve for the positions of the other gears by simply taking 248447 modulo the sizes of the gears. 248447 mod 29 = 4, mod 17 = 9, mod 22 = 1, mod 20 = 7, mod 28 = 3, mod 16 = 15, mod 19 = 3, mod 26 = 17, mod 23 = 1, mod 27 = 20. Turning each gear this amount in the appropriate direction spells out INTERLOCKS on the letters marked at the top of each gear. This puzzle was originally conceived from a wrong solution idea I had during the 2007 Hunt for the puzzle For Gearheads Only. I thought of the way that a series of meshing gears rotate in alternating directions, and considered something like a Caesar cipher but with the letters alternately moving forward and backward, and wanted to see what words could be made into other words by that mechanism. Since it relates each word to only 25 other strings of the same length, there were few possibilities longer than 5 letters and most of them involved obscure words. I tried to improve that by implementing gears of different sizes; one attempt to use two gear types, one with AEIOUY and one with all the other letters, led to most of the results keeping the same vowels with different consonants or vice versa. Finally I decided it was only going to be interesting if all the gears were of different sizes, and that suggested a different type of puzzle entirely, which led to the one you see here with a pleasing mathematical basis and a rather less mathy solution path. Testsolvers used both techniques successfully. 

