Solution: Ministry of Word Searches

Answer: PRESIDENT

Written by Anderson Wang, Jon Schneider, and Lewis Chen

Upon opening the puzzle, we are greeted with a fairly generic 11x11 wordsearch grid that changes every time the page is refreshed, as well as the opportunity to input a puzzle ID. From looking through several word searches, we can see the same words seem to appear in each one (one the particularly jumps out in a lot of grids is TRUDEAU, for reasons that will soon become clear). At the same time, there appears to be a message starting with “GREAT WORK” placed in every grid, presumably on the squares that aren’t used by the word search.

After solving some word searches, we can eventually deduce the following:

1. The same set of 9 words appear in every word search, though in different positions.
2. Whenever two words intersect in a square, one of them overwrites the other. In fact, the words can be put in a priority order such that words with higher priority always overwrite words with lower priority. This order from highest to lowest is: TRUDEAU, CAMPBELL, TURNER, DIEFENBAKER, BENNETT, LAURIER, BOWELL, ABBOTT, MACKENZIE.
3. Whenever a word intersects the edge of a grid, it continues from the opposite edge and in the same direction (i.e. word placement is toroidal).
4. The “GREAT WORK...” filler message is placed on the squares not used by the word search, from left-to-right and top-to-bottom.

So, what are the set of words? With a few names, it’s possible to Google them (or you may deduce this from TRUDEAU) - it turns out these are all Canadian Prime Ministers. Additionally, the prime minister “priority” order from lowest to highest is identical to their order from earliest to most recent (this allows us to determine that Trudeau refers to the son and not the father). Taking the order in which the prime ministers served, disregarding duplicates, these are the 2nd, 3rd, 5th, 7th, 11th, 13th, 17th, 19th, and 23rd. In other words, they really are prime ministers!

After looking at various grids, we might realize that the “filler message” always seems to cut inconveniently early: it starts off “GREAT WORK YOUR FIRST CLUE IS THE ANSWER HOLDS NINE LETTERS” and ends around “OK YOU MUST NOW ISOLATE THE UN...”. So one thing we might want to do in order to reveal more letters is to find a configuration where most of the words overlap each other and thus have a large amount of filler material generated.

However, to do this we must first figure out how the words are placed. This may be most readily evident with MACKENZIE, which only has two possible configurations, alternating between the two, and Mackenzie also happens to be the 2nd prime minister. Looking at other prime ministers, we can see that indeed, the Nth prime minister has N possible positions and cycles between them every N ID numbers. Furthermore, for ease of data collection, both the starting location of each word and its direction transform “linearly” over the course of the cycle. That is, the starting location of each word moves the same number of rows and columns between each two consecutive puzzles in a cycle (possibly wrapping around the grid), and the direction from start to end of the word rotates by the same angle between each two consecutive puzzles. See the appendix for more details and a spreadsheet of all possible word locations.

Phew! Armed with this knowledge (or being sufficiently lucky - you can probably get enough letters to understand the objective about 1% of the time), we may determine the message in its entirety, although you probably can understand the objective without getting every letter:

GREAT WORK YOUR FIRST CLUE IS THE ANSWER HOLDS NINE LETTERS OK YOU MUST NOW ISOLATE THE UNIQUE VALID WORD SEARCH!

(For the curious, the last character that can be generated is indeed an exclamation point. It can be found at two ID’s in the first 100,000,000: ID’s 23,607,102 and 49,853,322. Both of these involve having all words on the top-left to bottom-right diagonal, the third column, and fifth row.)

The filler message gives us two pieces of information: namely, that the answer is nine letters long, and there exists a unique configuration of words that gives a valid word search. After all, all of this words overlapping other words and crossing the edges nonsense really doesn’t make for a good word search.

Indeed, there is only one grid satisfying the two conditions that: 1) words do not wrap around grid boundaries, and 2) any intersections of words must agree. One way to find this grid by hand is by first noting that MACKENZIE and DIEFENBAKER each only have one possibility that do not cross the edge of the grid. Then we can work our way up from ABBOTT (only 3 possible placements) to TRUDEAU (23 possibilities) - it turns out that at each step there is a unique placement that satisfies our two conditions. Here is the resulting grid:

We could generate this grid ourselves by directly placing the words and the filler message, but if we wanted to find the ID of this word search, perhaps to check that there is no special message there (and indeed there isn’t), we could apply the Chinese Remainder Theorem to our 9 modular congruences to get it, which turns out to be 63,888,718. A more detailed explanation of how to apply the Chinese Remainder Theorem is in the appendix.

As you can see, all words can be found like a normal word search! That’s great, but what now? If we inspect the diagonal, it spells out what we must do next: GRAHAM’S NO. ID. That is, we must now go to the ID of Graham’s number, a notable large number in mathematics.

