Archive for the ‘Puzzles’ Category.

## A Problem from the Moscow Olympiad

Here is a problem from the 2012 Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

• Prove that all the people have exactly the same number of common acquaintances at this meeting.
• Show that n can be greater than 4.

My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.

Let’s take this up a notch and work on a more difficult problem.

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

• Prove that all the people have exactly the same number of common acquaintances at this meeting.
• Is it possible that n can be greater than 2k?

## Integers and Sequences Solution

This is the promised solution to the puzzle Integers and Sequences that I posted earlier. The puzzle is attached below.

Today I do not want to discuss the underlying math; I just want to discuss the puzzle structure. I’ll assume that you solved all the individual clues and got the following lists of numbers.

• 12 42 18 40 30 24 20
• 2 1 132 42 429 14
• 7 9 1 8 5 3 10 4
• 92 117 70 145 35 1 22 12 5
• 137 1 37 13 107 1013 113
• 30 12 2 42 6
• 70 4030 836 7192

Since the title mentions sequences, it is a good idea to plug the numbers into the Online Encyclopedia of Integer Sequences. Here is what you will get:

• not clear
• Catalan numbers with 5 missing: 1, 1, 2, 5, 14, 42, 132, 429
• not clear
• Pentagonal numbers with 51 missing: 1, 5, 12, 22, 35, 51, 70, 92, 117, 145
• Primeval numbers with 2 missing: 1, 2, 13, 37, 107, 113, 137, 1013
• not clear
• Weird numbers with 5830 missing: 70, 836, 4030, 5830, 7192

Your first “aha moment” happens when you notice that the sequences are in alphabetical order and each has exactly one number missing. The alphabetical order is a good sign that you are on the right track; it can also narrow down the possible names of the sequences that you haven’t yet identified. Alphabetical order means that you have to figure out the correct order for producing the answer.

Did you notice that some groups above are as long as nine integers and some are as short as four? In puzzles, there is nothing random, so the lengths of the groups should mean something. Your second “aha moment” will come when you realize that, together with the missing number, the number of the integers in each group is the same as the number of letters in the name of the sequence. This means you can get a letter by indexing the index of the missing number into the name of the sequence.

So each group of numbers provides a letter. Now we need to identify the remaining sequences and figure out in which order the groups will produce the word that is the answer.

Let’s go back and try to identify the remaining sequences. We already know the number of letters in the name of each sequence, as well as the range within the alphabet. The third sequence might represent a challenge as its numbers are small and there might be many sequences that fit the pattern, but let’s try. The results are below with the capitalized letter being the one that is needed for the answer.

• abundAnt
• caTalan
• dEficient or iMperfect
• pentaGonal
• pRimeval
• proNic or proMic
• weiRd

What is going on? There are two sequences that fit the pattern of the third group and the sequence for the sixth group has many names, two of which fit the profile but produce different letters. Now we get to your third “aha moment”: you have already seen some of the sequence names before, because they are in the puzzle. This will allow you to disambiguate the names.

Now that we have all the letters, we need the order. Sequences are mentioned inside the puzzle. You were forced to notice that because you needed the names for disambiguation. Maybe there is something else there. On closer examination, all but one of the sequence names are mentioned. Moreover, with one exception the clues for one sequence mention exactly one other sequence. Once you connect the dots, you’ll have your last “aha moment:” the way the sequences are mentioned can provide the order. The first letter G will be from the pentagonal sequence, which was not mentioned. The clues for the pentagonal sequence mention the primeval sequence, which will give the second letter R, and so on.

Many old-timers criticized the 2013 MIT Mystery Hunt. They are convinced that a puzzle shouldn’t have more than one “aha moment.” I like my “aha moments.”

*****

• (the largest integer n such that there exists a Platonic solid with n vertices, a Platonic solid with n edges, and a Platonic solid with n faces)
• (the largest two-digit tetrahedral number)/(the smallest value the second smallest angle of a convex hexagon with all integer degrees can have)
• (the number of positive integers less than 2013 that are divisible by 100, but not divisible by 70)
• (the number of two-digit numbers that produce a square when summed up with their reverse) ⋅ (the smallest number of weighings on a balance scale that guarantees to find the only fake coin out of 100 identical coins, where the fake coin is lighter than other coins)
• (the only two digit number n such that 2n ends with n) − (the second smallest, and conjectured to be the largest, triangular number such that its square is also triangular)
• (the smallest non-trivial compositorial number that is also a factorial)
• (the sum of the smallest three positive pronic numbers)

*****

