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 or send me an email.

Due to the holidays, the next column will appear on Jan. 6. See you in 2023!

Riddler Express

From Dean Ballard comes a puzzle to help us ring in the new year, 2023:

The Fibonacci sequence begins with the numbers 1 and 1,² with each new term in the sequence equal to the sum of the preceding two. The first few numbers of the Fibonacci sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on.

One can also make variations of the Fibonacci sequence by starting with a different pair of numbers. For example, the sequence that starts with 1 and 3 is 1, 3, 4, 7, 11, 18, 29, 47, 76 and so on. Generalizing further, a “tribonacci” sequence starts with three whole numbers, with each new term equal to the sum of the preceding three.

Many tribonacci sequences include the number 2023. For example, if you start with 23, 1000 and 1000, then the very next term will be 2023. Your challenge is to find starting whole numbers a, b and c so that 2023 is somewhere in their tribonacci sequence, a ≤ b ≤ c, and the sum a + b + c is as small as possible.

Submit your answer

Riddler Classic

From Gary Yane comes a a puzzle that’s just in time for Christmas:

Every Christmas, Gary’s family has a gift exchange. And every year, there is a big fight over how much folks should spend on the gifts. This year, they decided to pair up. So if Virginia gives Justin a gift, then Justin gives Virginia a gift. This way, while there will still be arguments, only two people will be involved in each argument.

There are 20 people in the gift exchange. In the first round, everyone writes down the name of a random person (other than themselves) and the names go in a hat. Then if two people randomly pick each other’s names out of that hat, they will exchange gifts, and they no longer participate in the drawing. The remaining family members go on to round two. Again, they write down the name of anyone left, and again, any two people who pick each other exchange gifts.  

This continues until everyone is paired up. And yes, if exactly two people remain, they still go through the process of selecting each other, even though they know who their partner will be.

On average, what is the expected number of rounds until everyone is paired up?

Submit your answer

Solution to last week’s Riddler Express

Congratulations to 👏 Nick Imholte 👏 of Charlotte, North Carolina, winner of last week’s Riddler Express.

World Cup group play consists of eight groups, each with four teams. The four teams in a group all play each other once (for a total of six matches), earning three points for a win, one point for a draw and zero points for a loss.

Last week, after group play in a particular group, all four teams had different numbers of points. The first-place team had A points, the second-place team B points, the third place team C points and the last-place team D points. Your task was to find all possible quadruples (A, B, C, D).

Several solvers brute-forced their way through this puzzle. With six matches, each resulting in one of three outcomes (one team wins, the other team wins or it’s a draw), there were a total of 3⁶, or 729, cases to consider. That wasn’t an unreasonable number of cases for those with computer assistance.

But for those who solved this by hand, I salute you!

One way to get started was to look for possible values of A. The best a team could have done was win all three matches, earning 9 points. But what was the minimum value of A? If A had been 4 — meaning the first-place team had a win, a draw and a loss — then there was no way for the four teams to have unique point totals and for the collective number of wins to equal the collective number of losses. That meant A had to be 5, 6, 7, 8 or 9.

Reader Kathy Estevez simultaneously narrowed down the possible values of A+B+C+D. If all the matches had been draws, this sum would have been 12; if none of them had been draws, the sum was 18. In other words, it had to be somewhere between 12 and 18. If it had been 12, then all four teams would have had 3 points each. If it had been 13, then (A, B, C, D) had to be (5, 3, 3, 2). That meant the sum had to be between 14 and 18.

All this forethought helped reduce the number of cases. For example, if A had been 5, then the only way for A+B+C+D to be at least 14 was if (A, B, C, D) was (5, 4, 3, 2). In the end, there were 13 possible quadruples:

• (5, 4, 3, 2)
• (6, 5, 4, 1)
• (7, 4, 3, 1)
• (7, 4, 3, 2)
• (7, 5, 2, 1)
• (7, 5, 3, 1)
• (7, 5, 4, 0)
• (7, 6, 2, 1)
• (7, 6, 3, 1)
• (7, 6, 4, 0)
• (9, 4, 2, 1)
• (9, 4, 3, 1)
• (9, 6, 3, 0)

In this year’s World Cup, three of these unique scores occurred. Group A resulted in the quadruple (7, 6, 4, 0), Group B resulted in (7, 5, 3, 1) and Group F resulted in (7, 5, 4, 0).

Solution to last week’s Riddler Classic

Congratulations to 👏 Michael M. Amati 👏 of Geneseo, New York, winner of last week’s Riddler Classic.

Last week’s Riddler Football Playoff (RFP) consisted of four teams. Each team was assigned a random real number between 0 and 1, representing the “quality” of the team. If team A had quality a and team B had quality b, then the probability that team A defeated team B in a game was a/(a+b).³

In the semifinal games of the playoff, the team with the highest quality (the “1 seed”) played the team with the lowest quality (the “4 seed”), while the other two teams played each other as well. The two teams that won their respective semifinal games then played each other in the final.

On average, what was the quality of the RFP champion?

Before tackling (see what I did there?) the semifinal games, let’s look at what would have happened if two teams faced off. The values of a and b could have been anywhere from 0 to 1. Team A won with a probability of a/(a+b), in which case the quality of the winner was a. Meanwhile, team B won with a probability of b/(a+b), in which case the quality of the winner was b. That meant the average quality of the winner was a²/(a+b) + b²/(a+b), or (a²+b²)/(a+b). Integrating this expression over a and b gave you (4·ln(2)−1)/3 — not the prettiest expression! — or about 59.1 percent.

Well, if you thought the two-team case was complicated, the four-team playoff was a lot more so. And on top of that was another wrinkle: The teams were ranked and seeded for their semifinals.

Many solvers, like David Ding, simulated thousands or even millions of playoffs to find the expected value. After 10 million simulations, David found the average quality of the winning team was approximately 0.674.

As with the case of two teams, you could use integration to find an expression for the four-team case as well. Suppose the four teams by order of seed were A, B, C and D, with respective qualities a, b, c and d. The probability that team A was the champion was a/(a+d) · [a/(a+b) · b/(b+c) + a/(a+c) · c/(b+c)]. In other words, team A had to defeat team D and then go on to defeat whichever team won the other semifinal (B or C). After finding similar probabilities for teams B, C and D, to find the expected value of the winner you had to multiply each probability by each team’s respective quality, then add these values up.

But you weren’t done yet! You still had to integrate over all possible quadrupes (a, b, c, d) with the restriction a > b > c > d. One way to do this was to integrate over a from 0 to 1, b from 0 to a, c from 0 to b and d from 0 to c. Alternatively, you could have integrated over d from 0 to 1, c from d to 1, b from c to 1 and a from b to 1. Either way, this region of integration was a four-dimensional tetrahedron with a volume⁴ of 1/24. To find the average quality of the winner, you had to divide your quadruple integral by 1/24.

This integral was rather nasty, to put it mildly. Nevertheless, several solvers, including Izumihara Ryoma, Benjamin Phillabaum and Laurent Lessard, evaluated the integral, finding the champion’s average quality was 2/5 · (23 − (29+2𝜋²)ln(2) + 39ln²(2) − 8ln³(2) − 3𝜻(3)), or about 0.67354. Here, 𝜻 is the Riemann zeta function, which, to my knowledge, has never before appeared in this column. Solver Ryan McShane plotted the probability distribution for the winning team, which had a nice little skew:

Given the complexity of the double integral in the two-team scenario, and the jump in complexity of the quadruple integral in the four-team scenario, I dare not ask about an octuple integral in the eight-team scenario.

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.