Of course, Graham’s number is larger than 10^{8 [citation needed]}. Since the server refuses to generate grids with IDs larger than 10⁸ (not to mention that Graham's number would be infeasible to enter in the box), we’ll have to calculate things another way. If we can compute Graham’s number modulo every prime from 2 to 23, then that’ll let us generate the grid, since we can place all the names from MACKENZIE to TRUDEAU, followed by the filler message. Some ways of doing this include:

1. You can use Euler’s theorem or Fermat’s little theorem, namely that for coprime (x,n), x^φ(n) = 1 mod n, where φ is Euler's totient function. Since Graham’s number is a sufficiently large power tower of 3’s, this means that, for example, 3^33... mod 23 is equal to 3^x mod 23, where x=3^33... mod 22. To save repeating work, we can compute Graham’s number mod n for n from 1-23 in that order, and at each step we can reuse a previous step’s computation.
2. Without knowledge of the above number theory, it is still possible to deduce the period of powers of 3 mod n by repeatedly multiplying 3 until you reach 1 mod n. This is essentially rederiving the above theorems without necessarily having a proof. This method is the “intended” way if you don’t immediately jump to Euler’s theorem, and we explain it in more detail in the appendix.
3. We could write a computer program to calculate successive power towers of 3s modulo a number, and discover that it becomes constant fairly quickly. This is a little trickier for the larger primes since power towers grow very fast.
4. After calculating Graham’s number mod some smaller numbers (say, 1 through 8), perhaps with the method in 3), we can plug the sequence into OEIS and see if it exists. Turns out, it does.
5. Some careful Googling (e.g. “graham’s number mod n”) can pull up scripts that already do this computation or the OEIS sequence.

Anyways, now that we have Graham’s number mod every prime from 2 to 23, we can generate the resulting grid by hand as stated above:

(As a side note, we can also compute this grid’s ID with the Chinese Remainder Theorem, but it turns out it has to be 137,693,037 mod 223,092,870. Since the ministry only accepts IDs up to 100,000,000, we are actually forced to make this final grid by hand. Though, it is possible to bypass most of the work by, for example, visiting the grid at 137693037-223092870/2 = 26146602 and then moving MACKENZIE)

Reading the diagonal again gives us the cluephrase LEADER OF USA. Knowing that the answer is nine letters long, the answer is therefore PRESIDENT.

Author’s Notes

Anderson: Early on in the writing process, I proposed a puzzle consisting of a word search that changed over time, and several of us brainstormed potential ideas for how it would work, but none of them ended up being that promising. Later, Lewis came up with the idea of having a procedurally-generated word search that included sets of things, with one key step of the puzzle being to use the generation rules to find a word search which had enough leftover letters to read a message. This idea went through many iterations: in the beginning, we were still going with the dates/time idea, so the puzzle was going to be The Mezzacotta Word Search, in reference to the mezzacotta webcomic that can generate a random comic for each day all the way back to 9999999999999 BC.

However, we had trouble coming up with an interesting way to use dates to generate a puzzle, so we eventually decided on just using and ID number, and word placement would be done by taking the number mod various primes. At first, we wanted to do a "No Man's Wordsearch" with over 18 quintillion word searches in reference to the video game No Man's Sky (turns out that 4*9*25*7*11*13*17*19*23*29*31*37*41*43*47 is equal to 2^64 to 6 significant digits!), but eventually I asked Jon for help and he reduced it to the much more reasonable (though still very large) size that you see now. Another fun fact: we spent quite a while discussing how to fit prime ministers into the grid before Lewis realized how appropriate "prime" ministers were for this puzzle!

The last step of finding the grid with ID Graham's number was somewhat contentious. We went back and forth a lot on whether it would be "fair" to include it, and eventually decided on leaving it in, partially because some testsolvers loved the step, but mostly because we believed that most teams who made it to the final step would be able to do it or find an alternative route like OEIS, googling "graham's number mod n", or just roping in a mathy friend. It did end up being unfortunate how this made a long puzzle even longer in a hunt filled with long puzzles, but I do hope that it was memorable to at least a few solvers.

Another title this puzzle once had was “The 10,000² Puzzle Squares”, as a reference to past “The 10,000 Puzzle X” puzzles in Mystery Hunt 2015, Mystery Hunt 2018, and the 2018 Caltech Puzzle Hunt. However, this was quickly changed, as the reference was pretty forced and also felt somewhat "insular", and besides, this puzzle works very differently from the others.

Appendix

Cycles of word positions/directions

Note that the row starts at 6 and increases by 1 each time to 10, until it hits the end of the cycle and starts from 6 again. Similarly, the column starts at 1 and decreases by 2 each time, ending up at 4 before restarting the cycle. This addition/subtraction “wraps around”, which is how 1 minus 2 ends up at 10 (or in slightly mathier terms, 1 minus 2 is congruent to 10 modulo 11).

