Can You Stick It To The Genie?

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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.

Riddler Express

I have three dice (d4, d6, d8) on my desk that I fiddle with while working, much to the chagrin of my co-workers. For the uninitiated, the d4 is a tetrahedron that is equally likely to land on any of its four faces (numbered 1 through 4), the d6 is a cube that is equally likely to land on any of its six faces (numbered 1 through 6), and the d8 is an octahedron that is equally likely to land on any of its eight faces (numbered 1 through 8).

I like to play a game in which I roll all three dice in “numerical” order: d4, then d6 and then d8. I win this game when the three rolls form a strictly increasing sequence (such as 2-4-7, but not 2-4-4). What is my probability of winning?

Extra credit: Instead of three dice, I now have six dice: d4, d6, d8, d10, d12 and d20. If I roll all six dice in “numerical” order, what is the probability I’ll get a strictly increasing sequence?

The solution to this Riddler Express can be found in the following column.

Riddler Classic

One day you stumble across a magic genie, who says that if you play a simple game with him, you could win fabulous riches. You take the genie up on his offer, and he hands you a stick of length 1. He says that behind his back is another stick, with a random length between 0 and 1 (chosen uniformly over that interval).

Next, you must break your stick into two pieces and present one of those pieces to the genie. If that piece is longer than the genie’s hidden stick, then you win a prize of \$1 million times the length of your remaining piece. For example, if you present to the genie a length of 0.4, and that’s longer than the genie’s stick, then you win \$1 million times 0.6, or \$600,000. However, if the genie’s stick is longer, then you win nothing.

Being a regular reader of The Riddler, you crunch some numbers and prepare to break your stick in half. But then you have a thought. You ask the genie if you can have more than one turn. For example, if you present the genie with a length of 0.4, but the genie’s stick is longer, can you break off a piece of the remaining length of 0.6 — say, a length of 0.5 — and then present that to the genie? To keep things fair, your winnings will still be proportional to the leftover length. So had the genie’s length indeed been between 0.4 and 0.5, your first and second guesses, then the remaining length would have been 0.1, and you would have won \$100,000.

The genie doesn’t think any of this really matters and says you can have as many turns as you desire. If your goal is to maximize your expected winnings, what will your strategy be? And how much money would you expect to win on average?

The solution to this Riddler Classic can be found in the following column.

Solution to last week’s Riddler Express

Congratulations to 👏 Peter Ji 👏 of Madison, Wisconsin, winner of last week’s Riddler Express.

Last week, The Riddler Social Network was being rebranded as μετα.

A group of 101 people joined μετα, and each person had a random, 50 percent chance of being friends with each of the other 100 people. Friendship was a symmetric relationship on μετα, so if you were friends with me, then I was also friends with you.

I picked a random person among the 101 by the name of Marcia. On average, how many friends would you have expected each of Marcia’s friends to have?

Before answering that question, let’s take a closer look at Marcia. How many friends would she have on average? Well, there were 100 other people on the network, and she had a 50 percent chance of being friends with each of them. So, on average, Marcia would have 50 friends.

But as most readers realized, that wasn’t the case for Marcia’s friends. Why? Because you were given one additional piece of information: By virtue of being friends with Marcia, each of these people had one guaranteed friend. If Randall was one of Marcia’s friends, then Randall still had a 50 percent chance of being friends with each of the other 99 people on the network. That meant his average number of friends was 1 + 99/2, or 50.5.

Now there was a small chance (one in 2100) that Marcia had no friends whatsoever, in which case it was meaningless to ask about her friends’ friends. A few sharp readers pointed out that the puzzle was therefore poorly defined. Based on the puzzle’s wording, I think it was fair to assume that Marcia had at least one friend. Nevertheless, I treated answers of “undefined” as correct as well.

A few solvers — including Matt Luedtke, Sanandan Swaminathan, Jeremy White and Emily Boyajian — connected this riddle to the well-known friendship paradox. This paradox says that in any social network, one’s friends will have more friends than you, on average. Apparently, this also applies to the probabilistic social network known as μετα.

Poke!

Solution to last week’s Riddler Classic

Congratulations to 👏 David Nash 👏 of Portland, Oregon, winner of last week’s Riddler Classic.

The sum of the factors of 36 — including 36 itself — is 91. Coincidentally, 36 inches rounded to the nearest centimeter is … 91 centimeters!

Last week, you had to find another whole number like 36, where you could “compute” the sum of its factors by converting it from inches to centimeters.

In 1959, an inch was defined as being exactly 2.54 cm. That meant if a number N had a sum of factors 𝝈(N), you wanted 2.54N to be very close to 𝝈(N). More specifically, to get the rounding right, you wanted the following inequality to be true: 𝝈(N) − 0.5 ≤ 2.54N < 𝝈(N) + 0.5.

Now you might have heard of a perfect number before — that’s a number whose sum of factors (other than the number itself) equals the number. In other words, the sum of all its factors (including the numbers itself) is twice the number. Meanwhile, numbers whose factors add up to more than twice the number are called abundant numbers. Because 2.54 is greater than 2, that meant the solution had to be an abundant number. Small abundant numbers tend to be the products of small primes, so they have many factors to add up despite their relatively small magnitude.

Nevertheless, many solvers, like Paulina Leperi and Razeen Hossain, wrote code to exhaustively search every number until a solution was found. This first such solution was 378, which was equal to 2·33·7. Its factors were 1, 2, 3, 6, 7, 9, 14, 18, 21, 27, 42, 54, 63, 126, 189 and, of course, 378. The sum of these factors was 960, whereas 2.54 times 378 was equal to 960.12, which indeed rounded down to 960.

For extra credit, you had to find a third whole number with this property, beyond 36 and 378. Many solvers continued running their code until they found another solution. Meanwhile, solver Austin Shapiro found such a solution analytically. First, Austin noted that for any relatively prime X and Y, it was always true that 𝝈(X)𝝈(Y) = 𝝈(XY), which further meant that 𝝈(X)/X · 𝝈(Y)/Y = 𝝈(XY)/(XY).

Here, we wanted 𝝈(N)/N to be approximately 2.54, or 127/50. That numerator of 127 was one less than a power of 2 (and also a Mersenne prime!), which meant it was also the sum of factors for  a smaller power of 2 — in this case, 26, or 64. So Austin rewrote 127/50 as 127/64·32/25. Next, in a happy coincidence, Austin recognized that 32 = 𝝈(31), and that 31 = 𝝈(25). Putting this all together, 127/50 = 𝝈(64)/64 · 𝝈(31)/31 · 𝝈(25)/25. And because 64, 31 and 25 were all relatively prime, you could combine these using the aforementioned multiplicative property to get 127/50 = 𝝈(49,600)/49,600. Sure enough, 49,600 was the next smallest solution. Because of the exact nature of the math here, 49,600 inches was precisely 125,984 cm, just as the sum of the factors of 49,600 was precisely 125,984.

Solvers Elliot Brown, John Adair, Brian Casaday, Eoin O’Brien and Neville Fogarty looked for solutions up through (and past) 1 million but did not find any others. Surely, more such numbers exist. And I bet that if we had a sufficiently long metric ruler, we’d find them.

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.

Footnotes

1. Important small print: In order to 👏 win 👏, I need to receive your correct answer before 11:59 p.m. Eastern time on Monday. Have a great weekend!

Zach Wissner-Gross leads development of math curriculum at Amplify Education and is FiveThirtyEight’s Riddler editor.