Can You Construct The Optimal Tournament?

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,¹ 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 Tyler Barron, where in the square?:

You are given an empty 4-by-4 square and one marker. You can color in the individual squares or leave them untouched. After you color as many or as few squares as you’d like, I will secretly cut out a 2-by-2 piece of it and then show it to you without rotating it. You then have to tell me where it was (e.g., “top middle” or “bottom right,” etc.) in the original 4-by-4 square.

Can you design a square for which you’ll always know where the piece came from?

Submit your answer

Riddler Classic

From Erich Friedman, conscientious competition construction:

Imagine a competition in which players are ordered in ability, but we do not know what that order is. Assume the better player will win two-thirds of the time in any one game, independent of any other games. We want to construct a tournament to maximize the probability that the best player wins.

For example, if there are four players and three games, the best tournament is the standard simple elimination tournament: A vs. B, C vs. D, and the winners play for the championship. The best player wins this \((2/3)^2\) = 4/9 = 44.4 percent of the time. Not as good, say, is a lopsided tournament: A vs. B, winner plays C, and winner plays D for the championship. The best player wins this just \((2/4)(2/3)^3 + (1/4)(2/3)^2 + (1/4)(2/3)\) = 23/54 = 42.6 percent of the time.

Your challenge: Construct the optimal tournaments for four players and four games, and for five players and five games.

Extra credit: How often does the best player win the optimal tournaments for N players and M games?

Submit your answer

Solution to last week’s Riddler Express

Congratulations to рџ‘Џ Lucas Gredell рџ‘Џ of St. Louis, winner of last week’s Riddler Express and ROFL Coach of the Year!

Last week, every Riddler reader became the coach of a team in the Riddler Official Football League, or ROFL. Each coach prepared his or her team to take and defend a penalty kick. The goal was divided into two rows (upper and lower) and three columns (left, center and right). A shooter could aim at any one of these six areas, and a goalie could choose to defend any one of the six. If a goalie chose the same area as the shooter, the shot was blocked. If the goalie did not choose the same area as the shooter, the shot had a chance of scoring, per the probabilities shown below.

Knowing that, each coach then submitted a selection for his or her shooter and his or her goalie. I matched each coach’s plan against every other coach’s — there were over 1,520 teams in the league and millions of randomly generated penalty kicks — and adjudicated all the shootouts. Overall, a goal was scored on about two-thirds of the shots. The coach with the most net goals at the end of all that won.

And that coach was Lucas Gredell, who scored 1,218 goals and gave up 902 for a total of 316 net goals. Here were the league’s Top Five performers, a leaderboard dominated by coaches from the soccer powerhouse that is the American Midwest:

All of the top performers had their shooter aim at the upper middle and their goalie defend the lower middle. But because the outcomes of many shots were random, there is a good deal of luck baked into the results, just as there is a good deal of luck baked into life itself.

Our winner explained his decision: “I chose to defend lower middle because it represents the largest risk — any shots attempted at that area will score. Eliminating that certainty means that all other shots have at least some probability of missing. I chose to shoot at upper middle because it is one of the 90 percent regions. I believe it likely that many will mirror my strategy of defending lower middle, so I wanted to maximize my shot probability against that strategy. Even for those who decided to defend a 90 percent region instead, there is only a 1/2 chance that they’ll select my shooting zone.”

Indeed, shooters overall heavily favored the upper and lower middle areas, where there were 90 and 100 percent chances of scoring, respectively, if those zones were left unguarded.

And goalies very heavily favored the lower middle area — where an unguarded shot was sure to score. Fully half of all keepers defended it.

And our winner’s 90-percent gambit clearly paid off: If a goalie did defend a 90-percent region, it was far more likely, for whatever reason, to be lower right rather than upper middle, despite their tactical identicality. Upper middle, therefore, became the juicy scoring spot. Lower middle, while very well defended and not juicy in the least, remained a popular choice among shooters given its scoring guarantee if the goalie doesn’t stay there.

We can also analyze this game through the lens of game theory, which is made easy with an online calculator. The Nash equilibrium of this game is in mixed strategies — that is, players randomize over their location choices with certain specific weights. The equilibrium of this game has the shooter placing the most weight on the riskiest upper left area (which ROFL did not do) and the goalie placing the most weight on the surest lower middle area (which ROFL did do). In equilibrium, the goalie also mixes equally between the two 90-percent zones (which definitely did not happen in ROFL). In equilibrium, a goal is scored about 70 percent of the time (somewhat more than in ROFL).

This column’s motto bears repeating … Riddler Nation: Out of equilibrium since 2015.

Solution to last week’s Riddler Classic

Congratulations to рџ‘Џ Christopher Clark рџ‘Џ of Boston, winner of last week’s Riddler Classic!

Last week’s Classic continued the sports theme, taking us in this case to the basketball court for a friendly game of HORSE. The two competitors, Alice and Bob, were equally good shots and both were perfectly aware of their abilities — they could select a particular shot that they knew they would make 90 percent of the time, for example, or 2 percent, or 50 percent, or whatever difficulty they chose. Alice and Bob were also both sharp strategists who selected their shots optimally in an effort to win the game. Your challenge: If Alice went first, what type of shot should she take to begin the game?

Alice should take the surest shot she can, perhaps one with a 99 percent chance of going in. (Bob, if and when it becomes his turn, should do the same.)

Intuitively, the only advantage Alice has in this game is that she goes first. It’s a bit like having the serve in volleyball — only you can score. Anything less than Alice’s surest shot cedes some of this advantage to Bob. The game may go on a very, very long time, but assuming she doesn’t have to go home any time soon, Alice does well to nurse this first-shooter advantage.

Mathematically: Let’s say Alice’s chosen shot has an \(X\) chance of going in. She has a \((1-X)\) chance of losing her “serve,” an \(X(1-X)\) chance of giving Bob a letter and an \(X^2\) chance of returning to the initial state of the game. The only thing that matters here, as solver Guy Moore explained, is the ratio of the first two outcomes. That is maximized by making \(X\) as close to 1 as possible.

Solver Laurent Lessard plotted the chances that Alice would eventually win the game depending on the surest shot available to her. As that surest shot approaches 100 percent, Alice’s chances of winning reach nearly 55 percent.

Speaking of “eventually,” let’s say that indeed the surest shot available to Alice is a 99-percenter. In that case, the game would take some 700 shots on average. If we assume the players are pretty quick and each shot takes 10 seconds, we’re looking at a two-hour game of HORSE. Let’s hope it’s not too close to dinner.

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 me at oliver.roeder@fivethirtyeight.com.