The same relationship holds for directions: BOWELL always goes in the north-east direction which isn’t that interesting, but for LAURIER, the 7th prime minister, the directions in the first 9 grids are NW, E, SW, N, SE, W, NE, NW, E. We can see that the direction always rotates 135 degrees clockwise between the first seven IDs before restarting with NW.

(The above “constant differences” observation is not necessary to solve the puzzle, but is intended to cut down the amount of time collecting data, since once you figure out the pattern you can extrapolate all possible positions of a word from the first two or three grids.)

For reference and for completeness, here is a sheet listing all the possible positions for each prime minister (the position of the Pth prime minister in the grid with ID number N, is given by N modulo P; this number is highlighted in blue to the above-left of each grid).

Modular congruences and Chinese Remainder Theorem

If we wanted to generate the ID of the “valid word search” grid, we know that the ID must be 0 mod 2 for the correct MACKENZIE placement, 10 mod 13 for the correct DIEFENBAKER placement (this is the only one that doesn’t cross the edge, as can be seen in cell DR62 on the spreadsheet), 1 mod 3 for the correct ABBOTT placement (the only one that doesn’t conflict with MACKENZIE), 3 mod 5 for BOWELL, etc.

All of these congruence relations can be combined with the Chinese Remainder Theorem, which is a fancy way of stating that if, for example, a number must be 0 mod 2 and 10 mod 13, then there is one and exactly one number mod 2*13=26 that satisfies this (in this case it’s 10 mod 26). Then, if our ID is 10 mod 26 and 3 mod 5, there is a unique number mod 26*5=130 that satisfies this (in this case it’s 88, which you can verify yourself). Basically, we can “build up” primes one by one until we get to some number mod 2*3*5*7*11*13*17*19*23.

As one final note, let’s say that we know the ID is 10 mod 26 and 3 mod 5. How do we actually compute the number 88 mod 130? One method involves the extended Euclidean algorithm (mentioned in the Wikipedia page on the Chinese Remainder Theorem), but a simpler way (which is also mentioned on the Wikipedia page) would be something like:

1. There are 5 possible numbers mod 130 that are equal to 10 mod 26. These are 10, 10+26, 10+26*2, 10+26*3, and 10+26*4. We need to pick the one that is 3 mod 5.
2. We could test each of these by hand, and that would work fine, but we can also be a little “smarter” about it: since 10 is 0 mod 5, and 26 is 1 mod 5, we can already tell that we need to add 26 three times to get up to 3 mod 5.

This same strategy works with 26 replaced by x and 5 replaced by y for any x and y, as long as x and y share no prime factors.

Computing Graham’s number modulo primes

First, Graham’s number can be expressed as a very large “power tower” of 3s, i.e. it is of the form 3^33... Since 3 to the power of anything is odd, we can deduce that Graham’s number is 1 mod 2. And clearly it is divisible by 3, so it is 0 mod 3. What about 5?

One way to approach this is by looking at the successive powers of 3 modulo 5. 3⁰ is 1, 3¹ is 3, 3²=9 which is 4 mod 5, 3³=27 which is 2 mod 5, 3⁴=3³*3=2*3=1 mod 5, and it repeats from here (1, 3, 4, 2, 1, 3, 4, 2, etc.). So that means that 3^x mod 5 depends on the value of x mod 4, since this sequence repeats every 4. In other words, if x = y mod 4, then 3^x = 3^y mod 5. This can be represented by the following table:

That reduces the problem to calculating 3^33... modulo 4. We can repeat the same logic to find that the powers of 3 alternate between 1 and 3 mod 4 (3⁰=1 mod 4, 3¹=3 mod 4, 3²=1 mod 4, etc.), so 3^z is 1 mod 4 if z is even, and 3 mod 4 if z is odd. Because z in this case equals (yet again) 3^33..., it is odd and therefore 3^33... is equal to 3 mod 4. And finally, consulting our table above means that 3^33... is equal to 3³=2 mod 5.

We can use this exact same technique to calculate Graham’s number modulo the rest of the primes. This seems like a daunting task, but we can save a lot of time by “saving” the results of previous computations. For example, let’s assume that we’ve already computed the value of the power tower of 3s modulo every number from 1 to 22, and want to compute it for 23. It turns out that the powers of 3 modulo 23 cycle every 11, so 3^33... mod 23 only depends on 3^33... mod 11. But from our assumption, we already know this number (it turns out to be 9), so we just need to compute 3⁹ mod 23 and don’t need to go further down.

As a side note, the method we’ve described above is pretty much the same as applying Euler’s theorem or Fermat’s little theorem; we’ve essentially rederived them for ourselves.