Can You Navigate The One-Way Streets?

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,¹ 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.

Riddler Express

You have two 16-ounce cups — cup A and cup B. Both cups initially have 8 ounces of water in them.

You take half of the water in cup A and pour it into cup B. Then, you take half of the water in cup B and pour it back into cup A. You do this again. And again. And again. And then many, many, many more times — always pouring half the contents of A into B, and then half of B back into A.

When you finally pause for a breather, what fraction of the total water is in cup A?

Extra credit: Now suppose both cups initially have somewhere between 0 and 8 ounces of water in them. You don’t know the precise amount in each cup, but you know that both cups are not empty. Again, you pour half the water from cup A into cup B, and then half from cup B back to A. You do this many, many times. When you again finally pause for a breather, what fraction of the total water is in cup A?

The solution to this Riddler Express can be found in the following column.

Riddler Classic

From Graydon Snider comes a one-way trip to a tangle of grids:

In Riddler City, all the streets are currently two-way streets. But in an effort to make the metropolis friendlier for pedestrians and cyclists, the mayor has decreed that all streets should be one-way. Meanwhile, the civil engineer overseeing this transition is not particularly invested in the project and will be randomly assigning every block of each street a random direction.

For your daily commute to work, you drive a car two blocks east and two blocks south, as shown in the diagram below. What is the probability that, after each block is randomly assigned a one-way direction, there will still be a way for you to commute to work while staying within this two-by-two block region (i.e., sticking to the 12 streets you see in the diagram)? Here is one such arrangement of one-way streets that lets you commute to work:

And no, you can’t get out of your car to hop on a bike or walk. I mean, you can, but not in this puzzle.

The solution to this Riddler Classic can be found in the following column.

Solution to last week’s Riddler Express

Congratulations to рџ‘ЏAndrew Ford рџ‘Џ of Madison, Wisconsin, winner of last week’s Riddler Express.

Last week, you and 2021 Regeneron Science Talent Search winner Wenjun Hou were playing a game in which you alternated taking turns, removing pennies from a pile. On your turn, you could remove either one or two pennies from the pile. On Wenjun’s turn, he could remove either two or three pennies. Whoever took the last penny lost. (If there was only one penny left and it was Wenjun’s turn, then he skipped his turn, which meant you would lose). Suppose both you and Wenjun played optimally.

1) If you went first, then what initial numbers of pennies meant you would win the game?

2) If Wenjun went first, then what initial numbers of pennies meant he would win the game?

Let’s call the initial number of pennies in the game N. An efficient way to solve these problems simultaneously was to look at smaller values of N and then work your way toward larger values. For starters, when N = 1, you lost, since you were the only one who could take a penny. Next, when N = 2 and it was your turn, you lost again — you could either take one penny, resulting in N = 1 and a loss for you, or take two pennies, meaning you took the last penny and therefore lost. But when N = 2 and it was Wenjun’s turn, he had to take both pennies, meaning you won.

From there, it was on to N = 3, again considering the separate cases of whose turn it was. If it was your turn, you could take one penny, so that N = 2 and it was now Wenjun’s turn. As we just said, this meant you would win! If it was Wenjun’s turn with N = 3, he could take two pennies, leaving you with N = 1 and a loss.

At this point, solvers like Betts Slingluff got a sense of a broader strategy. If it was your turn, then for any given value of N, then you could remove one coin (in which case it would then be Wenjun’s turn with N−1 coins) or two coins (in which case it would then be Wenjun’s turn with N−2 coins). You could look to see if either option resulted in a victory for you, and that would dictate whether you took one or two. Meanwhile, Wenjun would operate under a similar strategy, looking at what would happen when it was your turn with either N−2 or N−3 coins. And should either of you deviate from your optimal strategy, the other would seize the upper hand.

The following table illustrates these strategies. On your turn, look one or two rows up in Wenjun’s column to see if you can win. Wenjun will look up two or three rows in your column to see if he can win.

Most solvers saw the resulting pattern:

