Another week, another riddler. This one is from Blue Taylor:

You’re in a dark room and seated at a table with a deck of 52 cards on it, stacked into a single pile. You also happen to know that currently, within that stack of cards, exactly 13 of them are face up, while all the others are face down.

While you can’t see the cards, you can feel them and move them around. But you can’t tell by touch which cards are face up and which are face down.

How can you make two piles of cards that are guaranteed to have the same number of face-up cards? (And yes, each of these two piles must have at least one card.)

This was a fun problem. The solution:

Create two piles, one with 39 cards and the other with 13 cards. The pile with 39 cards has X that are face up. Therefore the other pile has 13 – X. When you flip every card in that pile over it will have 13 – (13-X), or X cards flipped over — which is the same as the other pile. Easy!

Jim Propp and the Unique Observed Series

Another week, another riddler. This one is from math professor Jim Propp:

At first glance, this might look like one of those annoying memes about order of operations that goes viral every few years — but it’s not.

When you write lengthy mathematical expressions using parentheses, it’s always clear which “open” parenthesis corresponds to which “close” parenthesis. For example, in the expression (1+2(3−4)+5), the closing parenthesis after the 4 pairs with the opening parenthesis before the 3, and not with the opening parenthesis before the 1.

But pairings of other mathematical symbols can be more ambiguous. Take the absolute value symbols in Jim’s example, which are vertical bars, regardless of whether they mark the opening or closing of the absolute value. As Jim points out, |−1|−2|−3| has two possible interpretations:

    • The two left bars are a pair and the two right bars are a pair. In this case, we have 1−2·3 = 1−6 = −5.
    • The two outer bars are a pair and the two inner bars are a pair. In this case, we have |−1·2−3| = |−2−3| = |−5| = 5.

Of course, if we gave each pair of bars a different height (as is done in mathematical typesetting), this wouldn’t be an issue. But for the purposes of this problem, assume the bars are indistinguishable.

How many different values can the expression |−1|−2|−3|−4|−5|−6|−7|−8|−9| have?

This problem was solved by finding all the ways brackets can exist then narrowing it down based on if it lead to something valid. The method for narrowing it down were:

  • at any point there have to be the same or more open brackets than closed brackets
  • at the end there have to be as many open brackets as closed brackets

Using this and Pythons “eval” function we can find the number of solutions: 39

And I did a minor extension! If we take the the index to be the integers from -1 to -2*(i)-1 (so the inputs are |-1|, |-1|-2|-3|, |-1|-2|-3|-4|-5|, etc) and find the number of unique solutions we get the following series:

Capture.JPG

This is a unique solution in the OEIS that I was able to get accepted. Fun!

The actual code is here

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