# A Cat Toy

A friend recently put out a call for help – could anyone help her with her restless cat? It would mope about during the day but then at night it would want to play. Was there something to entertain it during the day so it followed human’s sleep schedules? I saw this as a call for help so rose to the challenge with this cat toy:

Its a toy that randomly moves about to get the ball to bounce irratically. The ball has a failsafe so if it gets caught it will disengage — saving the toy from destruction.

It was made with an Arduino Nano and SG90 Micro Servo. Stay tuned to see what the cat thinks of it!

# A Dark Room With Cards

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: 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:

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: 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:

P(2,3)

P(2,3)

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

Putting it together:

#### $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!

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) = 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) = 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