A Story of Stacking Rings

Another week, another riddler. This one is from Austin Shapiro:

From Austin Shapiro comes a story of stacking that may stump you:

Mira has a toy with five rings of different diameters and a tapered column. Each ring has a “correct” position on the column, from the largest ring that fits snugly at the bottom to the smallest ring that fits snugly at the top.

Each ring she places will slide down to its correct position, if possible. Otherwise, it will rest on what was previously the topmost ring.

For example, if Mira stacks the smallest ring first, then she cannot stack any more rings on top. But if she stacks the second-smallest ring first, then she can stack any one of the remaining four rings above it, after which she cannot stack any more rings.

Here are a four different stacks Mira could make:

Four possible arrangements of stacks

This got Mira thinking. How many unique stacks can she create using at least one ring?

Extra credit: Instead of five rings, suppose the toy has N rings. Now how many unique stacks can Mira create?

To find this we brute forced solutions for rings of 3 through 7. Here are visualizations for the five and six ring solutions:

5_rings.JPG

Figure 1: All 45 solutions with five rings

 

6_rings

Figure 2: All 104 solutions with six rings

Code can be found here

Set

The Family Game of Visual Perception

During quarantine I found myself playing a lot Set – a card game where you try to find sets of three cards that fit certain constraints

And example Set board

 

A set is three cards where each individual feature (color, shape, number and shading) is either all the same OR all different – here are some examples

examples of sets using the above board

 

Naturally, this had to be automated. My friends were running a “casual distanced hackathon” and I chose this as my project. Here was the hardware setup I used:

Hardware setup

Using the Kinect as a (annoying to work with) RGB camera I was able to take in images and do processesing in OpenCV and python. The program looks at an image of the board, labels the cards, finds sets and reports them with a refresh rate of 0.25s on my 2018 ultrabook.

Here is a video demonstrating it:

 

I was very happy with what I was able to create in one weekend in my first hackathon — I’d definitely do another in the future

Golden Spheres

Another week, another riddler. This one is from Dean Ballard:

King Auric adored his most prized possession: a set of perfect spheres of solid gold. There was one of each size, with diameters of 1 centimeter, 2 centimeters, 3 centimeters, and so on. Their brilliant beauty brought joy to his heart. After many years, he felt the time had finally come to pass the golden spheres down to the next generation — his three children.

He decided it was best to give each child precisely one-third of the total gold by weight, but he had a difficult time determining just how to do that. After some trial and error, he 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 this division. How many golden spheres did King Auric have?

To find this one I found by creating lists of cube numbers and seeing if there was a way to subdivide the subsets into groups that summed to a third of the sum. I was able to find the answer relatively easily without many optimizations (the only one I found was I only looked for subsets if the sum of the cube numbers was divisible by 3).

The division of the 23 spheres for 3 heirs is:

Heir 1: 3, 6, 10, 13, 18, 19, 21

Heir 2: 1, 4, 7, 8, 12, 16, 20, 22

Heir 3: 2, 5, 9, 11, 14, 15, 17, 23


 

I did an extension for the case where the king has a different number of heirs.

The division of the 24 spheres for 4 heirs is:

Heir 1: 7, 9, 21, 23

Heir 2: 8, 10, 11, 16, 17, 22

Heir 3: 1, 2, 3, 4, 14, 18, 24

Heir 4: 4, 6, 12, 13, 15, 19, 20

 

The division of the 24 spheres for the 5 heirs is:

Heir 1: 1, 18, 23

Heir 2: 8, 14, 16, 22

Heir 3: 2, 4, 9, 15, 24

Heir 4: 3, 5, 12, 19, 21

Heir 5: 6, 7, 10, 11, 13, 17, 20

 

 

Can You Join the World’s Biggest Zoom Call?

Another week, another riddler. This one came from Jim Crimmins:

One Friday morning, suppose everyone in the U.S. (about 330 million people) joins a single Zoom meeting between 8 a.m. and 9 a.m. — to discuss the latest Riddler column, of course. This being a virtual meeting, many people will join late and leave early.

In fact, the attendees all follow the same steps in determining when to join and leave the meeting. Each person independently picks two random times between 8 a.m. and 9 a.m. — not rounded to the nearest minute, mind you, but any time within that range. They then join the meeting at the earlier time and leave the meeting at the later time.

What is the probability that at least one attendee is on the call with everyone else (i.e., the attendee’s time on the call overlaps with every other person’s time on the call)?

As a quarantine experiment I solved this live on Twitch.tv in what I called a “speedrun”. About 50 people joined over the two and half hour broadcast — some familiar faces and some people I’d never met.

After cleaning up a bit of the work the next few days we got a solution of 2/3.

Overall, it was a fun experiment. As I noted after, I don’t think live streaming the solving process is the best method — hosting and solving is very taxing and a “worst of both worlds” situation… but one I wanted to try. Stay tuned for new forays into content creation 😂 – face with tears of joy emoji

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?

Untitled

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!

Edit: here is the video including a real cat

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:

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!