A Hexagon Problem

Another week, another riddler. This one was from Zach Wissner-Gross:

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:

Spelling Bee screenshot, with the required letter G, and the additional letters L, A, P, X, M and E.

The goal is to identify as many words that meet the following criteria:

    1. The word must be at least four letters long.
    2. The word must include the central letter.
    3. 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.

For consistency, please use this word list to check your game score.2

This problem was very fun. The methodology was simple — brute force every letter combination for the set of 6 “ring letters” and every letter for the “hub”.

Getting something that worked, however, was the fun part. Initially, the first iteration was very slow to work. It took something along the lines of 15s to run through each combination. Given that there are 3,364,900 (25 * nCr(24,6)) combinations to test, this is would have taken 584 days to run which is infeasible.

Through a host of improvements we got the checks to take ~10ms which made the entire process take a few hours. This was run overnight and led us to the solution:

honeycomb

Hub: r     Ring: aegint

 

This honeycomb will result in 3898 points from the words listed here.

The code used to generate this is located here.

 

Can You Find A Matching Pair Of Socks?

Another week, another riddler. This one was from Kathy Bischoping:

I have 10 pairs of socks in a drawer. Each pair is distinct from another and consists of two matching socks. Alas, I’m negligent when it comes to folding my laundry, and so the socks are not folded into pairs. This morning, fumbling around in the dark, I pull the socks out of the drawer, randomly and one at a time, until I have a matching pair of socks among the ones I’ve removed from the drawer.

On average, how many socks will I pull out of the drawer in order to get my first matching pair?

(Note: This is different from asking how many socks I must pull out of the drawer to guarantee that I have a matching pair. The answer to that question, by the pigeonhole principle, is 11 socks. This question is instead asking about the average.)

Extra credit: Instead of 10 pairs of socks, what if I have some large number N pairs of socks?

This problem is just strict probabilities. The form of our answer is:

EV(p) = P(2,p) * 2 + P(3,p) * 3 + ... + P(p,p) * p

Where the probability of getting a sock at each pull is recursively discovered with

P(x,p) = (1 - \sum\limits_{k = 2}^x P(k-1,p)) (\frac {x-1}{2*p - x - 1})

As an example, here is what the probability looks like when you have three pairs of socks:

General form:

EV(3) = P(2,3) * 2 + P(3,3) * 3

P(2,3)

P(2,3) = (1 - \sum\limits_{k = 2}^x P(k-1,3)) (\frac {2-1}{2*3 - 2 - 1})

P(2,3) = 1 * (\frac {1}{3})

P(2,3) = \frac {1}{3}

P(2,3)

P(3,3) = (1 - \sum\limits_{k = 2}^x P(k-1,3)) (\frac {3-1}{2*3 - 3 - 1})

P(3,3) = (1 - \frac {1}{3}) * (\frac {2}{2})

P(3,3) = \frac {2}{3}

Putting it together:

EV(3) = \frac {1}{3} * 2 + \frac {2}{3} * 3

EV(3) = \frac {8}{3} \approx 2.667

Extending this to 10 gives us an answer of 5.675 socks removed from the drawer, on average.

A Particularly Prismatic Puzzle

Another week, another riddler. This was a fun one from Steve Abney:

Suppose I have a rectangle whose side lengths are each a whole number, and whose area (in square units) is the same as its perimeter (in units of length). What are the possible dimensions for this rectangle?

Alas, that’s not the riddle — that’s just the appetizer. The rectangle could be 4 by 4 or 3 by 6. You can check both of these: 4 · 4 = 16 and 4 + 4 + 4 + 4 = 16, while 3 · 6 = 18 and 3 + 6 + 3 + 6 = 18. These are the only two whole number dimensions the rectangle could have. (One way to see this is to call the rectangle’s length a and its width b. You’re looking for whole number solutions to the equation ab = 2a + 2b.)

On to the main course! Instead of rectangles, let’s give rectangular prisms a try. What whole number dimensions can rectangular prisms have so that their volume (in cubic units) is the same as their surface area (in square units)?

To get you started, Steve notes that 6 by 6 by 6 is one such solution. How many others can you find?

To solve this I set the volume equation

V = a b c

To be equal to the surface area equation

SA = 2ab + 2bc + 2bc

Rearranging, we can solve for a

