# Can You Buy The Right Shirt?

Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,^{1} and you may get a shoutout in the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.

## Riddler Express

From Irwin Altrows comes a problem about a problematic business model:

The Riddler Shirt Store sells *N* kinds of shirts, each kind with a picture of a different famous mathematician. Unfortunately, on average, 80 percent of orders are returned.

Thatâs because the companyâs website has customers order their shirts using a code (from 1 to *N*), but does not state which code corresponds to which shirt. Each customer knows which mathematician â and therefore which shirt â they want.

But to get that desired shirt, they enter a random shirt code and order the corresponding shirt without knowing which mathematician theyâll get. If that shirt depicts the wrong mathematician, they randomly select a different (untested) code, and repeat this process until the desired shirt arrives.

How many different shirts does the store sell?

## Riddler Classic

From Graydon Snider comes a pen pal puzzle:

Graydon is about to depart on a boating expedition that seeks to catch footage of the rare aquatic creature, *F. Riddlerius*. Every day he is away, he will send a hand-written letter to his new best friend, David Hacker.^{2} But if Graydon still has not spotted the creature after *N* days (where *N* is some very, very large number), he will return home.

Knowing the value of *N*, Graydon confides to David there is only a 50 percent chance of the expedition ending in success before the *N* days have passed. But as soon as any footage is collected, he will immediately return home (after sending a letter that day, of course).

On average, for what fraction of the *N* days should David expect to receive a letter?

## Solution to last weekâs Riddler Express

Congratulations to đ Peter Norvig đ of Palo Alto, California, winner of last weekâs Riddler Express.

Last week, you were driving from Riddler City to Puzzletown, which are separated by 1,500 miles of highway. On a full charge, your electric car was able to drive 500 miles before it needed a recharge. Fortunately, the highway had charging stations every 250 miles, with the first in Riddler City and the last in Puzzletown.

Once you committed to charging your car at a station, you had to wait until it was fully charged. For the purposes of this riddle, you were asked to assume that charging occured at a constant rate. Also, you assumed that you could comfortably roll into a charging station just as your car ran out of power and recharge it there.

You began your journey with a full charge. Before heading out, you wanted to come up with an itinerary for which charging stations youâd stop at along the way. Being impatient, you also wanted to arrive in Puzzletown as quickly as possible, meaning you wanted to minimize the time spent waiting at charging stations.

How many distinct itineraries were possible?

Between Riddler City and Puzzletown, there were five charging stations (i.e., one less than 1,500 divided by 250). If your goal was to make as few stops as possible, then you should have stopped at the second and fourth charging stations at mile markers 500 and 1,000 respectively. But if you didnât worry about time spent decelerating into charging stations (which wasnât explicitly mentioned in the puzzle), other itineraries were possible.

As long as you didnât skip two charging stations in a row, youâd successfully make it to Puzzletown. But to be as efficient as possible, solver Madeline Argent noted that you *didnât* want to stop at the last charging station. If you had, then you would have arrived at Puzzletown still able to travel another 250 miles, meaning you wasted time charging your car more than you needed somewhere along the way.

So how many distinct itineraries were there that skipped the last charging station but never skipped two stations in a row? Because you skipped the last charging station, you *had* to charge at the penultimate station. That left eight cases to consider: to charge or not to charge at each of the first three stations (at mile markers 250, 500 and 750). Among these eight cases, three left you in need of tow service: charging at 250 miles but skipping 500 and 750, charging at 750 but skipping 250 and 500, and skipping all three stations.

The remaining **five** itineraries allowed you to reach Puzzletown with minimal charging time. So come on down to Puzzletown!

## Solution to last weekâs Riddler Classic

Congratulations to đ Stefano Perfetti đ, winner of last weekâs Riddler Classic.

Last week you tried your hand at Anigrams, a game created by Friend-of-The-Riddlerâ˘ Adam Wagner. In the game, you had to unscramble successively larger, nested collections of letters to create a valid âchainâ of six English words between four and nine letters in length.

For example, a chain of five words (sadly, less than the six needed for a valid game of Anigrams) could be constructed using the following sequence, with each term after the first including one additional letter than the previous term:

- DEIR (which unscrambles to make the words DIRE, IRED or RIDE)
- DEIRD (DRIED or REDID)
- DEIRDL (DIRLED, DREIDL or RIDDLE)
- DEIRDLR (RIDDLER)
- DEIRDLRS (RIDDLERS)

What was the longest chain of such nested anagrams you can create, starting with four letters?

All valid words had to come from Peter Norvigâs word list (a list weâve used previously here at The Riddler). And coincidentally, this is the very same Peter who won this past weekâs Riddler Express.

Given the incredibly vast space of words and letters, most solvers turned to their computers for some automated assistance. Josh Silverman first developed an algorithm that checked which words could be reached in Anigrams. After listing all the four-letter words, Josh looked at all the five-letter words and noted the ones for which removing a letter resulted in an anagram of a four-letter word. Then, he looked at all the six-letter words and noted the ones for which removing a letter resulted in an anagram of a valid *five*-letter word, and so on. By keeping track of each wordâs precursor words, Josh was able to identify the longest chains.Â

For example, here was the chain Stefano found. For clarity, I have underlined the new letter added with each subsequent word.

- INTO
- NITON
- NITONS
- INTONES
- MENTIONS
- NOMINATES
- ANTINOMIES
- INSEMINATOR (!)
- TERMINATIONS
- ANTIMODERNIST
- DETERMINATIONS
- INTERMEDIATIONS
- INDETERMINATIONS

It turned out there were quite a few chains of this length, but they all ended with either INDETERMINATIONS or UNDERESTIMATIONS, both of which were 16 letters long. That meant the longest chains all had **13 words**.

For extra credit, you had to determine the total number of Anigrams games there were â that is, how many valid sets there were of four initial letters, and then five more letters added one at a time in an ordered sequence, that resulted in a sequence of valid anagrams. Swapping the order of the first four letters was not to be considered as a distinct game.

Again, your computer was your friend here. Solver Robin Christopher Yu wrote some C++ code that counted up all the paths from each set of four letters (that could be arranged to make a valid word) to each reachable set of nine letters (that could similarly be arranged to make a valid word). In the end, the total number of paths was **4,510,515**. With one new game per day, it would take the actual Anigrams game more than 12,000 years to play every variant. And by then, Iâm sure there would be a whole bunch of new words added to Peterâs word list!

## Want more puzzles?

Well, arenât you lucky? Thereâs a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. Itâs called âThe Riddler,â and itâs in stores now!

## Want to submit a riddle?

Email Zach Wissner-Gross at riddlercolumn@gmail.com.