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,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.
From Jason Zimba comes a sequence of scrambled screens:
Each of the images below is a different nation’s flag in which the pixels have been randomly rearranged. Can you figure out which flag is which?
Important note: Some browsers can distort the colors of the flags. If you’d like to scrutinize these images, consider downloading them first, which you can do by right-clicking each image.
There will be one winner per flag. And if you’re a little rusty on your flags, you can view them all here.
The New York Times recently launched some new word puzzles, one of which is Spelling Bee. In this game, seven letters are arranged in a honeycomb lattice, with one letter in the center. Here’s the lattice from December 24, 2019:
The goal is to identify as many words that meet the following criteria:
- The word must be at least four letters long.
- The word must include the central letter.
- The word cannot include any letter beyond the seven given letters.
Note that letters can be repeated. For example, the words GAME and AMALGAM are both acceptable words. Four-letter words are worth 1 point each, while five-letter words are worth 5 points, six-letter words are worth 6 points, seven-letter words are worth 7 points, etc. Words that use all of the seven letters in the honeycomb are known as “pangrams” and earn 7 bonus points (in addition to the points for the length of the word). So in the above example, MEGAPLEX is worth 15 points.
Which seven-letter honeycomb results in the highest possible game score? To be a valid choice of seven letters, no letter can be repeated, it must not contain the letter S (that would be too easy) and there must be at least one pangram.
Solution to last week’s Riddler Express
Congratulations to 👏 Josiah Jenkins 👏 of Rugby, North Dakota, winner of the most recent Riddler Express.
Last week, your office voted on a theme for its holiday party. It fell on you to record the percent of your coworkers (including yourself) who voted for each one. Since you were in a hurry, you just wrote down everything in the percentage that came before the decimal point. So for example, 35.0 percent, 35.17 percent and 35.92 percent would all be written simply as “35 percent.”
After the votes were tallied, you found that the winner received 73 percent of the vote (at least, that’s what you wrote down), while second place had 58 percent and third place had 32 percent. Apparently, people voted more than once. Based on these percentages, what was the minimum number of people who could work in your office?
Some solvers noted that in order to calculate the percentages in the first place, you must have known how many people worked in the office. That’s a fair point. But it’s the holidays, let’s be generous, people.
So let’s assume someone else told you the percentages; you can use them to figure out how many coworkers you have. One way to do this is to try out lots of different numbers. For example, there couldn’t have been 10 people in your office, since the only possible voting percentages would have been 0 percent, 10 percent, 20 percent, 30 percent, and so on up to 100 percent — 73, 58 and 32 percent would not have been possible. Meanwhile, there could have been 100 people in your office — then 73 people, 58 people and 32 people would have voted for the respective party themes. After this, it was a matter of trial and error to pin down the minimum possible number of people in the office. Many solvers, like Quoc Tran, wrote computer code to check which numbers worked and which didn’t.
Solver Tim Guindon constructed a Desmos graph that revealed the answer. Tim’s approach turned the information from the problem into equations. For example, if there were N people in your office, what did it mean that you wrote down 73 percent? It meant that there was some number of people A who voted for one of the choices, such that A/N was a percentage equal to 73 point something. Mathematically speaking, that translated to the following equation: floor(100·A/N) = 73. (If the floor function is new to you, worry not. It does exactly what you’d do in recording the percentage — it gets rid of everything after the decimal point.) Tim then went a step further, narrowing down which values of A he should check depending on the value of N. The end result was that there were at least 34 people in the office. Had there been exactly 34 people, 25 people made up 73.53 percent, 20 people made up 58.82 percent and 11 people made up 32.35 percent. This was the smallest value of N that could have produced percentages that start with 73, 58 and 32.
For extra credit, you were asked to find the greatest number of people who couldn’t have worked in your office. We said earlier that there could have been 100 people in your office. Sure enough, any number beyond 100 was also possible, as proven by solver Mitch Schmidt. This is because the spacing between the possible percentages gets smaller and smaller, until you reach a point where there will always be percentages that start with 73, 58 and 32. Starting with N = 100 and working his way down, Mitch found that the biggest number of officemates that didn’t work was 88. Had there been 88 people in the office, 51 people would have made up 57.95 percent, while 52 people made up 59.09 percent. There’s simply no way you could have recorded 58 percent.
Anyway, with that riddle behind us, here’s hoping your office’s holiday party fared better than the typical office party.
Solution to last week’s Riddler Classic
Congratulations to 👏 Hector Pefo 👏 of San Francisco, California, winner of the most recent Riddler Classic.
Last week, I had 10 pairs of socks in a drawer. Each pair was distinct from another and consisted of two matching socks. Alas, I was negligent when it came to folding my laundry, so the socks were not folded into pairs. Fumbling around in the dark, I pulled the socks out of the drawer, randomly and one at a time, until I had a matching pair of socks among the ones I had removed from the drawer. On average, how many socks would I have had to pull out of the drawer in order to get my first matching pair?
We can attack this problem one case at a time, as solver Jess Bianchi did, starting with the first sock. What’s the probability that I’d have a pair after I pull out the first sock? Well, one sock can’t possibly make a pair, so the probability is zero. On to the next case!
What’s the probability that I’d have a pair when I pull out my second sock? The first sock could have been any of the 10 pairs — but whatever pair it belonged to, of the 19 socks remaining in the drawer, only one of them pairs up with the first sock I pulled. That means my chances of making a pair on the second sock were 1/19.
And what about the third sock? To have my first pair upon pulling out the third sock, the second sock must not have made a pair. Since we just found the second sock makes a pair 1/19 of the time, that means it won’t make a pair the remaining 18/19 of the time. Once I’m pulling out that third sock, there are 18 socks remaining in the drawer, and exactly two of them will give me a pair (one that matches the first sock I pulled out, and one that matches the second sock I pulled out), meaning the probability is 2/18. Overall, my chances of getting my first pair with the third sock are then 18/19 · 2/18.
At this point, many solvers saw a pattern emerge. Continuing with the logic above, the probability of getting your first pair with the fourth sock were 18/19 · 16/18 · 3/17, and the chances for the fifth sock were 18/19 · 16/18 · 14/17 · 4/16. With each additional sock, the probability calculations included one more fraction to multiply, whose denominator decreased by one (because there was one less sock in the drawer) and whose numerator decreased by two (one for the sock that was removed and one for its paired sock you can’t pull in order to avoid having a pair). As you’d expect, these probabilities all add up to one upon reaching the eleventh sock, since at that point you’re guaranteed to have a pair by the pigeonhole principle.
To find the average number of socks needed for a pair, you can add up the products of each of these probabilities multiplied by their corresponding number of socks. The average number of socks needed for a pair turns out to be about 5.675 (the exact value is 262,144 divided by 46,189).
But for this puzzle, this solution was just the tip of the iceberg. The extra credit asked for a general solution when there were N pairs of socks instead of just 10 pairs. To the surprise of many, the answer was surprisingly compact. As N gets bigger, the average number of socks needed for a pair approaches √(𝜋N). This approximation worked pretty well for small values of N — for 10 pairs of socks, it gave you a reasonable value of 5.605 — and it got even more accurate as N got bigger.
At this point, you may be wondering how on earth a 𝜋 showed up in the solution (considering there weren’t any circles involved!). The constant 𝜋 can often appear in problems involving infinite sums and, on occasion, in approximating ratios of factorials of large numbers. Proving this result is beyond the scope of this column, but I will refer interested readers to the write-ups of Laurent Lessard, this week’s winner Hector and Emma Knight (who nicely explained why the answer should be proportional to the square root of N).
Still don’t believe me? Well here’s a graph showing how the exact solution compares with N for different values of N, courtesy of Laurent. I mean, just look how close those dots are to the curve!
If there’s a takeaway from all this, it’s that you shouldn’t lose sleep over all your unpaired socks. Pulling them all out of your drawer may be a lot of work, but finding a pair is then only the square root of a lot of work (times the square root of 𝜋).
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 Zach Wissner-Gross at firstname.lastname@example.org.