a = \frac{2bc}{bc-2b-2c}

Then we iterate through the the first ten thousand integers for b and c to see if it leads to an integer value for a. It works for the following values:

(3, 8, 24)
(3, 9, 18)
(4, 8, 8)
(4, 6, 12)
(6, 6, 6)
(3, 12, 12)
(3, 10, 15)
(3, 7, 42)
(4, 5, 20)
(5, 5, 10)

Do I conclusively know that these are the only ones? No. But the fact that there aren’t any between 50 – 10,000 means I don’t think there are any after 10,000… but I’d be excited to be proven wrong!

How Fast Can You Skip To Your Favorite Song?

Another week, another riddler. This one was fun, even if a bit lackluster. Austin Chen’s problem reads:

You have a playlist with exactly 100 tracks (i.e., songs), numbered 1 to 100. To go to another track, there are two buttons you can press: (1) “Next,” which will take you to the next track in the list or back to song 1 if you are currently on track 100, and (2) “Random,” which will take you to a track chosen uniformly from among the 100 tracks. Pressing “Random” can restart the track you’re already listening to — this will happen 1 percent of the time you press the “Random” button.

For example, if you started on track 73, and you pressed the buttons in the sequence “Random, Next, Random, Random, Next, Next, Random, Next,” you might get the following sequence of track numbers: 73, 30, 31, 67, 12, 13, 14, 89, 90. You always know the number of the track you’re currently listening to.

Your goal is to get to your favorite song (on track 42, of course) with as few button presses as possible. What should your general strategy be? Assuming you start on a random track, what is the average number of button presses you would need to make to reach your favorite song?

This type of problem is fun because you can make a model of it and test it against your brute force case pretty easily. My model was to find a threshold at which you press random — but once your “random” function gets you below the threshold press “next” until you get to the selected song. This model ended up being correct.

Here is how I represented the model with the threshold at 0 (we press random until we hit the exact song we want):

f_{0}(x) = \frac{1}{100}(x) + \frac{99}{100}(f_{0}(x) + 1)

 

f_{0}(x) = x + 99

 

This shows it would take 99 button presses on average. And here it is with a threshold of 1 (if we are one or less away we’ll press next to get to the song):

f_{1}(x) = \frac{1}{100}(x) + \frac{1}{100}(1 + x) + \frac{98}{100}(f_{0}(x) + 1)

 

f_{1}(x) = x + 49.5

 

This shows it would take 49.5 button presses on average. Finally, here is the equation for a generalized threshold, R:

f_{R}(x) = x + \frac{\binom {R+1}{2} + 100 - R}{R}

 

This is minimized when R = 13 for an expected 12.643 button presses.

 

Fun fact: You can use the equation above to find for different sized playlists by replacing the 100 with your playlist size. For a 10,000 song playlist? It takes a surprisingly low 139.92 presses

Evaluating Expected Values

Another week, another riddler. I really liked this one even if it was a bit linear. Ricky Jacobson’s problem reads:

You are given a fair, unweighted 10-sided die with sides labeled 0 to 9 and a sheet of paper to record your score. (If the very notion of a fair 10-sided die bothers you, and you need to know what sort of three-dimensional solid it is, then forget it — you have a random number generator that gives you an integer value from 0 to 9 with equal probability. Your loss — the die was a collector’s item.)

To start the game, you roll the die. Your current “score” is the number shown, divided by 10. For example, if you were to roll a 7, then your score would be 0.7. Then, you keep rolling the die over and over again. Each time you roll, if the digit shown by the die is less than or equal to the last digit of your score, then that roll becomes the new last digit of your score. Otherwise you just go ahead and roll again. The game ends when you roll a zero.

For example, suppose you roll the following: 6, 2, 5, 1, 8, 1, 0. After your first roll, your score would be 0.6, After the second, it’s 0.62. You ignore the third roll, since 5 is greater than the current last digit, 2. After the fourth roll, your score is 0.621. You ignore the fifth roll, since 8 is greater than the current last digit, 1. After the sixth roll, your score is 0.6211. And after the seventh roll, the game is over — 0.6211 is your final score.

What will be your average final score in this game?

This type of problem is fun because it relies on knowing expected values of lower rolls. Here is what a simple case looks like where you have a two sided die:

Value(2) #if you roll a 2 sided die:
	0: (1/2) * 0
	1: (1/2) * (1 + (1/10) * Value(2))

What does this mean? If you rolled a two sided die with these rules there are two possible outcomes and they each have an equal probability of coming up. The first is you roll a zero, in which case you get no additional points and the round is over. The second option is you roll a 1, in which you get one point and you get a tenth of the value of rolling another two sided die.

This is simple algebra and looks like this:

v2.png

Extending it here is what the 3 sided die case looks like:

Value(3) #if you roll a 3 sided die:
	0: (1/3) * 0
	1: (1/3) * (1 + (1/10) * Value(2))
	2: (1/3) * (2 + (1/10) * Value(3))

Now there are three options because we can roll a zero, one and two. Again, we use algebra:

v3.png

This can be extended all the way to the ten sided die case:

Value(10) #if you roll a 10 sided die:
	0: (1/10) * 0
	1: (1/10) * (1 + (1/10) * Value(2))
	2: (1/10) * (2 + (1/10) * Value(3))
	3: (1/10) * (3 + (1/10) * Value(4))
	4: (1/10) * (4 + (1/10) * Value(5))
	5: (1/10) * (5 + (1/10) * Value(6))
	6: (1/10) * (6 + (1/10) * Value(7))
	7: (1/10) * (7 + (1/10) * Value(8))
	8: (1/10) * (8 + (1/10) * Value(9))
	9: (1/10) * (9 + (1/10) * Value(10))

This evaluates to V(10) = 100/19 = 4.7368

Halloween Candy Problem

Another week, another Riddler. This is a puzzle about finding the number of combinations you can make of a candy:

Now that Halloween has come and gone, your chances of getting free candy have similarly disappeared. Desperate for sugar, you wander into the candy store, where three kinds of candy are being sold: Almond Soys (yummy, sounds vegan!), Butterflingers and Candy Kernels.

You’d like to buy at least one candy and at most 100, but you don’t care precisely how many you get of each or how many you get overall. So you might buy one of each, or you might buy 30 Almond Soys, six Butterflingers and 64 Candy Kernels. As long as you have somewhere between one and 100 candies, you’ll leave the store happy.

But as a member of Riddler Nation, you can’t help but wonder: How many distinct ways are there for you to make your candy purchase?

To solve this problem I used a summation of combinations. You can think of it in the following two forms:

T(s) = \sum_{n=1}^{s} \binom{n+2}{2} = \sum_{n=1}^{s} (n+1)(n+1)/2

 

Where s is the total number of candies. This evaluates to:

T(100) = 176,850

 

This is the same as summing the first one hundred terms of the Triangle Number Sequence (well, after skipping the first term).

 

New Sultan’s Dowry Problem

Another week, another Riddler. This is a puzzle about maximizing a selection with limited resources:

From Julien Beasley, a new spin on the Sultan’s Dowry Problem, a classic problem of matrimony:

The sultan has asked her vizier to present her with 10 candidates for marriage. The vizier has searched the kingdom for the 10 most desirable partners, but he does not know whom the sultan will prefer. If she saw them all at the same time, she would easily be able to rank them from 1 (the best partner) to 10 (the worst partner). But the vizier can only present the candidates one at a time — very hard to sync everybody’s calendars, even back then — and in a random order. Upon seeing each candidate, the sultan must reject or accept him. If a candidate is rejected, the sultan cannot pick him again. But on seeing each new candidate, she knows exactly where he’d stack up relative to the candidates she has rejected. If she strategizes, what’s the highest rank she can expect her chosen candidate to have on average?

For example, if she simply accepted the first candidate presented to her, his rank could be anywhere from 1 to 10 with equal probability, averaging to 5.5. Surely she can do better…

This was a difficult problem. With each candidate you have more information to make a decision — but wait too long and you don’t get to make a decision.

Here are the acceptance criteria that I suggest using:

[N/A, N/A, N/A, 3, 4, 4, 5, 6, 7, 0]

What does this mean? Start by always letting the first three candidates pass. Then, if the next candidate is better then 3 of the previous candidates accept them. If you don’t, accept the next if they are better than 4 of the previous candidates. Continue like this through the array — always accepting the last candidate if you get there.

Using this method you will have a suitor with an average value of 8.34166

I hope to have an explanation of the math behind why this works later in the week