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
It’s time for another interactive Riddler, this one suggested by Abijith Krishnan:
Submit a positive integer. Whoever submits the number closest to the median of all the submitted numbers wins! (For some context, a related earlier Riddler Express generated about 2,500 submissions.)
Riddler Classic
From Todd Garon, a puzzle born of boredom:
While killing some time at your desk one afternoon, you fire up a new game of Solitaire (also called Klondike, and specifically the version where you deal out three cards from the deck at a time). But your boredom quickly turns to rage because your game is unplayable — you can flip through your deck, but you never have any legal moves! What are the odds?
Solution to last week’s Riddler Express
Congratulations to 👏 Leonid Kruglyak 👏 of Los Angeles, winner of last week’s Riddler Express!
In the group stage of the men’s World Cup this summer, each group of four teams will play a round robin, with every team playing each other team once. A win is worth 3 points, a draw 1 point and a loss 0 points. The points are tallied, and the top two teams in each group advance to the knockout stage. For a given group, how many different final standings, including point totals, are possible in this stage?
There are 556.
Each game in this stage can either be a win for Team A, a win for Team B or a draw. And to complete the round robin, six total games are played. Therefore, we might suspect that there are \(3^6=729\) possible final standings. However, this total includes some duplicate final standings, meaning the correct answer is lower. For example, as solver Kyle Hird explained, if Russia beat Saudi Arabia, Saudi Arabia beat Egypt and Egypt beat Russia, then the results would be the same as if Saudi Arabia beat Russia, Egypt beat Saudi Arabia and Russia beat Egypt, assuming their results against Uruguay were unchanged.
So let’s start with 729 and subtract off the duplicates. There are two pieces of vocab to know: a construction, which is the outcome of the various games the teams play, and a permutation, which is the number of ways to distribute a set of points among the four teams.
A couple of examples: There are six group stage outcomes that would construct standings in which the final point totals are {4, 4, 4, 4}, and there is only one way those point totals can be permuted across the four teams. We need only one of those, so we can eliminate five duplicates. There are four ways to construct standings in which the final point totals are {6, 6, 3, 3}, and there are six ways those point totals could be permuted across the four teams. We need to keep one of those constructions, so we can eliminate 18 duplicates. And so on. In general, we can remove the number of constructions minus one (which we keep) times the number of permutations.
Here’s the full list:
- 6 ways to construct {4, 4, 4, 4}; 1 unique permutation; eliminate 5 duplicates
- 4 ways to construct {6, 6, 3, 3}; 6 permutations; eliminate 18
- 3 ways to construct {7, 4, 4, 1}; 12 permutations; eliminate 24
- 3 ways to construct {6, 4, 4, 3}; 12 permutations; eliminate 24
- 2 ways to construct {7, 4, 3, 3}; 12 permutations; eliminate 12
- 2 ways to construct {7, 4, 2, 2}; 12 permutations; eliminate 12
- 2 ways to construct {6, 6, 4, 1}; 12 permutations; eliminate 12
- 2 ways to construct {6, 4, 4, 2}; 12 permutations; eliminate 12
- 2 ways to construct {5, 5, 4, 1}; 12 permutations; eliminate 12
- 2 ways to construct {5, 4, 4, 3}; 12 permutations; eliminate 12
- 2 ways to construct {5, 4, 4, 2}; 12 permutations; eliminate 12
- 2 ways to construct {5, 5, 2, 2}; 6 permutations; eliminate 6
- 2 ways to construct {9, 3, 3, 3}; 4 permutations; eliminate 4
- 2 ways to construct {6, 6, 6, 0}; 4 permutations; eliminate 4
- 2 ways to construct {4, 4, 4, 3}; 4 permutations; eliminate 4
That’s a total of 173 duplicate standings we can eliminate. 729 – 173 = 556, our answer.
Solution to last week’s Riddler Classic
Congratulations to 👏 Andy Mills 👏 of Iowa City, Iowa, winner of last week’s Riddler Classic!
Imagine taking a number and moving its last digit to the front. For example, 1,234 would become 4,123. What is the smallest positive integer such that when you do this, the result is exactly double the original number?
It is 105,263,157,894,736,842. Not really that “small,” after all!
I offered bonus points for eschewing computers while solving this problem, but without some seriously efficient code or a super-fast machine, a computer would take a very long time to find such a big number. So here’s a tidy pencil-and-paper proof from this puzzle’s submitter, Joseph Converse:
Let the last digit of our mystery number be \(a\), and the rest of it be \(b\). So the number we’re searching for equals \(10b + a\). Let \(b\) be an \(n\)-digit number. Then, moving the last digit to the front gives a new number equal to \(10^n \cdot a + b = 2(10b+a)\).
Simplifying that gives \((10^n – 2)a = 19b\). For \(a\) and \(b\) to be integers, we need the left-hand side to be divisible by 19, like the right-hand side is. In other words, we need it to be the case that \(10^n = 2\mod 19\). The smallest \(n\) for which this is true is \(n=17\). So we have \([(10^{17} – 2)/19] \cdot a = 5,263,157,894,736,842 \cdot a = b\).
To find the smallest possible answer, let’s try plugging in \(a=1\). This gives \(b=\) 5,263,157,894,736,842, making our potential solution number 52,631,578,947,368,421. But if we double this we get 105,263,157,894,736,842, which doesn’t quite work. So let’s try plugging in \(a=2\), in which case we get \(b=\) 10,526,315,789,473,684, making our number 105,263,157,894,736,842, which indeed doubles to be 210,526,315,789,473,684 — and so we’re done!
Solver Hector Pefo described a somewhat different proof, and Laurent Lessard wrote up his approach, which is similar to the one above. And finally, Tom Collier illustrated an appealing way that our solution and some other, even larger solutions line up:
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.