• (the digit you get when you sum up the digits of 20132013 repeatedly until you get a single digit) − (the greatest common factor of the indices of the Fibonacci numbers divisible by 13)
• (the largest common divisor of numbers of the form p2 − 1 for primes p greater than three) − (the largest sum of digits that can appear on a 12-hour digital clock starting from 1:00 up to 12:59)
• (the largest Fibonacci number, such that it and all positive Fibonacci numbers less than it are deficient) + (the difference between the sum of all even numbers up to 100 and the sum of all odd numbers up to 100) − (the first digit of a four-digit square that has the first two digits the same and the last two digits the same)
• (the smallest composite Jacobsthal number) ⋅ (the only digit needed to express the number of diagonals of a convex hendecagon)/(the smallest prime divisor of 132013 + 1)
• (the smallest integer the fate of whose aliquot sequence is unknown) + (the largest amount of money in cents you can have in American coins without having change for 2 dollars) − (the repeated number in the aliquot cycle of 95) ⋅ (the second-smallest integer n such that the Russian word for n has n letters)
• (the smallest positive even integer that’s not a totient)

*****

• (the number of letters in the last name of a famous Russian writer whose year of birth many Russians use to help them memorize the digits of e)
• (the number of pluses you need to insert in a row of 20 fives so that the sum is 1000)
• (the number of positive integers less than 2013 such that not all their digits are distinct) − (the number of four-digit numbers with only odd digits) − (the largest Fibonacci square)
• (the number of positive integers n for which the sum of the n smallest positive integers evenly divides 18n)
• (the number of trailing zeroes of 2013!) − (the number of sets in the game of Set such that every feature is different on all three cards) − (an average speed in miles per hour of a person who drives somewhere with a speed of 420 miles per hour, then drives back using the same route with a speed of 210 miles per hour)
• (the smallest fortunate triangular number)
• (the smallest weird number)/(the only prime one less than a cube)
• (the third most probable product of the numbers showing when two standard six-sided dice are rolled)

*****

• (the largest integer number of dollars you can’t pay if you have an unlimited supply of 9-dollar bills and 13-dollar bills) − (the positive difference between the two prime numbers that do not share a unit digit with any other prime number)
• (the largest three-digit primeval number) − (the largest number of distinct SET cards without a set)
• (the number conjectured to be the second-largest number such that two to its power has no zeroes) − (the largest number whose cube has at most two distinct digits and no zeroes)
• (the number of 5-digit palindromic integers in base 5) + (the only positive integer that is five times the sum of its digits)
• (the only Fibonacci number that is a double of a prime) + (the only prime p such that p! has p digits) − (the only fixed point of look-and-say operation)
• (the only number whose concatenation with itself is prime)
• (the only positive integer that that differs by 1 from a square and a nonsquare cube) − (the largest number such that its divisors are each 1 less than a prime)
• (the smallest evil untouchable number)

*****

• (the alphanumeric value of MANIC SAGES) + (the sum of all three-digit numbers you can get by permuting digits 1, 2, and 3) + (the number of two-digit integers divisible by 9) − (the number of rectangles whose sides are composed of edges of squares of a chess board)
• (the integer whose standard Roman numeral representation is alphabetically later than all others) − (the number you get if you divide a three digit number with identical digits by the sum of the digits)
• (the largest even integer that is not a sum of two abundant numbers) − (the digit in the first position where e and π have the same digit)
• (the number formed by the last two digits of the sum: 1! + 2! + 3! + 4! + . . . + 2013!)
• (the only positive integer such that if you sum the digits and the squares of the digits, you get the original number back) + (the largest prime factor of the smallest Carmichael number)
• (the smallest multi-digit hyperperfect number such that more than half of its digits are the same) − (the sum of digits that cannot be the last digits of squares) ⋅ (the largest base n in which 8n is not written like 80) ⋅ (the smallest positive integer that leaves a remainder of 2 when divided by 3, 4, and 5)
• (the smallest three-digit brilliant number) − (the first decimal digit of the number that in hexadecimal gives the house number of Sherlock Holmes)

*****

• (the number of evil minutes in an hour)
• (the number of fingers on ten hands) − (the smallest number such that its square has a digit repeated three times)
• (the number of ways you can rearrange letters of MANIC)/(the number of ways you can rearrange letters of SAGES)
• (the only multi-digit Catalan number with digits in strictly decreasing order)
• (the smallest perfect number)

*****

• (the largest product of positive integers that sum up to 10) + (the smallest perimeter of a rectangle with integral sides of area 120) − (the day of the month of the second Thursday in a January that has exactly 4 Mondays and 4 Fridays)
• (the second-largest number with all distinct digits, such that all the words in its American English representation start with the same letter) + (the largest square-free composite number that contains each of the digits 1, 2, 3, 4 exactly once in its prime factorization) + (the number of ways you can flip a coin 10 times so that the number of heads is the same as the number of tails) + (the smallest positive integer such that 2 to its power contains 2013 as a substring) + (the sum of five prime numbers formed from the digits 2, 3, 5, 7, 8, 9 where each digit is used exactly once) + (the number of days in a year where the day of the month is odious) + (the sum of the digits each of which spelled out has an alphanumeric value equal to the meaning of life, the universe, and everything) ⋅ (the sum of all prime numbers p such that p + 20 and p + 40 are also prime) + (the first digit of the total number of legal moves of the Black king in chess)
• (the second-largest three-letter palindrome in Roman numerals)/((the smallest composite number not divisible by any of its digits)/(the last digit of 20132013) − (the digit in position 2013 of the string formed by concatenation of all integers into one stream: 123456789101112…)) − (the number of days in a year such that the month and the day of the month are simultaneously composite)
• (the second-smallest cube with only prime digits) ⋅ (the smallest perimeter of a Pythagorean triangle)/(the last digit to appear in the units place of a Fibonacci number) + (the greatest common divisor of the sums in degrees of the interior angles of convex polygons with an even number of sides) + (the number of subsets that you can form from the set {1,2,3,4,5,6,7,8,9} that do not contain two consecutive numbers) − (the only common digit of 2013 base 8 and base 9)

