The Seventh Battle For Riddler Nation
Illustration by Guillaume Kurkdjian
Welcome to The Riddler. Most weeks, I offer up two problems related to the things we hold dear around here: math, logic and probability.
But this week is special. The time has flown, and somehow it’s been three years since I (peacefully) took over this column from my predecessor, Oliver Roeder.
It is only fitting that we continue one of Ollie’s (and my) favorite traditions here at The Riddler: the Battle for Riddler Nation. In order to have a chance at ÑбâÑб÷âбâбâ¤âбâб⤠winning ÑбâÑб÷âбâбâ¤âбâб⤠and becoming the next ruler, I need to receive your battle plans before 11:59 p.m. Eastern time on Monday. Have a great weekend!
This week’s Riddler
Some readers may be familiar with the first, second, third, fourth, fifth and sixth Battles for Riddler Nation. If you missed out, you may want to consult the thousands of attack distributions from some of these previous contests.
I am pleased to say that this week marks the seventh such competition — but like in previous years, I’m tweaking the rules.
In a distant, war-torn land, there are 10 castles. There are two warlords: you and your archenemy. Each castle has its own strategic value for a would-be conqueror. Specifically, the castles are worth 1, 2, 3, …, 9 and 10 victory points. You and your enemy each have 100 phalanxes of soldiers to distribute, any way you like, to fight at any of the 10 castles. Whoever sends more phalanxes to a given castle conquers that castle and wins its victory points. If you each send the same number of phalanxes, you split the points. You don’t know what distribution of forces your enemy has chosen until the battles begin. Whoever wins the most points wins the war.
Submit a plan distributing your 100 phalanxes among the 10 castles. Once I receive all your battle plans, I’ll adjudicate all the possible one-on-one matchups. In previous years, whoever won the most wars also won the battle royale and was crowned ruler of Riddler Nation. But not this time!
Once all the one-on-one matchups are complete, you will be seeded in a single-elimination tournament to determine the ultimate winner. That means the optimal strategy no longer only preys on weaker strategies but also defeats similarly strong strategies.
Who can steal the crown from ÑбâÑб÷âбâбâ¤âбâб⤠Bill Neagle ÑбâÑб÷âбâбâ¤âбâб⤠of Springfield, Missouri, last year’s winner?
Perhaps you have the cunning and logic to be the next ruler of Riddler Nation!
Solution to last week’s Riddler Express
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Liorel ÑбâÑб÷âбâбâ¤Ðбâ of Grenoble, France, winner of last week’s Riddler Express.
Last week, your fairy godmother appeared and gave you a chance to play a game. In this game, she dealt 10 cards face down. Nine of the cards were winners, and one card was a loser. If you picked a winning card, you got a prize. You could then either take your prize and walk away or play again for the chance to win a second prize. But if you lost on that second play, you walked away with nothing and the game was over. Each time you succeeded, she invited you to play again under the same conditions (win yet another prize or lose everything).
What strategy maximized the average number of prizes you expected to win? And what was that average?
First off, several readers noted the slight ambiguity in the problem. Each successive time you played, was the previous winning card removed from the deck or was it instead shuffled back in? In my view, both interpretations were valid, and so I wound up accepting two solutions.
Let’s start with the case in which winning cards were removed. Suppose you had already won w times, meaning there were now 10−w cards remaining in the deck, one of which was the losing card. If you played another round, you stood to win one more prize with probability (10−w−1)/(10−w). But if you picked that losing card, you lost all w prizes you had already won with probability 1/(10−w).
Now, it made sense to play whenever your expected winnings exceeded your expected losses, i.e., when 1·(10−w−1)/(10−w) was greater than w·1/(10−w). Multiplying both sides by their common denominator resulted in the inequality 10−w−1 > w, which simplified to w you played until you lost or won five prizes, at which point you walked away.
And how many prizes could you have expected to win with this optimal strategy? You walked away with prizes if you made it to the fifth round, which occurred with probability (9/10)·(8/9)·(7/8)·(6/7)·(5/6), which simplified to 1/2. On that fifth round, you walked away with five prizes, so your expected winnings were (1/2)·5, or 2.5 prizes.
As for the case in which winning cards were not removed, your probability of winning each round was always 9/10. So if you had already won w prizes, it made sense to play if 9/10 was greater than w/10. In this case, you could have played until you won nine or 10 prizes — both resulted in the same expected value. The probability of winning nine rounds was (9/10)9, and then you won nine prizes, which meant your expected winnings were 910/109, or about 3.487 prizes.
For extra credit, your fairy godmother had a deck of N cards rather than 10 cards. Again, N−1 were winning cards and one was a losing card. Now what was your strategy, and how many prizes did you expect to win on average?
If you drew cards with replacement, then your best bet was to always draw either N−1 or N cards for an expectation of (N−1)N/N(N−1) prizes. But if you drew without replacement, then the answer depended on the parity of N (i.e., whether N was even or odd). If N was even, as with the case when N was 10, your best bet was to draw N/2 cards for an expectation of N/4 prizes. Finally, if N was odd, then you could draw either (N−1)/2 or (N+1)/2 cards for an expectation of N/4−1/N prizes.
In any case, I’d appreciate a fairy godmother who doled out prizes without restrictions. Losing cards, carriages transforming back into pumpkins at midnight — what gives?
Solution to last week’s Riddler Classic
Congratulations to ÑбâÑб÷âбâбâ¤Ðбâ Steve Schaefer ÑбâÑб÷âбâбâ¤Ðбâ of Carlsbad, California, winner of last week’s Riddler Classic.
Last week, you took a second look at a riddle from several years ago about cars getting caught in traffic jams. In the original puzzle, there were N cars on a long, straight highway with a single lane. Each car traveled in the same direction but at a constant speed that was unique and randomly selected. However, if a driver caught up to another, slower car (or a group of cars similarly blocked by that slower car), they remained stuck behind that slower car.
This time around, a second lane had opened up. The catch was that there was only one entry point into this second lane, so each car had exactly one opportunity to decide whether to proceed into this second lane.
From the first car in the original lane to the last car, each decided whether to make the switch to the second lane as it passed. Fortunately, each car knew the speed of every other car, so each made the switch provided that it could ultimately proceed at a greater speed (whether on its own or as part of a faster group).
On average, how many total groups of cars eventually formed in the two lanes?
As is often a good idea around here, let’s start with a small value of N and see what happens. When N was 1, there was one group of cars — not too interesting. When N was 2, there were always two groups of cars, because if the faster car started in the back it would move to the second lane and proceed unimpeded.
But things got trickier when N was 3. Among the six possible orderings of their relative speeds along the road, five resulted in all three cars being their own group. But when the slowest car was first on the road and the fastest car was last, the middle car wound up impeding the fastest car in the second lane. So when N was 3, the average number of groups was 17/6, slightly less than 3.
To find a general solution, solver Sanandan Swaminathan first reviewed the one-lane version of this puzzle. When there were N cars, the last car on the road only formed its own group when it was the slowest car, which occurred with probability 1/N. That meant the expected number of groups with N cars, E(N), was equal to E(N−1) + 1/N.
Now, with two lanes, Sanandan again examined the probability of the last car on the road forming its own group. When the last car was the slowest, again with probability 1/N, it was guaranteed to form its own group. When the last car was the second-slowest, it was impeded by the slowest car (which never switched lanes), so it switched and became the slowest car in the second lane — again guaranteeing that it formed its own group. When the last car was the third-slowest, it again switched to the second lane. But it only formed its own group if the second-slowest car didn’t switch lanes, which happened half of the times in which the second-slowest car started ahead of the slowest car.
You may see where this is headed, but let’s look at one more example — when the last car was the fourth-slowest. Again, it switched lanes, and found itself in its own group when the third-slowest car started ahead of the second-slowest car, which in turn started ahead of the slowest car — something that happened 1/6 of the time.
While the recursive formula was relatively concise for the one-lane puzzle, the second lane certainly muddied the waters. This time around, E(N) = E(N−1) + 1/(0!·N) + 1/(1!·N) + 1/(2!·N) + 1/(3!·N) + … 1/((N−1)!·N). We can double check this formula for when there were three cars. We already said E(2) was 2, so then E(3) was 2 + 1/3 + 1/3 + 1/6, or 17/6 — the same value we arrived at before! This further meant that E(4) was 17/6 + 1/4 + 1/4 + 1/8 + 1/24, or 7/2.
Several solvers went a step further by attempting to find closed-form approximations or even exact expressions for E(N). One notable approximation involved factoring out the 1/N from the previous expression, which gave you E(N) = E(N−1) + 1/N · (1/0! + 1/1! + 1/2! + 1/3! + … + 1/(N−1)!). The sum inside the parentheses famously converges to e as N gets very large. That meant there were roughly e times as many groups of cars with two lanes as there were with one lane. Readers Josh Silverman and Jim Crimmins each demonstrated this fact empirically:
If you were one of those readers who thought that e (and not just the harmonic series) should have shown up in the original puzzle many years ago, I am glad the second lane finally proved your intuition right.
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.