• When you went first, you would win if N was a multiple of 4 or a multiple of 4 plus 3, also known as 0 or 3 (mod 4).
• When Wenjun went first, he would win if N was a multiple of 4, a multiple of 4 plus 1 or a multiple of 4 plus 3, also known as 0, 1 or 3 (mod 4).

For a more rigorous explanation of these results, check out write-ups by solvers Eli Wolfhagen and Rohan Lewis.

And while the column didn’t ask for this, another quirky outcome of this game was that if you randomly selected a number of coins and who went first, you had a 37.5 percent chance of winning, versus Wenjun’s 62.5 percent chance. Wenjun’s edge of being allowed to pass when there was just one coin turned out to be quite the advantage.

Solution to last week’s Riddler Classic

Congratulations to рџ‘ЏBrian Auriti рџ‘Џ of Morrisville, North Carolina, winner of last week’s Riddler Classic, which came from Timothy Qian, another winner of this year’s Science Talent Search. 

Last week, you were asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic you knew absolutely nothing about. Before the first question was asked, you had exactly $1. For each question, you could bet any non-negative amount of money that you would answer correctly. That is, you could bet any real number (including fractions of pennies) between zero and the current amount of money you had. After each of your answers, the Sphinx revealed the correct answer. If you were right, you gained the amount of money you had bet; if you were wrong, you lost the money you had bet.

However, there was a catch. (Isn’t there always, with the Sphinx?) The answer would never be the same for three questions in a row.

With this information in hand, what was the maximum amount of money you could be sure that you would win, no matter what the answers wound up being?

At first, it might have seemed implausible that you could guarantee any winnings from the Sphinx, given the capricious nature of its answers. But sure enough, it was possible to leverage the Sphinx’s constraint to your advantage.

There were a total of 10 answer combinations to the four questions that had no three-peats: TTFT, TTFF, TFTT, TFTF, TFFT, FTTF, FTFT, FTFF, FFTT and FFTF. You had no information about what the Sphinx would answer for the first question, so you bet nothing. For the second question, six of the 10 cases had a second answer that was different from the first, so suppose you bet x that it would be different.

At this point, you were down to 1−x dollars for the cases TTFT, TTFF, FFTT and FFTF. But for all four of these, you knew that the third answer had to differ from the first two, which meant you could double your money. That left you with 2−2x dollars going into the fourth question. With no leverage on the information here, you sat right with 2−2x dollars in the end.

Alternatively, you were up to 1+x dollars for the cases TFTT, TFTF, TFFT, FTTF, FTFT and FTFF. Notice that two-thirds of the time, the third answer differed from the second. While it wasn’t a sure thing, it was worth betting on. Suppose, in this case, you bet y dollars that the third answer would differ from the second. If you were right, then you had 1+x+y dollars in the end, since you couldn’t make guaranteed money on the last question. If you were wrong, then you had 1+x−y dollars, which you could double up on the last question, lest the Sphinx give the same answer three times in a row.

Putting this all together, depending on the Sphinx’s answers, you could win 2−2x dollars, 1+x+y dollars or 2+2x−2y dollars. From here, you were free to choose any value of x between 0 and 1 and any value of y between 0 and 1+x. Due to the tradeoffs among these three possible winnings, your guaranteed winnings were maximized when all three of these values were equal. The expressions 2−2x, 1+x+y and 2+2x−2y all equaled 8/5 when x was 1/5 and y was 2/5.

That meant with four questions, such that three in a row never had the same answer, you were guaranteed winnings of 8/5 dollars, or $1.60. (Note: You invested $1 to win $1.60, so I also accepted answers of $0.60, which represented your profit from this game.)

For extra credit, you generalized the game so that the Sphinx asked N questions, such that the answer was never the same for Q questions in a row. What were your maximum guaranteed winnings in terms of N and Q?

This general version of the problem had a surprising relationship to Fibonacci numbers. As solvers Laurent Lessard showed, your maximum guaranteed winnings were 2^N−1 divided by the N+1 term in the sequence of Fibonacci (Q−1)-step numbers. The following graph, courtesy of Laurent, shows your guaranteed winnings as a function of N and Q:

Take that, Sphinx!

Want more riddles?

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.