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 Dave Moran and family, a telephonic coincidence:
My daughter recently noticed that the 10 digits of our old landline phone number are the same digits as those in my wife’s cell phone. The first three digits match exactly because we are in the same area code as before. And the last seven digits of my wife’s cell phone are an exact scrambled version of the last seven digits of the old landline. By “exact scramble,” I mean a string of numbers that is different than the original string of numbers but contains all of the same digits with the exact same number of repetitions (so, for example, if “4” appears exactly three times in the landline number, it also appears exactly three times in my wife’s cell number).
My daughter asked, “What are the odds of that?”
To make this concrete, assume that landlines and cell numbers in my area code are assigned randomly, such that a person is equally likely to get any of the 10,000,000 numbers between and including 000-0000 to 999-9999. Given that assumption, what is the probability that the last seven digits of the cell number are an exact scramble of the last seven digits of our landline?
Riddler Classic
From Jesse Senko — Come on down! You’re the new head of the Ministry of Sport:
Today marks the beginning of Riddler Sports League. Sixteen teams, with strengths ranging from 1 to 16, will be taking part. Every team plays every other team once, with the schedule randomly determined at the start of the season. The games’ outcomes are decided probabilistically. Take the strengths of the two competing teams, add them together and add an extra 1. That creates the denominators of three fractions that determine the chances of each outcome: win, loss or draw.
Here’s an example of how it works: If Team A’s strength is 2 and Team B’s strength is 1, then Team A wins 2/4 of the time, loses 1/4 and draws 1/4. Another example: If Team A’s strength is 15 and Team B’s strength is 14, then Team A wins 15/30 of the time, loses 14/30 and draws 1/30.
A win earns 2 points, a loss 0 points, and a draw 1 point for each team. The title winner (or winners) is whoever has the most points at the end of the season.
But — everybody in Riddler Nation is so busy solving puzzles that they don’t have time to play every game of the sports season, so they’ll play only until a title winner is mathematically determined. On opening day, every team plays its first game. Afterward, one specifically chosen game is played each day. Each chosen game must be the next scheduled game for at least one of the participating teams. Your challenge, as head of the Ministry of Sport, is to craft an algorithm that chooses the next game to play such that the median number of games across a thousand simulated seasons is as small as possible. What is that number? What is the theoretical fewest games it would take?
Extra credit: Modify your code to model soccer’s Premier League and determine how many of its games are meaningless. (In that league, there are 20 teams that face each other twice, and a win is worth three points, a tie one point and a loss zero points. Also, the bottom three teams need to be mathematically determined for purposes of relegation.)
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ The Hewitt School’s probability and statistics class ÑÑâÐ in New York City, winners of last week’s Riddler Express!
Last week brought a numerical numismatic challenge. Coin flips are great for determining winners if you want each of two people to have an equal chance of winning. But what if you don’t? Anna and Barry, for example, weren’t interested in equity. All they had was a fair coin marked heads and tails. How could they devise a game that gave Anna a 1 in 3 chance of winning? What about a 1 in 4 chance? What about a 1 in 5 chance?
There are a number of ways to properly arrange these games. Here are a few examples that do the trick:
To achieve a 1 in 3 chance for Anna, have the players alternate flips, with Barry going first. The first person to flip a head wins. In each pair of flips, Barry is twice as likely as Anna to win, because Barry went first. Somebody will win — therefore Anna will win one time in three.
A 1 in 4 chance is pretty easy: Simply have Barry flip the coin twice. If he gets a head either time, he wins. He’ll lose — and Anna will win — if both his flips wind up tails, which happens one time in four.
And, finally, to achieve a 1 in 5 chance for Anna, have the players alternate again. But this time, each gets two flips, so that Barry flips twice, then Anna flips twice, then Barry, and so on. The first to flip a head wins. In every set of four flips, there are 16 possible coin-toss combinations (HH-HH, HT-HH and so on). Out of those, Barry will win 12, Anna will win three, and they’ll move onto another set of flips once. Anna wins one-fourth as often as Barry, so Anna wins one time in five.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Hernando Cortina ÑÑâÐ of New York City, winner of last week’s Riddler Classic!
Last week, you were the elections analyst for Riddler Nation’s data-driven political blog, OneHundred. An annual election was coming up, and all 100 of the Riddler Nation Senate seats were up for grabs.
There are two parties, the Theorists and the Programmers, and elections work differently there. In Riddler Nation, a virtual coin is flipped for each seat — the Programmers win on heads, while the Theorists win on tails. The founders of Riddler Nation allowed for a political party to write the program that does the flipping. The Programmers do the programming of the virtual coin, but the Theorists do have a recourse: They can challenge the results in Riddler Nation Statistical Court if they think something is fishy. The court is made up of honest and learned statisticians. A number of questions about this election followed.
(The answers below hold on average — that is, if there were many instances of Riddler Nations in many parallel universes. In any given nation, anything could happen — the Programmers could cheat, heavily rigging the coin, and still get unlucky and not win any seats, for example.)
First, if the Programmers don’t cheat (i.e., the coin is fair), what is the probability that one party will win a simple majority in the Senate and what is the probability that one party will win a supermajority of 60 seats or more?
The chances of one given party winning a majority are about 46 percent. The chances of one given party winning a supermajority are about 3 percent. We can arrive at these numbers using a binomial distribution. This distribution describes the likelihood of the number of “successes” in some larger number of “trials.” In this case, a “success” is a given party winning a coin flip, and there are 100 seats, or “trials.”
Second, if the Programmers decide to cheat by weighting the virtual coin in their favor, what weighting will give them a 50 percent chance of winning a supermajority? How often can they do this periodic, annual weighting before the Theorists can prove to the Statistical Court that there’s at least a 99 percent chance that the coin wasn’t fair?
The Programmers would need to weight the coin such that it landed heads about 59.5 percent of the time. Again, this comes straight from the binomial distribution — but in this case, the probability of success is unknown. So we set the probability of a supermajority (60 or more “successes”) to 50 percent, and then solve for the weight of the coin (the probability of a “success”). The Programmers can only “get away” with this annual weighting once, however. Anything more and the supermajorities they are likely to win are expected to become too suspicious.
Third, if the Programmers decide to cheat by weighting the coin permanently for the next 100 elections, how heavily can they weight it and escape a successful 99 percent challenge by the Theorists? How many 60-seat supermajorities can they expect to win over this 100-year period?
Over 100 years, there will be 10,000 coin flips. The 99th percentile of this binomial distribution is 5,116, as our winner Hernando Cortina explained in his excellent solution. Therefore, the Programmers can probably safely pump up the heads probability to about 51.16 percent. That will buy them an expected 4.7 or so supermajorities over the next century.
And fourth, what is the optimal cheating strategy for the Programmers to perpetually escape a successful 99 percent statistical challenge and maximize the number of expected supermajorities?
Hernando suggested an “oscillatory” strategy, whereby the Programmers begin by weighting the coin quite heavily in their favor and then dial it back a bit, eventually alternating between slightly weighted and unweighted, in order to avoid “detection” — and resulting banishment — by the court. That would look something like this:
Finally, for those still interested in coin-flip-based elections, I would like to direct you to EightThirtyFive, created by solver Conor C. “We 100% guarantee our results will have a minimum of 50% accuracy for each individual race!” I’m impressed!
Want more riddles?
Well, aren’t you lucky? There’s a whole book full of the best of them and some never seen before, called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.