Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and 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 next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Charlie Drinnan, find the letters’ numbers:
If A, B, C, D and E are all unique digits, what values would work with the following equation?
ABC,CDE × 4 = EDC,CBA
Riddler Classic
From Ricky Jacobson, a classic problem of pirates, monkeys and coconuts:
Seven pirates wash ashore on a deserted island after their ship sinks. In order to survive, they gather as many coconuts as they can find and throw them into a central pile. As the sun sets, they all go to sleep.
One pirate wakes up in the middle of the night. Being the greedy person he is, this pirate decides to take some coconuts from the pile and hide them for himself. As he approaches the pile, though, he notices a monkey watching him. To keep the monkey quiet, the pirate tosses it one coconut from the pile. He then divides the rest of the pile into seven equally sized bunches and hides one of the bunches in the bushes. Finally, he recombines the remaining coconuts into a single pile and goes back to sleep. (Note that individual coconuts are very hard, and therefore indivisible.)
Later that night, a second pirate wakes up with the same idea. She tosses the monkey one coconut from the central pile, divides the pile into seven bunches, hides her bunch, recombines the rest, and goes back to sleep. After that, a third pirate wakes up and does the same thing. Then a fourth. Then a fifth, and so on until all seven pirates have hidden a share of the coconuts.
In the morning, the pirates look at the remaining central pile and notice that it has gotten quite small. They decide to split the pile into seven equal bunches and take one bunch each. (Note: The monkey does not get one this time.)
If there were N coconuts in the pile originally, what is the smallest possible value of N?
Solution to last week’s Riddler Express
Congratulations to 👏 Greg Mokodean 👏 of Washington, D.C., winner of last week’s Riddler Express!
Last week, we went to the men’s room, where some number of people need to pee, and there were some number of urinals in a row. The people always followed a rule for which urinal they select: The first person goes to one on either end of the row, and the rest try to maximize the number of urinals between them and any other person. So the second person will go on the other end, the third person will go to the middle, and so on. People continue to occupy the urinals until one person would have to go directly next to another person, at which point that person decides not to go at all. What’s the minimum number, M, of urinals required to accommodate all the N people at the same time?
This was not exactly a trick question, but it is tricky. The answer is not 2N – 1, as most readers submitted. It does seem like it at first. One person requires one urinal, two people require three urinals, and three people require five urinals. But this pattern soon breaks down. Consider the case of four people and seven urinals. (Let X be an occupied urinal and O an unoccupied one.) The first person goes to the far end: OOOOOOX. The next person goes to the other end: XOOOOOX. The third person goes to the middle, maximizing distance from any other person: XOOXOOX. But now there is no room for the fourth person; each unoccupied urinal is adjacent to someone else. It is true that N people could fit at 2N – 1 urinals and not stand next to anyone else, but not given the way these specific choosy people are behaving. To accommodate four people, we’d need 2N, or eight, urinals: OOOOOOOX, XOOOOOOX, XOOXOOOX, XOOXOXOX.
The pattern only gets stranger. Solver Darren Blum charted the number of urinals required for the first 22 people:
So what is going on in this weird bathroom? In essence, the distance-maximizing behavior of the bathroom users is inefficient. Some numbers of people fill a row of urinals fairly densely. For example, three people pack themselves in as efficiently as possible given their preference to not stand next to anyone. But some numbers of people are especially inefficient and throw everything off. Four people do that, as we saw above, as do six people, as do 10 people, as you can see in Darren’s chart.
To accommodate N people who behave in this fashion, there appears to be a relatively clean but still pretty complex mathematical expression: You’d need \(N+2^{\lceil log_2(N-1) \rceil}\) urinals, as Tom Singer explained further in his solution. This function ranges between the tightest possible packing of people (2N – 1 urinals, or a person every other urinal) and the sparsest (3N – 4 urinals, or a person every third urinal). Tom also continued the pattern shown above, charting the minimum number needed for up to 1,000 people:
The XKCD blog also tackled this problem a few years ago. It provided some advice: “Guys: if you enter a bathroom with an awkward number of vacant urinals in a row, rather than taking one of the end ones, you can take one a third of the way down the line. This will break the awkward row into two optimal rows, turning a worst-case scenario into a best-case one.”
Mathematics is beautiful.
Solution to last week’s Riddler Classic
Congratulations to 👏 Adam Thornton 👏 of Tucson, Arizona, winner of last week’s Riddler Classic!
Last week brought a creative optimization challenge: What is the fastest way to fill up a text editor with a string of 1 million of the same character? (Let’s go with the letter “i.”) There are a lot of considerations here. You could simply type i’s at a certain rate. You could hold down the key, initially getting a single i and then a quickly repeating stream of i’s. You could use copy and paste. You could also do something I hadn’t even thought of. What should you do, when should you do it, and how long will it take?
Let’s start with a baseline. If you just tapped the i key as fast as you could — about five times per second, we estimated last week — it’d take more than two days to arrive at a million characters. If you held down the i key, it’d take a little over 9 hours.
Doug Midkiff did it in about 14.5 seconds. His intuition was to leverage powers of 10, typing 100 i’s, pasting 10 copies of those, and then repeating that process three times.
Joseph Lombardo turned the above typing/timing constraints into a formalized math problem. He found that you should first hold the i key for 1 second, producing 16 i’s. You should then copy those to the clipboard and hold paste for 0.966 seconds, producing 15 copies. Finally, you should copy and paste for 0.96 seconds four more times. The total time is 8.86 seconds. Ben Knox — and many other solvers — came in at around 8 seconds, too, with video evidence to prove it.
And still others went beyond the pedestrian typing and copying and pasting that I proposed. Most of them leveraged the power of either a small computer program or a text editor such as Vim, which has powerful commands that can automate much of the typing. Kevin Labe, for example, achieved a time of 5 seconds using the command “i i Esc v y 999999 p.”
Kyle Pekosh also achieved about 5 seconds by leveraging the programing language Python and the text editor Vim.
And finally our winner, Adam Thornton, along with a few other solvers, pared the problem down to just a handful of keystrokes. In Emacs, another text editor, Thornton explained that solvers can type Control-U, then type 1000000, then type i. Voila. You can find his video here.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.