Can You Drink More Coffee Than Your Co-workers?

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-sized and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,¹ and you may get a shoutout in next week’s column. If you need a hint, or if you have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express

From Colm Kelleher, a small but tricky number square problem:

There is a very specific logic underlying the grid of numbers above, and X is somewhere between 1 and 14. What, specifically, is X?

Submit your answer

Riddler Classic

From Dan Waterbury, a participatory collective-action caffeine problem:

Riddler Headquarters is a buzzing hive of activity. Mathematicians, statisticians and programmers roam the halls at all hours, proving theorems and calculating probabilities. They’re fueled, of course, by caffeine. But the headquarters has just one coffee pot, along with one unbreakable rule: You finish the joe, you make some mo’.

Specifically, the coffee pot holds one gallon of coffee, and workers fill their mugs from it in sequence. Whoever takes the last drop has to make the next pot, no ifs, ands or buts. Every worker in the office is trying to take as much coffee as he or she can while minimizing the probability of having to refill the pot. Also, this pot is both incredibly heavy and completely opaque, so it’s tough to tell how much remains. That means a worker can’t keep pouring until she sees or feels just a drop left. Anyone stuck refilling the pot becomes so frustrated that they throw their cup to the ground in frustration, so they get no coffee that round.

Congratulations! You’ve just been hired to work at Riddler Headquarters. Submit a number between 0 and 1. (It could be 0.9999, or 0.0001, or 0.5, or 0.12345, and so on.) This is the number of gallons of coffee you will attempt to take from the pot each time you go for a cup. If that amount remains, lucky you, you get to drink it. If less remains, you’re out of luck that round; you must refill the pot, and you get no coffee.

Once I’ve received your submissions, I’ll randomize the order in which you and your colleagues head for the pot. Then I’ll run a lot of simulations — thousands of hypothetical trips to the coffee pot in the Riddler offices. Whoever drinks the most coffee is the тШХ Caffeine King or Queen тШХ of Riddler Headquarters!

Submit your amount

Solution to last week’s Riddler Express

Congratulations to ЁЯСП Peter Sloan ЁЯСП of Montreal, winner of the previous Express puzzle!

In a certain family, there have been some funny coincidences. Among an extended family of 23 people, three pairs of people share birthdays. What are the odds of that? Moreover, all these pairs are on one side of the family, a group of only 14 people. What are the odds of that?

They’re roughly 1.8 percent and 0.07 percent, respectively.

To calculate these odds, we need to calculate two separate things. First, we need the total number of different ways that a group’s birthdays could be arranged. Second, we need the total number of different ways that a group’s birthdays could be arranged such that three pairs of them share a specific birthday. Then, because any individual arrangement of birthdays is equally likely, we’ll divide that second number by the first number and voila.

Our winner, Peter, walks us through the rest of the details:

Let’s start with the extended family of 23 people. There are \(365^{23}\) (an enormous number, 85 octodecillion) ways that this family’s birthdays can occur, since each person has a shot at having a birthday on any of the 365 days in a year. (Let’s ignore leap years.) That’s our first piece. Next, we can split the second calculation into three products. Since there are three pairs of shared birth dates, there are 20 unique birth dates in total among the group, which allows us to break things down like this:

1. The number of ways to choose 20 unique birth dates out of 365 multiplied by
2. the number of ways to choose three birth dates out of 20 to be our “pair” birth dates multiplied by
3. the number of ways to assign our 23 people to the chosen birth dates so that two are assigned to each pair birth date and one is assigned to each of the other birth dates.

The first two expressions are given by what’s called the choose function, which gives us the number of ways you can select a set of objects from a larger collection: \({365 \choose 20} \cdot {20 \choose 3}\). The third expression is given by the multinomial distribution as \(\frac{23!}{2!^3 1!^{17}}\), and works out to 23!/8. So the solution is \({365 \choose 20} \cdot {20 \choose 3} \cdot \frac{23!}{8}/365^{23}\), or about 1.832 percent. The odds of getting three pairs in a group of 14 people are, similarly, \({365 \choose 11} \cdot {11 \choose 3} \cdot \frac{14!}{8}/365^{14}\), or about 0.07956 percent. But we must also take into account that on the other side of the family, nine people don’t share any birthdays. The odds of this happening are \({365 \choose 9} \cdot 9!/365^9\), or about 0.905. Thus the total odds are 0.07956*0.905, or about 0.072 percent. Lucky family!

