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 Roman Lee and George Yan, a problem in which nature calls:
Some number, N, of people need to pee, and there is some number, M, of urinals in a row in a men’s room. The people always follow a rule for which urinal they select: The first person goes to one on either far 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 far end, the third person in the middle, and so on. They 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?
Riddler Classic
From Brendan Hill, an open-ended, experimental and dare-I-say creative optimization puzzle, on a topic about which I myself have often pondered in my idler moments:
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 variables here. You can type “i’s” at a certain rate, maybe around five per second, by simply pressing its key repeatedly. You can also hold down the key, initially getting a single “i,” and then after a “repeat delay” of about half a second, getting a quickly repeating stream of “i’s” at a “repeat rate” of about 30 per second. You can also use copy and paste. If you release the “i” key, you can hit Ctrl+A then Ctrl+C, then hit the right arrow key, and finally Ctrl+V, selecting all your text, copying it and pasting it to what you had already. (Replace Ctrl with Command if on a Mac, of course.) This process costs you about a second from “i” key release to initial depress of Ctrl+V. If you hold down Ctrl+V, there is the same repeat delay and repeat rate that then generates a bunch of copies of your clipboard very quickly.
So the questions are: How big should you make the original edition of your clipboard before you transition to the more efficient copy/paste? Then, how long should you stick with that clipboard before going back to the Ctrl+A and growing your clipboard again?
(There may be no single right answer here, but Bonus Riddler Points will be awarded for mathematical and empirical insight. Extra Special Bonus Riddler Points — and who knows, maybe a copy of a book — will be awarded for video evidence of the quickest 1 million “i’s” to populate a solver’s text editor.)
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Shawn Cooke ÑÑâÐ of Glen Allen, Virginia, winner of last week’s Riddler Express!
Suppose you have N circles, all of which are joined so that their centers lie on a larger circle. What is the ratio of the diameter of the larger circle to the diameter of the smaller circles?
Think of the centers of the circles as forming an n-gon. We can then draw the following figure, where \(r_1\) is the radius of one of the smaller circles, \(r_2\) is the radius of the larger circle, and \(\theta\) is the angle shown:2
The ratio is \(1/\sin(\pi/n)\).
We can then calculate that \(\theta = (2\pi)/(2n)\) — there are \(2\pi\) radians in a circle and \(2n\) angles like \(\theta\) that make up this bigger circle. We also know that \(\sin \theta = r_1/r_2\) — this is just the definition of sine. Equivalently, to get an answer in terms of the circles’ diameters, as the puzzle asked for, \(\sin \theta = d_1/d_2\), where d is diameter. Finally, combining these mathematical facts, \(d_2/d_1 = 1/\sin(\pi/n)\), our answer!
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Jared Nielsen ÑÑâÐ of Provo, Utah, winner of last week’s Riddler Classic!
Last week, we found ourselves in the situation depicted below, on a gridded system of streets, standing at point A and wanting to meet a mutual friend at point B as quickly as possible. We couldn’t jaywalk, could cross only one street at each intersection and didn’t know anything about the timing of the lights at the other intersections, save for the fact that their cycles were the same length — T. What should we have done?
Despite our northbound “Walk” signal, we probably should’ve waited a second and walked east! Specifically, as long as the length of the signals’ cycles is at least 4 seconds, we do better going east. Pedestrian discretion is the better part of pedestrian valor.
Why? The solution has to do with the trade-off between a second saved and crossing options earned. The details of the rest of the solution are adapted from this puzzle’s submitter, Ben Wiener.
Let’s say, for the sake of comparison, that the two of us split up. You go north immediately while I wait for a second and then go east. Here’s an example of what might happen: At your next intersection, you can only go east, so you have no choice but to wait 3 seconds for the light to change. The intersection after that, you need to go east again. You wait an excruciating five seconds. I, on the other hand, lost one second waiting for the light to change — but I’m not worried. As I arrive at the next intersection, I smile to myself and immediately walk whichever way the light allows — east in this case. At the next intersection, I wait a modest four seconds for the light to allow me to go north. One block later, I arrive first at the intersection, three precious seconds before you do. I high-five our mutual friend. You miss out.
What happened here? The only signal we know about is the one we’re standing at. We know that we can go north immediately, but we have to wait one second to go east, so call that \(\tau_{north}=0\) seconds and \(\tau_{east}=1\) second. We don’t know anything about the other lights, but we can try to figure out some average behavior. First, let’s label the intersections as shown below:
To find the average wait time, let’s plot out the system. Say each walk signal cycle lasts a time T. The x-axis on the plot below is the time you arrive at the light, marked with the moments when the signals change. The y-axis is the resulting wait time to go in each direction. If you know nothing about the state of an intersection and you want to go east, you could get lucky and arrive when the light allows you to go east. But you could also arrive and have to wait T seconds. There is a 1-in-2 chance of catching a walk signal. There is an average wait time of T/2 if you catch a Don’t Walk signal.3 Overall, the average time you expect to wait is \(\langle t \rangle=T/4\).
We can apply this to the intersections in question. At the intersection (1,0), we must go east. We could get lucky and be able to go immediately, but we expect to wait an average of T/4. We’ll denote this \(\langle t_{(1,0)} \rangle=T/4\). The situation at (0,1) is the same: \(\langle t_{(0,1)} \rangle=T/4\). At (2,0), you have to wait the same average time as at (1,0) twice, for a total wait time of \(\langle t_{(2,0)} \rangle=2T/4\) from (2,0) to the finish line.
Things are different at (1,1). Here, you get to make a decision. You can immediately go to either (0,1) or (1,0) — whichever the light allows. Because you get to choose, the intersection at (1,1) is free. That means a total wait time of only \(\langle t_{(1,1)} \rangle=T/4\) from here. That’s the value of having multiple options!
Our problem is almost solved. At (2,1), we know our options now. We can immediately go north to (2,0), where we expect to wait T/2, or we can wait one second and go to (1,1), where we expect to wait T/4. In other words, \(\langle t_{north} \rangle=T/2\) and \(\langle t_{east} \rangle=(T/4) + 1\). As long as T is longer than 4 seconds, you should go east. In general, you should go east unless your initial wait time is big relative to the lights’ cycle, that is \(\tau_{east}>T/4\).
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.