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.
Riddler Express
In Riddler City, the city streets follow a grid layout, running north-south and east-west. You’re driving north when you decide to play a little game. Every time you reach an intersection, you randomly turn left or right, each with a 50 percent chance.
After driving through 10 intersections, what is the probability that you are still driving north?
Extra credit: Now suppose that at every intersection, there’s a one-third chance you turn left, a one-third chance you turn right and a one-third chance you drive straight. After driving through 10 intersections, now what’s the probability that you are still driving north?
The solution to this Riddler Express can be found in the following week’s column.
Riddler Classic
Polly Gawn loves to play “connect the dots.” Today, she’s playing a particularly challenging version of the game, which has six unlabeled dots on the page. She would like to connect them so that they form the vertices of a hexagon. To her surprise, she finds that there are many different hexagons she can draw, each with the same six vertices.
What is the greatest possible number of unique hexagons Polly can draw using six points?
(Hint: With four points, that answer is three. That is, Polly can draw up to three quadrilaterals, as long as one of the points lies inside the triangle formed by the other three. Otherwise, Polly would only be able to draw one quadrilateral.)
Extra Credit: What is the greatest possible number of unique heptagons Polly can draw using seven points?
The solution to this Riddler Classic can be found in the following week’s column.
Solution to last week’s Riddler Express
Congratulations to 👏 Emma Knight 👏 of Toronto, Canada, winner of last week’s Riddler Express.
Last week, I had a coin with a sun on the front and a moon on the back. I claimed that on most days it was a fair coin. But once a year, on the summer solstice, the coin always came up the opposite side as the previous flip.
Of course, you were skeptical of my claim. You initially figured there was a 1 percent chance that the coin was magical and a 99 percent chance that it was just an ordinary fair coin. You then asked me to “prove” the coin was magical by flipping it some number of times.
How many successfully alternating coin flips would it have taken for you to think there was a 99 percent chance the coin was magical (or, more likely, that I had rigged it so it always alternated)?
Wow, there was a lot of disagreement about this problem! About 40 percent thought the answer was eight flips, 30 percent thought the answer was seven, 12 percent thought the answer was 15 and 8 percent thought the answer was 14. (The remaining 10 percent gave answers ranging from zero to 100.) But before revealing the correct result, let’s take a closer look at what was happening with these coin flips.
Suppose my first flip happened to be a sun, my second flip was a moon, and the outcome continued alternating with every subsequent flip. The more alternating flips I got in a row, the more confident you’d become that the coin was magical.
To quantify this level of confidence, you needed an assist from Bayes’ theorem: Given N alternating flips in the row, the probability that the coin was magical was equal to the probability that a magic coin would generate N alternating flips, multiplied by the prior probability that the coin was magical, then divided by the prior total probability of getting N alternating flips.
Some of these were easier to calculate than others. For example, the probability that a magical coin would generate N alternating flips was 1. (That’s what it meant for the coin to be magical; the flips would always alternate.) And the prior probability that the coin was magical — prior to any flipping to prove it was magical — was given in the statement of the problem: 1 percent, or 0.01. The challenge was to determine the final value to plug into Bayes’ theorem: the prior total probability of getting N alternating flips.
On the (1 percent) off chance the coin was magical, you would always get N alternating flips. But even if the coin wasn’t magical (the remaining 99 percent of the time), you could still get N alternating flips, with a probability that decreased with N. In fact, the probability was 1/2N−1, since the first flip could be a sun or a moon, and the remaining N−1 flips each had a 50 percent chance of being different from the previous flip. All together, that meant the total prior probability of getting N alternating flips was 0.01+0.99/2N−1.
At last, with all that deep thought behind us, it’s time to plug and chug. Given N alternating flips in a row, the probability that the coin was magical was 0.01/(0.01+0.99/2N−1). Now your task was to find the first value of N where this probability exceeded 0.99, meaning you could be 99 percent sure the coin was magical.
Starting with the inequality 0.01/(0.01+0.99/2N−1) ≥ 0.99, some careful rearrangement led to the simplified inequality 2N−1 ≥ 992. The smallest power of two that exceeded 992, or 9,801, was 214, or 16,384. While many thought the answer was 14, it was in fact N−1 that equalled 14, meaning the answer was 15 flips.
And in calculating that tricky prior total probability of getting N alternating flips, if you forgot to account for the 1 percent of the time the coin was magic, you got the incorrect answer of eight flips (or seven, if you again forgot to add one to the exponent). Or you might have discarded the prior probability altogether and looked for the first power of 1/2 that was less than 0.01.
No doubt this was a challenging Express. And in case you were curious, yes, the coin really was magical.
Solution to last week’s Riddler Classic
Congratulations to 👏 Eric Widdison 👏 of Kaysville, Utah, winner of last week’s Riddler Classic.
Last week, King Auric was passing his most prized possession — perfect spheres of solid gold — to his three children. He had spheres with diameters of 1 centimeter, 2 centimeters, 3 centimeters, and so on. To be fair to his children, he wanted to give each an equal weight of gold.
After much trial and error, the king managed to divide his spheres into three groups of equal weight. He was further amused when he realized that his collection contained the minimum number of spheres needed for such a division. How many golden spheres did King Auric have?
An important detail from the puzzle was that the spheres were solid gold, meaning their weight was proportional to the cube of their diameter. In other words, you had to find a whole number N such that 13, 23, 33, … , N3 could be partitioned into three groups with the same sum.
A good place to start was to find the weights of each of those three groups. Summing the cubes from 13 to N3 always equals N2(N+1)2/4, and since each group had a weight that was one-third of the total, the weight of each group was therefore N2(N+1)2/12.
You also knew that the largest sphere must have belonged to one of the three groups, and clearly its weight couldn’t be greater than the sum of its corresponding group. In other words, N3 had to be less than or equal to N2(N+1)2/12. With a little algebraic manipulation, this meant that N had to be 10 or greater.
Also, in order to evenly split the spheres into three groups, you knew that the total sum of the weights, N2(N+1)2/4, had to be divisible by three. That meant N had to either be a multiple of three or two more than a multiple of three. So possible values of N were now 11, 12, 14, 15, 17, 18, etc.
At this point, solver after solver turned to their computer for assistance. As this week’s winner Eric Widdison noted, this problem appeared to be a variant of the famous knapsack problem, which is NP-complete. So it was computers or bust.
Nevertheless, Eric was able to find that the smallest possible number of spheres was 23. The fair division of the spheres was {1, 4, 7, 8, 12, 16, 20, 22}, {2, 5, 9, 11, 14, 15, 17, 23} and {3, 6, 10, 13, 18, 19, 21}. For all three groups, the sum of the cubes was 76,176. That’s a whole lotta gold!
Last week’s extra credit asked you to find the smallest number of spheres that could be evenly shared among other numbers of children, like two, four, five, six, etc.
Solver Allen Gu reported several of these results, along with how long it took his computer to generate each result. With two children, King Auric would need 12 spheres; with four or five children, he would need 24 spheres; with six children, he would need 35 spheres; with seven children, he would need 41 spheres, and with eight children, he would need 47 spheres. At this point, Allen’s computer failed him, and he upgraded to a “beefier” virtual machine. After several hours, he found that with nine children, King Auric would need 53 spheres. Allen is still waiting to hear back from his computer in the case of 10 children.
These results formed a rather unpredictable sequence of integers: 1, 12, 23 (this week’s answer), 24, 24, 35, 41, 47, 53, and so on. And now, thanks to the puzzle’s submitter, Dean Ballard, this sequence has been enshrined for all eternity in the On-line Encyclopedia of Integer Sequences as sequence A330212. While he was there, Dean apparently updated the related sequence, A240070, which looks at splitting up powers other than cubes into three equal groups.
As for the computational difficulty in cranking out these integer sequences, Emma Knight put it best, concluding that “[a]t this point I (and my poor CPU) would advise the royal couple to ease up on their procreation habit.”
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 riddlercolumn@gmail.com.