## Skyscrapers

### Tanya Khovanova and Joel Brewster Lewis

In skyscraper puzzles you have to put an integer from 1 to n in each cell of a square grid. Integers represent heights of buildings. Every row and column needs to be filled with buildings of different heights and the numbers outside the grid indicate how many buildings you can see from this direction. For example, in the sequence 213645 you can see 3 buildings from the left (2,3,6) and 2 from the right (5,6).

In mathematical terminology we are asked to build a Latin square such that each row is a permutation of length n with a given number of left-to-right and right-to-left-maxima. The following 7 by 7 puzzle is from the Eighth World Puzzle Championship.

Latin squares are notoriously complicated and difficult to understand, so instead of asking about the entire puzzle we discuss the mathematics of a single row. What can you say about a row if you ignore all other info? First of all, let us tell you that the numbers outside have to be between 1 and n. The sum of the left and the right numbers needs to be between 3 and n+1. We leave the proof as an exercise.

Let’s continue with the simplest case. Suppose the two numbers are n and 1. In this case, the row is completely defined. There is only one possibility: the buildings should be arranged in the increasing order from the side where we see all of them.

Now we come to the question we are interested in. Given the two outside numbers, how many permutations of the buildings are possible? Suppose the grid size is n and the outside numbers are a and b. Let’s denote the total number of permutations by fn(a, b). We will assume that a is on the left and b is on the right.

In a previous example, we showed that fn(n, 1) = 1. And of course we have fn(a, b) = fn(b, a).

Let’s discuss a couple of other examples.

First we want to discuss the case when the sum of the border numbers is the smallest — 3. In this case, fn(1, 2) is (n−2)!. Indeed, we need to put the tallest building on the left and the second tallest on the right. After that we can permute the leftover buildings anyway we want.

Secondly we want to discuss the case when the sum of the border numbers is the largest — n+1. In this case fn(a,n+1-a) is (n-1) choose (a-1). Indeed, the position of the tallest building is uniquely defined — it has to take the a-th spot from the left. After that we can pick a set of a-1 buildings that go to the left from the tallest building and the position is uniquely defined by this set.

Before going further let us see what happens if only one of the maxima is given. Let us denote by gn(a) the number of permutations of n buildings so that you can see a buildings from the left. If we put the shortest building on the left then the leftover buildings need to be arrange so that you can see a-1 of them. If the shortest building is not on the left, then it can be in any of the n-1 places and we still need to rearrange the leftover buildings so that we can see a of them. We just proved that the function gn(a) satisfies the recurrence:

Actually gn(a) is a well-known function. The numbers gn(a) are called unsigned Stirling numbers of the first kind (see http://oeis.org/A132393); not only do they count permutations with a given number of left-to-right (or right-to-left) maxima, but they also count permutations with a given number of cycles, and they appear as the coefficients in the product (x + 1)(x + 2)(x + 3)…(x + n), among other places. (Another pair of exercises.)

We are now equipped to calculate fn(1, b). The tallest building must be on the left, and the rest could be arranged so that, in addition to the tallest building, b-1 more buildings are seen from the right. That is fn(1, b) = gn-1(b-1).

Here is the table of non-zero values of fn(1, b).

b=2 b=3 b=4 b=5 b=6 b=7
n=2 1
n=3 1 1
n=4 2 3 1
n=5 6 11 6 1
n=6 24 50 35 10 1
n=7 120 274 225 85 15 1

Now we have everything we need to consider the general case. In any permutation of length n, the left-to-right maxima consist of n and all left-to-right maxima that lie to its left; similarly, the right-to-left maxima consist of n and all the right-to-left maxima to its right. We can take any permutation counted by fn(a, b) and split it into two parts: if the value n is in position k + 1 for some 0 ≤ k ≤ n-1, the first k values form a permutation with a - 1 left-to-right maxima and the last n - k - 1 values form a permutation with b - 1 right-to-left maxima, and there are no other restrictions. Thus:

Let’s have a table for f7(a,b), of which we already calculated the first row:

b=1 b=2 b=3 b=4 b=5 b=6 b=7
a=1 0 120 274 225 85 15 1
a=2 120 548 675 340 75 6 0
a=3 274 675 510 150 15 0 0
a=4 225 340 150 20 0 0 0
a=5 85 75 15 0 0 0 0
a=6 15 6 0 0 0 0 0
a=7 1 0 0 0 0 0 0

We see that the first two rows of the puzzle above correspond to the worst case. If we ignore all other constrains there are 675 ways to fill in each of the first two rows. By the way, the sequence of the number of ways to fill in the most difficult row for n from 1 to 10 is: 1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704. The maximizing pairs (a,b) are (1, 1), (1, 2), (2, 2), (2, 2), (2, 2), (2, 3), (2, 3), (2, 3), (3, 3).

The actual skyscraper puzzles are designed so that they have a unique solution. It is the interplay between rows and columns that allows to reduce the number of overall solutions to one.

## Integers and Sequences

The most personal puzzle that I wrote for the 2013 MIT Mystery Hunt was Integers and Sequences based on my Number Gossip database. I named it after the first lecture that I prepared after I decided to return to mathematics. It is still my most popular lecture.

Many of the clues in this puzzle are standard math problems that are very good for math competition training. Other clues are related to sequences and integer properties.

You might wonder why I often ask for the second largest integer with some property. Isn’t the largest one more interesting than the second largest? I do think that the largest number is more interesting, but exactly for this reason the largest number is available on my Number Gossip website and therefore is googleable. For example, my Number Gossip properties for 3000 contain the fact that 3000 is the largest palindrome in Roman numerals. This is why in the puzzle I used a slightly different clue, i.e. “the second largest three-letter palindrome in Roman numerals.”

It took me many hours to find non-googleable variations of interesting properties for this puzzle. Unfortunately, its non-googleability evaporated as soon as my solution was posted, right after the hunt. In any case some clues in this puzzle are useful for math competition training, and I plan to use them myself in my classes. The puzzle is attached below. I will post the solution in a couple of weeks.

*****

• (the largest integer n such that there exists a Platonic solid with n vertices, a Platonic solid with n edges, and a Platonic solid with n faces)
• (the largest two-digit tetrahedral number)/(the smallest value the second smallest angle of a convex hexagon with all integer degrees can have)
• (the number of positive integers less than 2013 that are divisible by 100, but not divisible by 70)
• (the number of two-digit numbers that produce a square when summed up with their reverse) ⋅ (the smallest number of weighings on a balance scale that guarantees to find the only fake coin out of 100 identical coins, where the fake coin is lighter than other coins)
• (the only two digit number n such that 2n ends with n) − (the second smallest, and conjectured to be the largest, triangular number such that its square is also triangular)
• (the smallest non-trivial compositorial number that is also a factorial)
• (the sum of the smallest three positive pronic numbers)

*****

• (the digit you get when you sum up the digits of 20132013 repeatedly until you get a single digit) − (the greatest common factor of the indices of the Fibonacci numbers divisible by 13)
• (the largest common divisor of numbers of the form p2 − 1 for primes p greater than three) − (the largest sum of digits that can appear on a 12-hour digital clock starting from 1:00 up to 12:59)
• (the largest Fibonacci number, such that it and all positive Fibonacci numbers less than it are deficient) + (the difference between the sum of all even numbers up to 100 and the sum of all odd numbers up to 100) − (the first digit of a four-digit square that has the first two digits the same and the last two digits the same)
• (the smallest composite Jacobsthal number) ⋅ (the only digit needed to express the number of diagonals of a convex hendecagon)/(the smallest prime divisor of 132013 + 1)
• (the smallest integer the fate of whose aliquot sequence is unknown) + (the largest amount of money in cents you can have in American coins without having change for 2 dollars) − (the repeated number in the aliquot cycle of 95) ⋅ (the second-smallest integer n such that the Russian word for n has n letters)
• (the smallest positive even integer that’s not a totient)

*****

• (the number of letters in the last name of a famous Russian writer whose year of birth many Russians use to help them memorize the digits of e)
• (the number of pluses you need to insert in a row of 20 fives so that the sum is 1000)
• (the number of positive integers less than 2013 such that not all their digits are distinct) − (the number of four-digit numbers with only odd digits) − (the largest Fibonacci square)
• (the number of positive integers n for which the sum of the n smallest positive integers evenly divides 18n)
• (the number of trailing zeroes of 2013!) − (the number of sets in the game of Set such that every feature is different on all three cards) − (an average speed in miles per hour of a person who drives somewhere with a speed of 420 miles per hour, then drives back using the same route with a speed of 210 miles per hour)
• (the smallest fortunate triangular number)
• (the smallest weird number)/(the only prime one less than a cube)
• (the third most probable product of the numbers showing when two standard six-sided dice are rolled)

*****

• (the largest integer number of dollars you can’t pay if you have an unlimited supply of 9-dollar bills and 13-dollar bills) − (the positive difference between the two prime numbers that do not share a unit digit with any other prime number)
• (the largest three-digit primeval number) − (the largest number of distinct SET cards without a set)
• (the number conjectured to be the second-largest number such that two to its power has no zeroes) − (the largest number whose cube has at most two distinct digits and no zeroes)
• (the number of 5-digit palindromic integers in base 5) + (the only positive integer that is five times the sum of its digits)
• (the only Fibonacci number that is a double of a prime) + (the only prime p such that p! has p digits) − (the only fixed point of look-and-say operation)
• (the only number whose concatenation with itself is prime)
• (the only positive integer that that differs by 1 from a square and a nonsquare cube) − (the largest number such that its divisors are each 1 less than a prime)
• (the smallest evil untouchable number)

*****

• (the alphanumeric value of MANIC SAGES) + (the sum of all three-digit numbers you can get by permuting digits 1, 2, and 3) + (the number of two-digit integers divisible by 9) − (the number of rectangles whose sides are composed of edges of squares of a chess board)
• (the integer whose standard Roman numeral representation is alphabetically later than all others) − (the number you get if you divide a three digit number with identical digits by the sum of the digits)
• (the largest even integer that is not a sum of two abundant numbers) − (the digit in the first position where e and π have the same digit)
• (the number formed by the last two digits of the sum: 1! + 2! + 3! + 4! + . . . + 2013!)
• (the only positive integer such that if you sum the digits and the squares of the digits, you get the original number back) + (the largest prime factor of the smallest Carmichael number)
• (the smallest multi-digit hyperperfect number such that more than half of its digits are the same) − (the sum of digits that cannot be the last digits of squares) ⋅ (the largest base n in which 8n is not written like 80) ⋅ (the smallest positive integer that leaves a remainder of 2 when divided by 3, 4, and 5)
• (the smallest three-digit brilliant number) − (the first decimal digit of the number that in hexadecimal gives the house number of Sherlock Holmes)

*****

• (the number of evil minutes in an hour)
• (the number of fingers on ten hands) − (the smallest number such that its square has a digit repeated three times)
• (the number of ways you can rearrange letters of MANIC)/(the number of ways you can rearrange letters of SAGES)
• (the only multi-digit Catalan number with digits in strictly decreasing order)
• (the smallest perfect number)

*****

• (the largest product of positive integers that sum up to 10) + (the smallest perimeter of a rectangle with integral sides of area 120) − (the day of the month of the second Thursday in a January that has exactly 4 Mondays and 4 Fridays)
• (the second-largest number with all distinct digits, such that all the words in its American English representation start with the same letter) + (the largest square-free composite number that contains each of the digits 1, 2, 3, 4 exactly once in its prime factorization) + (the number of ways you can flip a coin 10 times so that the number of heads is the same as the number of tails) + (the smallest positive integer such that 2 to its power contains 2013 as a substring) + (the sum of five prime numbers formed from the digits 2, 3, 5, 7, 8, 9 where each digit is used exactly once) + (the number of days in a year where the day of the month is odious) + (the sum of the digits each of which spelled out has an alphanumeric value equal to the meaning of life, the universe, and everything) ⋅ (the sum of all prime numbers p such that p + 20 and p + 40 are also prime) + (the first digit of the total number of legal moves of the Black king in chess)
• (the second-largest three-letter palindrome in Roman numerals)/((the smallest composite number not divisible by any of its digits)/(the last digit of 20132013) − (the digit in position 2013 of the string formed by concatenation of all integers into one stream: 123456789101112…)) − (the number of days in a year such that the month and the day of the month are simultaneously composite)
• (the second-smallest cube with only prime digits) ⋅ (the smallest perimeter of a Pythagorean triangle)/(the last digit to appear in the units place of a Fibonacci number) + (the greatest common divisor of the sums in degrees of the interior angles of convex polygons with an even number of sides) + (the number of subsets that you can form from the set {1,2,3,4,5,6,7,8,9} that do not contain two consecutive numbers) − (the only common digit of 2013 base 8 and base 9)

## Weighing Coins during the Mystery Hunt

The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:

There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.

Actually, it is possible to find the real coin in six weighings. Can you do that?

## Solving In the Details

I posted the puzzle In the Details two weeks ago. This is the most talked-about puzzle of the 2013 MIT Mystery Hunt. The author Derek Kisman invented this new type of puzzle and it is now called a Fractal Word Search. I anticipate that people will start inventing more puzzles of this type.

Let’s discuss the solution. The words in the given list are very non-random: they are related to fractals. How do fractals work in this puzzle? The grid shows many repeating two-by-two blocks. There are exactly 26 different blocks. This suggests that we can replace them by letters and get a grid that is smaller, for it contains one-fourth of the number of letters. How do we choose which letters represent which blocks? We expect to see LEVEL ONE in the first row as well as many other words from the list. This consideration should guide us into the matching between letters and the two-by-two blocks.

The level one grid contains 18 more words from the list. But where are the remaining words? So we have level one, and the initial grid is level two. The substitution rule allows us to replace letters by blocks and move from level one to level two. When we do this again, replacing letters in level two by blocks, we get the level three grid. From there we can continue on to further levels. There are three words from the list on level three and one word on level four. But this is quickly getting out of hand as the size of the grid grows.

Let’s step back and think about the next step in the puzzle. Usually in word search puzzles, after you cross out the letters in all the words you find, the remaining letters spell out a message. What would be the analogous procedure in the new setting of the fractal word search? In which of our grids should we cross out letters? I vote for grid number one. First, it is number one, and, second, we can assume that the author is not cruel and put the message into the simplest grid. We can cross-out the letters from words that we find in level one grid. But we also find words in other levels. Which letters in the level one grid should we cross out for the words that we find in other levels? There is a natural way to do this: each letter in a grid came from a letter in the previous level. So we can trace any letter on any level to its parent letter in the level one grid.

We didn’t find all the words on the list, but the missing words are buried deep in the fractal and each can have at most three parent letters. I leave to the reader to explain why this is so. Because there are so few extra letters, it is possible to figure out the secret message. This is what my son Sergei and his team Death from Above did. They uncovered the message before finding all the words. The message says: “SUM EACH WORD’S LEVEL. X MARKS SPOT.” Oh no! We do need to know each word’s level. Or do we? At this point, the extra letters provide locations of the missing words. In addition, if a word on a deep level has three parents, then it has to be a diagonal word passing through a corner of one of the child’s squares. So our knowledge of extra letters can help us locate the missing words faster.

Also, the message says that the answer to this puzzle will be on some level in the part of the grid that is a child of X. Luckily, but not surprisingly, there is only one letter X on level one. The child of X might be huge. But we could start looking in the center. Plus, we know from the number of blanks at the end of the puzzle, that the answer is a word of length 8. So Sergei and his team started looking for missing words and the answer in parallel. Then Sergei realized that the answer might be in the shape of X, so they started looking at different levels and found the answer before finding the last word on the list. The answer was hiding in the X shape in the center of the child of X on level 167: HUMPHREY.

```H..Y
.UE.
.RM.
H..P```

## Cambridge Waldo

Cambridge Waldo puzzle from the 2013 MIT Mystery Hunt was supposed to be easy. Its goal was to get people out of the building for some fresh air. I made this puzzle jointly with Ben Buchwald, Adam (Pesto) Hesterberg, Yuri Lin, Eric Mannes and Casey McNamara. The puzzle consists of 50 pictures of different locations in Cambridge; one of the above individuals was hiding in each picture. Let me use this opportunity to thank my friends for starring in my puzzle and being inventive while doing it.

The puzzle starts with a group picture of my stars. The caption to the picture gives their names. The fact that they are standing in alphabetical order is a clue.

Out of the 50 pictures, each person appears in exactly ten pictures. If you mark the locations of one person on a map, they look like a letter. For example, below are Ben’s locations that form a letter “S”. When you put the letters in the alphabetical order by people names you get the answer to the puzzle: SCAMP.

As you can see, you do not need all ten locations to recognize the letter. You might be able to recognize the letter with five locations, or at least significantly reduce possibilities for the letter. Besides, you do not need all the letters to recognize the answer. We thought that this was an easy puzzle.

And, to make it even easier, the order in which we posted the pictures was not completely random. The pictures of one person were in the order one might walk from one location to another. This played two important roles. If you recognize the person but do not recognize the location on the picture, you can make an approximate estimation of the location because it must be on the path between the previous and next locations. If you recognize the location but not the person, you can guess the person by checking whose path it fits better.

It was difficult to hide people, especially when there were no other people around. So we sometimes used props. We only used one prop per person. Here you can see Pesto with his sarongs in plain view. In the other picture (below) he is hiding under a white sarong. Yuri had a bicycle helmet. In one of the pictures, she hid so well that you couldn’t see her — but you could see her helmet. Ben had a bear hat. In one of the pictures you can only see a shadow of a person, but this person was clearly wearing a hat with bear ears. Eric didn’t have a prop, but my car was eager to make a cameo appearance at the Mystery Hunt, so I hid him in my car in one of the pictures.

As you might guess I made the pictures of different people at different times. So Ben Buchwald was the one who realized that solvers might differentiate people by looking at the data of the picture files. He carefully removed the original time stamps.

Despite our best intentions, our test-solvers decided not to leave their comfy chairs, but rather to use Google-StreetView. We strategically made some of the pictures not Google-StreetViewable, but our test-solvers still didn’t leave the comfort of their chairs. They just became more inventive. I do not know all the things they did to solve the puzzle, but I heard about the following methods:

• Finding a website with parking meter locations by meter number.
• Looking for one-way streets in the proper configuration to find likely places for One-Way/Do-Not-Enter signs.
• Looking up the street cleaning signs in the street cleaning schedule.
• Differentiating the streets by their separator line: double, single, or no line.

I have yet to understand why this puzzle was difficult for the Mystery Hunt teams.

## Open Secrets Revealed

Here is the solution to the Open Secrets puzzle I published recently. Through my discussion of this solution, you’ll also get some insight into how MIT Mystery Hunt puzzles are constructed in general.

I’ve included the puzzle (below) so that you can follow the solution. The puzzle looks like a bunch of different cipher texts. Even before we started constructing this puzzle, I could easily recognize the second, the seventh, and the last ciphers. The second is the cipher used by Edgar Allan Poe in his story, The Gold-Bug. The seventh cipher is a famous pigpen (Masonic) cipher, and the last is the dancing men cipher from a Sherlock Holmes story. Luckily you do not need to know all the ciphers to solve the puzzle. You can proceed with the ciphers you do know. With some googling and substitution you will translate these three pieces of text into: COLFERR, OAOSIS OF LIFEWATER, and RBOYAL ARCH.

These look like misspelled phrases, each of which has an extra letter. However, there are no typos in good puzzles. Or, more precisely, “typos” are important and often lead to the answer. So now I will retype the deciphered texts with the extra letter in bold: COLFERR, OAOSIS OF LIFEWATER and RBOYAL ARCH. In the first word it is not clear which R should be bold, but we will come back to that later.

At this point you should google the results. You may notice that the “royal arch” leads you to the Masons, who invented the pigpen cipher. From this, you can infer the structure of the ciphers and the connections among them. Indeed, a translation of one cipher refers to another. So you should proceed in trying to figure out what the texts you have already deciphered refer to. Eoin Colfer is the author of the Artemis Fowl series that contains a Gnomish cipher, and Oasis of Lifewater will lead you to Commander Keen video games with their own cipher. When you finish translating all of the ciphers, you get the following list:

• AQUAL MAGNA: in Coldplay’s X&Y Baudot code
• COLFERR: in Edgar Allen Poe’s “The Gold-Bug” cipher
• DOCTOR WEFRNSTROM: in Daedric from the Elder Scrolls series
• ELEMENTARHY: in Futurama’s Alienese
• MYLKO XYLOTO: in Commander Keen’s Standard Galactic Alphabet
• NEVEROMORE: in Bionicle’s Matoran alphabet
• OAOSIS OF LIFEWATER: in the Pigpen (Masonic) cipher
• ORANGE DYARTWING: in Eoin Colfer’s Gnommish from Artemis Fowl series
• RBOYAL ARCH: in Conan Doyle’s “The Adventure of the Dancing Men” code

The bold letters do not give you any meaningful words. So there is more to this puzzle and you need to keep looking. You will notice that the translations are in alphabetical order. This is a sign of a good puzzle where nothing is random. The alphabetical order means that you need to figure out the meaningful order.

To start, the phrases reference each other, so there is a cyclic order of reference. More importantly, the authors of the puzzle added an extra letter to each phrase. They could have put this letter anywhere in the phrase. As there is nothing random, and the placements are not the same, the index of the bold letter should provide information. If you look closely, you’ll see that the bold letters are almost all in different places. If we choose the second R in COLFERR as an extra R, then the bold letter in each text is in a different place. Try to order the phrases so that the bold letters are on the diagonal. You’ll see that this order coincides with the reference order, which gives you an extra confirmation that you are on the right track. So, let’s order:

• RBOYAL ARCH
• OAOSIS OF LIFEWATER
• MYLKO XYLOTO
• AQUAL MAGNA
• NEVEROMORE
• COLFERR
• ORANGE DYARTWING
• DOCTOR WEFRNSTROM
• ELEMENTARHY

Now the extra letters read BOKLORYFH. This is not yet meaningful, but what is this puzzle about? It is about famous substitution ciphers. The first and most famous substitution cipher is the Caesar cipher. So it is a good idea to use the Caesar cipher on the phrase BOKLORYFH. There is another hint in the puzzle that suggests using the Caesar cipher. Namely, there are many ways to clue the dancing men code. It could be Conan Doyle, Sherlock Holmes, and so on. For some reason the authors chose to use the word ELEMENTARY as a hint. Although this is a valid hint, you can’t help but wonder why the authors of the puzzle are not consistent with the hints. Again, there is nothing random, and the fact that the clues are under-constrained means there might be a message here. Indeed, the first letters read ROMAN CODE, hinting again at the Caesar shift. So you have to do the shift to arrive at the answer to this puzzle, which is ERNO RUBIK.

## Turnary Reasoning

The most difficult puzzle I wrote for the MIT Mystery Hunt 2013 was Turnary Reasoning. I can’t take credit for the difficulty: I designed the checkers positions; they were expectedly the easiest. Timothy Chow created the chess positions, and Alan Deckelbaum created the MTG positions. As the name of the puzzle suggests, you need to find whose turn it is in each position or, as the flavor text suggests, decide that the position is impossible.

I tried to solve the chess positions myself and was charmed by their beauty. The most difficult one was the first chess puzzle presented below. Find whose turn it is or prove that the position is impossible.

## The Most Difficult Hunt Puzzle: 50/50

The puzzle titled “50/50” was the most difficult puzzle in MIT Mystery Hunt 2013. It is a puzzle in which information is hidden in the probability distribution of coin flips. I consider it the most difficult puzzle of the hunt because it took the longest time to test-solve and we were not able to solve all four layers of the original puzzle. As a result, one of the layers was removed. I think this puzzle is very important and should be included in statistics books and taught in statistics classes. If I were ever to teach statistics, I would teach this puzzle. By the way, this elaborate monstrosity (meant as a compliment) was designed by Derek Kisman.

I am not sure that the puzzle is working on the MIT server. The puzzle is just a coin flip generator and gives you a bunch of Hs (heads) and Ts (tails). Here is the solution.

When you flip a coin, the first thing to check is the probability of heads. In this puzzle it is fifty percent as expected. Then you might check probabilities of different sequences of length 2 and so on. If you are not lazy, you will reach length 7 and discover something interesting: some strings of length seven are not as probable as expected. The two least probable strings are TTHHTTH and HTHHTTT, with almost the same probability. The two most probable strings are TTHHTTT and HTHHTTH, with the matching probability that is higher than expected. All oddly behaving strings of length 7 can be grouped in chunks of four with the same five flips in the middle. In my example above, the five middle flips are THHTT. Five flips is enough to encode a letter. The probabilities provide the ordering, so you can read a message. In the version I tested it was “TAXINUMBLOCKS.” In the current version it is “HARDYNUMBLOCKS.” Keep in mind that the message encoded this way has to have all different letters. So some awkwardness is expected. The message hints at number 1729, a famous taxicab number, which is a clue on what to do next in the second step.

What do you do with number 1729? You divide the data in blocks of 1729 and see how the k-th flip in one block correlates with the k-th flip in the next block. As expected, for most of the indices there is no correlation. But some of the indices do have correlation. These indices are close together: not more than 26 flips apart. Which means the differences will spell letters. Also, there is a natural way to find a starting point: the group of indices spans only a third of the block. In the original version the message was: “PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJKHEREHAVEAPIECEOFPIE.”

Now I want to discuss the original version, because its solution is not available online. Here is Derek’s explanation of what happens in the third step:

So, this punny message is another hint. In fact the sequence of coin flips conceals pieces of the binary representation of Pi*e. These pieces are of length 14 (long enough to stand out if you know where to look, but not long enough to show up as significant similarities if you compare different sessions of flips), always followed by a mismatch. They occur every 1729 flips, immediately after the final position of the 1729-block message. The HERE in the message is intended to suggest looking there, but you can probably also find them (with more effort) if you search for matches with Pi*e’s digits.
The 14-flip sequences start near the beginning of the binary representation of Pi*e and continue to occur in order. (ie, every 1729 flips, 14 of them will be taken straight from Pi*e.) However, between sequences, either 1, 3, or 5 digits will be skipped. These lengths are a sequence of Morse code (1=dot, 3=dash, 5=letter break) that repeats endlessly, with two letter breaks in a row to indicate the start:
- …. ..- ..- ..- - ..- -..- ..- ..- ..- …. ..- …. - ..- ..- …. ..- ….
Translated, this gives the message “THUUUTUXUUUHUHTUUHUH”.
(Aside: I didn’t use Pi or e individually, because one of the first things I expect some teams will try is to compare the sequence of flips with those constants!)

As I said before, we didn’t solve the third step. So Derek simplified it. He replaced “PIECEOFPIE” by “BINARYPI”, and made it the digits of Pi, rather than of Pi*e. We still couldn’t solve it. So he changed the message from the second step to hint directly at the fourth step: “PLEASEHELPTRAPPEDINCOINFLIPPINGFACTORYJUSTKIDDINGTHUUUTUXUUUHUHTUUHUH.” But the binary Pi was still trapped in the coin flipping factory.

Here is Derek’s explanation of the fourth step:

Almost there! This message looks like some sort of flip sequence, because it has several Ts and Hs in there, but what of the Us and Xs? Well, U just stands for “unknown”, ie, we don’t care what goes there. And there’s only one X, so it seems significant!
The final step is to look for every occurrence of this pattern in the sequence. The flips that go where the X is are the final channel of information. You’ll find that they repeat in an unvarying pattern (no noise!) with period 323=17*19. There’s only one way to arrange this pattern into a rectangular image with a blank border, and it gives the following image:

`.................`
`...X..XXX.XXX....`
`...X..X...X.X....`
`...X..XXX.XXX....`
`...X..X...XX.....`
`...X..X...X.X....`
`...X.....X.......`
`...X.....X.......`
`...X....XXX......`
`...X.....X.......`
`...X.............`
`...X.....XXX...X.`
`...X....XXXXX.XX.`
`..X....XX.XXXXX..`
`.X......XXXXXX...`
`.X...X.XXXXXXXX..`
`..XXX...XXXXX.XX.`
`.........XXX...X.`
`.................`

The final answer is the French word for fish, POISSON, a word heavily related to statistics!

The answer POISSON didn’t fit in the structure of the Hunt. So Derek was assigned a different answer: MOUNTAIN. He changed the picture and it is now available in the official solution to the puzzle. He adjusted his code for coin flips so that the picture of a mountain is hidden there. But the digits of Pi are still trapped in the flips. They are not needed for the solution, but they are still there.

Derek kindly sent to me his C++ program for the latest version of the puzzle. So if the MIT website can’t generate the flips, you can do it yourself. And play with them and study this amazing example of the use of statistics in a one-of-a-kind puzzle.