And now for the true story of how puzzle solvers saved Christmas. It all began this past Tuesday when my friend Alex came to me with a time-sensitive problem. He wrote:
The lady that sits next to me in the lab has a 10 year old son who's just of the age to be questioning Santa. Since Santa sees all, he decided to write a Christmas list in code, and only utter the decryption key to the code only once, out loud, to a friend of his on the playground, under the assumption that Santa or his agents should hear it and would decrypt his list. His mom and dad have been working on the code for a week or two now with little progress, and Christmas is getting close. Think you know a puzzle geek that want's to take a crack at it?
We're not looking at a basic substitution or Caesar cipher, probably something more like a Vigenère, which, theoretically can be uncrackable. However, being a 10 year old boy, encoding this in his head while reciting the alphabet and counting, he seems to have violated several of the basic requirements of a strong cypher, making it vulnerable to attack.
The first and last two phrases have the proper character count to decode to "Dear Santa" and "Thank you."
The boy's Christmas list looked like so:
Wlju vdgz bcn J iyci b bnsjgpgwwo, gpb jsijgm gp fhrga: kxfabmt ivryt, Frqeqkg, bcn J iyci hju Mtnnxvrhcfpf gp icqyayeqpj xjfqwo ryu. Prdju xqz!
For those who wish to crack the code themselves, please stop reading now. For the rest of you, the story continues as follows.
I immediately sprung into action and reposted the letter to Facebook, and within ten minutes some heavy-hitters had already noticed some interesting patterns. Dan Katz, a math lecturer at Brown, said "If it starts 'Dear Santa,' I don't think it's Vigenère unless it's a very long keyword. Eight of the first nine shifts are different." Guy Tabachnik, a student at Brown, chimed in: "There's the repeated bcn J iyci string in the middle, which might be something like 'and I want.'" While the up and coming puzzle maker Erik Agard added, "the repeated bcn J iyci strings are 48 characters apart, if that helps." The chase was underway.
Out came the cynics. "Coal for this kid. Thou shalt not put Santa to the test!," spake "Jeopardy!" champ Joon Pahk. Elizabeth White of Reno said, "Smart kid. Probably time to just come clean about Santa." While Eric Maddy of Huntington Beach proposed a wicked response: "Mom and Dad should leave a coded message telling kid where to find his gifts from Santa. A really well-coded message."
The code-breakers pushed forward. Guy, especially, was undeterred. He employed the tried-and-true formula of solving the problem out loud that works so well in group solving. "If iyci is want, that's kind of interesting, since w and t are three letters apart both in the alphabet and in the code." "If bcn is and, we have +1, =, -1 with the second and third letters switched." Then the firewall was broken as Natan Last of Brooklyn posted the key. "If Prdju xqz is Thank you: reverse each to get Ujdrp zqx. T + 1 = U, h + 2 = j, a + 3 = d, ..."
While Natan was the first to publicly announce the solution, it should be said that Kevin Wald of Cambridge, MA, also privately IMed the solution almost simultaneously. Kevin explained his approach: "I got lucky. I thought of 'This year,' realized 'Dear' and 'year' (which end the same) had become Vdge and vdgz (which start the same) and did everything I'd tried before, for the word-reversed version. when I looked at the Vigenère shifts, the 1, 2, 3 pattern leapt out."
And thanks to power of group solving on-line, Christmas was saved. The boy's letter to Santa is as follows. And yes, the typos are his, not mine:
DEAR SANTA THIS YEAR MAY I HAVE A NUTCKACKER AND LEGEND OE ZEODA SKYWARD SWORD FINALLY MAY I HAVE THE ENCYCLOPEDIA OE INNATURITY NUNBER TWO THANK YOU
Share the puzzle. New one on Monday.