Solution to last week’s Riddler Classic

Congratulations to ЁЯСП Laurent Bartholdi ЁЯСП of Paris, winner of the previous Classic puzzle!

On a sunny summer day, you’ve gone to the park with your friends. You decide to play a game of “chaos tag,” according to the following rules: Any group of two or more people can play. All players are active at the start of the game. Active players can run around and tag other active players. A player who is tagged becomes inactive and must sit on the spot where they were tagged. An inactive player becomes active again when the player who tagged them is tagged. Victory is achieved by being the only remaining active player.

Suppose N of you are at the park that day. If all active players are equally likely to tag someone and any of the possible targets are equally likely to be tagged, how long will the game last on average, as measured in tags?

It will last an average of \(2^{N-1}-1\) tags.

Many of you solvers turned to computer simulation, with you and your digital friends sprinting around at lightning speed inside your CPUs. David Gardner modeled the problem in the numerical computing environment MATLAB, and his simulations gave him the following trend in number of tags:

As the number of players increases, the number of tags the game will take increases very fast — you’ll notice the y-axis of David’s chart is on a logarithmic scale, ranging from 1 tag to 100,000,000 tags.

Zack Segel modeled it in the programming language Python and found the pattern shown in the table at left. One thing quickly becomes clear: The average number of tags for each number of players are all very close to powers of two! That is, they almost, but not quite, match a simple doubling pattern of 1, 2, 4, 8, 16, 32, 64 and so on. From that simple observation, we can posit our general solution for N players: \(2^{N-1}-1\) tags.

But others, of course, took more analytical (and analog) approaches. Here’s Joseph Wetherell’s nifty solution:

Each player \(P\) is responsible for some number \(n(P)\) of currently inactive players. For example, at the start of the game \(n(P) = 0\) for all players and at the end of the game, \(n(Winner) = N-1\). Define the “score” of player P to be \(2^{n(P)}-1\), and define the “total score” of the current game to be the sum of the scores of the players. So the total score at the beginning of the game is 0 and the total score at the end is \(2^{N-1}-1\). Suppose we are in the midst of the game and we consider what is going to happen next. In this scenario, \(P\) and \(Q\) are two active players. If \(P\) tags \(Q\), the change in the score is \(2^{n(P)}-2^{n(Q)}+1\), while if \(Q\) tags \(P\), the change in score is \(2^{n(Q)}-2^{n(P)}+1\). Note that the average of these two values is 1. Since these two options are equally likely, according to the assumptions of the problem, and in fact all options occur in pairs like this, we see that the expected value of the score goes up by 1 each time. It follows that the expected remaining duration of the game starting from any given situation S will be Score(EndState) – Score(S). Thus, the expected length of the game will be Score(EndState) – Score(BeginState) = \(2^{N-1}-1\).

And Sawyer Tabony shared his lovely pen-and-paper work:

This week’s ЁЯПЖ Coolest Riddler Extension Award ЁЯПЖ goes to Tim Black of Madison, Wisconsin. Tim proposed a variant of this game that he calls break-free chaos tag. Another good name might be “even more chaotic tag.” “Each time you are inactive,” he wrote, “you have one chance to flip a fair coin. If it comes up heads, you ‘break free’ and become active again. You win the game when you are the only active player and all other players have used up their coin flips.”

Tim was kind enough to publish his analysis, along with a very clever solution to the original problem, on his blog. Again, there’s a tidy solution to this variant, but I hope you’ve been getting your cardio in: In even more chaotic tag, the game lasts \(3^{N-1}-1\) tags on average.

Want to submit a riddle?

Email me at oliver.roeder@fivethirtyeight.com.