Can You Salvage Your Rug?

Illustration by Guillaume Kurkdjian
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 or send me an email.
Riddler Express
From Michael Amspaugh comes a riddle that will pull the rug out from under you:
I have a rug that is 12 feet long and nine feet wide. Unfortunately, after many years of using it as a putting green, a narrow section in the middle had to be excised. That middle strip was eight feet long and one foot wide, as shown below.

Upon seeing the state of the rug, my neighbor (and golf partner) suggested I cut the rug into two pieces and sew them back together so that it formed a square rug, 10 feet by 10 feet, with no holes (shown below).

How was this possible?
Riddler Classic
Today I happen to be celebrating the birthday of a family member, which got me wondering about how likely it is for two people in a room to have the same birthday.
Suppose people walk into a room, one at a time. Their birthdays happen to be randomly distributed throughout the 365 days of the year (and no one was born on a leap day). The moment two people in the room have the same birthday, no more people enter the room and everyone inside celebrates by eating cake, regardless of whether that common birthday happens to be today.
On average, what is the expected number of people in the room when they eat cake?
Extra credit: Suppose everyone eats cake the moment three people in the room have the same birthday. On average, what is this expected number of people?
Solution to last week’s Riddler Express
Congratulations to 👏 Shawn Mier 👏 of Buffalo Grove, Illinois, winner of last week’s Riddler Express.
Last week, you analyzed a digital 12-hour clock that displayed 10 digits: two digits representing the hour (from “00” to “12”), two digits representing the minute, two digits representing the second and four digits representing the year.
When did this clock next use every digit from 0 to 9?
It was helpful to arrange the digits from most significant (i.e., representing the greatest amount of time) to least significant (representing the least amount of time). We can write this as YYYY:HH:MM:SS, with Y representing “year,” H representing “hour,” M representing “minute” and S representing “second.”
At the time of this writing, the year is 2022, which meant the first Y had better be a 2. Ideally, the second Y was also a small digit, so let’s suppose it was 0. Because it was a 12-hour clock, the first H then had to be 1, which meant HH was 10 (not allowed since we already used the zero), 11 (not allowed since digits can’t repeat) or 12 (not allowed since we already used the two). Yikes! This meant the second Y couldn’t be 0, so our next best option was to have it be 1. In other words, the answer was some time in the 22nd century.
Next, you could use up some of the higher-valued digits toward the end of the solution. The first digit of M and S both had to be less than six, so HH:MM:SS was optimally 07:48:59. That left two remaining digits: 3 and 6.
In the end, the next time the clock used every digit from 0 to 9 was 2136:07:48:59, or 7:48 a.m. (and 59 seconds) in the year 2136. As solver Kiera Jones pointed out, the first time this would happen was specifically on the morning of January 1, 2136.
That’s a little over a century from now. But the good news is that you wouldn’t have to wait long for the next time the clock used all 10 digits — that came less than a minute later, at 7:49 a.m. (and 58 seconds). And then again at 8:47 (and 59 seconds). And then again …
Solution to last week’s Riddler Classic
Congratulations to 👏 Eric Snyder 👏 of Everett, Washington, winner of last week’s Riddler Classic.
Last week, I had 14 pairs of socks in my laundry basket that I needed to pair up. To do this, I used a chair that could fit nine socks, at most. I randomly drew one clean sock at a time from the basket. If its matching counterpart was not already on the chair, then I placed it in one of the nine spots. But if its counterpart was already on the chair, then I removed it from the chair (making that spot once again unoccupied) and placed the folded pair in my drawer.
What was the probability I could fold all 14 pairs without ever running out of room on my chair?
Given the computational complexity of this puzzle, it made sense that many solvers decided to simulate thousands or even millions of laundry baskets and see how often all the socks could be folded. Clement Lelievre from Blois, France, ran 100,000 simulations, finding that all socks could be folded very nearly 70 percent of the time.
Multiple solvers were able to find an exact solution, again with the help of a computer. But before getting to that, I wanted to highlight a geometric interpretation of this puzzle. You could think of folding the socks as navigating a grid, as shown below. Initially, there were 14 pairs of socks in the basket. In the end, there were zero pairs of socks in the basket. And between these two end states, there were many paths indicated by the arrows from one state to another. The height of each state represented how many unfolded socks there were on the chair. To solve the puzzle, you had to find the probability of successfully navigating this grid without ever exceeding a height of nine — that is, without entering the red zone at the top of the grid. This calculation remained tricky, since the probabilities of transitioning from one state to the next depended on how many paired and unpaired socks remained in the basket.

Josh Silverman called the number of single socks in the basket (and therefore the number of socks laid out on the chair) s, and the number of paired (or “doubled”) socks in the basket d. Then the probability of picking out a single sock from the basket and hence removing a sock from the chair was s/(s+2d), while the probability of pulling out a paired sock from the basket and hence adding a sock to the chair was 2d/(s+2d).
From there, Josh plugged these probabilities into a recursive formula and (with the assistance of a computer) determined that the probability of never having more than nine socks on the chair was precisely 15,627,431/22,309,287, or about 70.049 percent — a figure that agreed with Blois’s simulations.
For extra credit, you were asked for a more general solution, where the number of pairs of socks and the capacity of the chair were both variable. Solvers Emily Boyajian and Michael Goldwasser created heat maps that illustrated the probability of being able to fold your socks as a function of these parameters. Here was Emily’s heat map:

When the maximum number of socks on the chair was much greater than half the number of pairs in the basket — or rather, when the chair could hold much more than a quarter of all the socks — you had a very good chance of being able to fold them. But when the chair couldn’t hold nearly a quarter of all the socks, your chances of folding were quite poor. This phase transition, when the chair could hold just about a quarter of all the socks, was mathematically very interesting.
In any case, if you have many pairs of socks, make sure you have a big enough chair.
Want more puzzles?
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.