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 next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
It’s summertime and my local swimming pool, which has exactly five swimming lanes (and no general swim area), may be opening in the coming weeks. It remains unclear what social distancing practices will be required, but it’s quite possible that swimmers will not be allowed to occupy adjacent lanes.
Under these guidelines, the pool could accommodate at most three swimmers — one each in the first, third and fifth lanes.
Suppose a queue of swimmers arrives at the pool when it opens at 9 a.m. One at a time, each person randomly picks a lane from among the lanes that are available (i.e., the lane has no swimmer already and is not adjacent to any lanes with swimmers), until no more lanes are available.
At this point, what is the expected number of swimmers in the pool?
Extra credit: Instead of five lanes, suppose there are N lanes. When no more lanes are available, what is the expected number of swimmers in the pool?
The solution to this Riddler Express can be found in the following week’s column.
Riddler Classic
Just in time for the Fourth of July, this week’s Classic is about stars on the American flag:
The 50 stars on the American flag are arranged in such a way that they form two rectangles. The larger rectangle is 5 stars wide, 6 stars long; the smaller rectangle is embedded inside the larger and is 4 stars wide, 5 stars long. This square-like pattern of stars is possible because the number of states (50) is twice a square number (25).
Now that the House of Representatives has passed legislation that would make the District of Columbia the fifty-first US state — and renamed Washington, Douglass Commonwealth, in honor of Frederick Douglass — a natural question is how to aesthetically arrange 51 stars on the flag.
One pleasing design has a star in the middle, surrounded by concentric pentagons of increasing side length, as shown below. The innermost pentagon has five stars, and subsequent pentagons are made up of 10, 15 and 20 stars. All told, that’s 51 stars.
It just so happens that when N equals 50, N is twice a square and N+1 is a centered pentagonal number. After 50, what is the next integer N with these properties?
The solution to this Riddler Classic can be found in the following week’s column.
Solution to last week’s Riddler Express
Congratulations to ÑÑâÐ Josiah Kollmeyer ÑÑâÐ of Baton Rouge, Louisiana, winner of last week’s Riddler Express.
Last week, you were driving north in Riddler City, whose streets run north-south and east-west. At every intersection, you randomly turned left or right, each with a 50 percent chance.
After driving through 10 intersections, what was the probability that you were still driving north?
One way to solve this was to look at what happened after the first few intersections. It wasn’t long before a pattern emerged.
After the first intersection, you had a 50 percent chance of turning east and a 50 percent chance of turning west. In the event you turned east, upon reaching the second intersection, you then had a 50 percent chance of turning north and a 50 percent chance of turning south. But in the event you turned west, you still had a 50 percent chance of turning north and a 50 percent chance of turning south. Putting these possibilities together, that meant that after the second intersection, you were definitely driving north or south, each with a 50 percent chance.
Following this reasoning, solver Lily Koffman realized that after every odd number of intersections, you were driving east or west with equal probability, and after every even number of intersections, you were driving north or south with equal probability. Since the given number of intersections, 10, was even, that meant there was a 50 percent chance you were driving north in the end.
For extra credit, instead of just turning left or right, you now also had the option of driving straight — each with a one-third chance. After driving through 10 intersections, now what was the probability that you were still driving north?
This was certainly a trickier scenario. Mike Bourdaa solved it by looking at what would happen if there were fewer intersections, hoping to find a pattern. After N intersections, there were a total of 3N equally likely sequences of turns you could make. Mike found that approximately 3N/4 of these sequences — or, more precisely, the smallest whole number greater than 3N/4 — resulted in you driving north.
But that certainly wasn’t the only approach that worked here. Juan Casaravilla solved it using linear algebra, by first lining up the probabilities of driving north, south, east or west into a vector, which was initially [1; 0; 0; 0]. Each intersection could be modeled as multiplying this vector by the transition matrix [1/3 0 1/3 1/3; 0 1/3 1/3 1/3; 1/3 1/3 1/3 0; 1/3 1/3 0 1/3], where the output of this multiplication was a new probability vector that revealed your updated chances of driving north, south, east or west.
But why would you ever want to go through the hassle of encoding an intersection as a matrix in the first place? Well, if each intersection was equivalent to multiplying by a matrix, then driving through 10 intersections was equivalent to multiplying by 10 identical copies of that matrix — or, better yet, multiplying by the matrix raised to the 10th power, an operation that any computer can do with ease.
It turned out that your chances of driving in each of the four directions rapidly approached 25 percent. After 10 intersections, your chances of driving north stood at precisely 4,921/19,683, or about 25.00127 percent.
Just to be extra sure, a few solvers went ahead and checked their work via computer simulation. Daniel Silva-Inclan ran 1,000 trials and verified that after 10 intersections, the probabilities of driving in all four directions were very close to 25 percent.
There’s definitely a life lesson here. If you ever find yourself approaching an intersection and you really want to come out of it driving in a random direction — but you know that pulling a U-turn is illegal — then don’t lose heart. Instead, randomly drive straight or turn left or right at each intersection for a few minutes. Before you know it, you’ll be driving in a random direction.
Yes, that was definitely an important life lesson.
Solution to last week’s Riddler Classic
Congratulations to ÑÑâÐ Eli Wolfhagen ÑÑâÐ of Brooklyn, New York, winner of last week’s Riddler Classic.
Last week, Polly Gawn was playing “connect the dots.” She specifically wanted to connect six dots so that they formed the vertices of a hexagon. To her surprise, she found that there were many different hexagons she could draw, each with the same six vertices.
What was the greatest possible number of unique hexagons Polly could draw using six points?
If the question had ended there, then there would have been some ambiguity around the use of the word “hexagon.” If self-intersecting hexagons (meaning the edges coincided or crossed each other) were allowed, then all you had to do was count how many ways she could connect the six points, one at a time. She could pick any starting point and then choose among the remaining five points to connect it to, then pick four points, then three, then two, and finally one. But wait — each polygon was the same whether she traversed its points in one direction or the other, so she had double counted. Dividing by two, that meant there were 60 total hexagons Polly could have drawn.
But if you read the hint, you saw that Polly was only counting simple hexagons — that is, hexagons whose sides didn’t cross. This was decidedly harder, but was within the realm of possibility if you had a weekend to kill and a bountiful supply of scratch paper.
Many solvers came close, missing a few potential hexagons. In the end, it was three points that all lay within the triangle formed by the other three points that produced the most polygons. Solvers Laurent Lessard and Emma Knight both arrived at this arrangement by leaning on the work of Oswin Aichholzer. They looked at “untangled” complete graphs that had the minimal number of intersections, arguing that this would result in the maximal number of polygons.
Without further ado, here is one such arrangement of six points and all the polygons it produces:
Polly could draw at most 29 hexagons — a far cry from the upper bound of 60.
For extra credit, you were asked to find the greatest possible number of unique heptagons Polly could draw using seven points. In this case, the upper bound was 420, suggesting this was beyond the realm of pencil, paper and patience. Indeed, the greatest possible number of heptagons was 92.
As some solvers noted, there’s an OEIS sequence for that — sequence A063546, to be exact, which lists the “largest number of crossing-free Hamiltonian cycles of n points in the plane.” Or as Polly likes to call them, polygons. (Yes, simple polygons.)
According to the sequence, Polly could draw at most 339 octagons (drawn below, courtesy of solver Josh Silverman), 1,282 nonagons and 4,994 decagons.
While the precise pattern for this sequence remains unknown, it is known to grow exponentially. Erik Demaine has followed the literature on this problem and tracked the evolution of the upper and lower bounds. As of 2011, it was known that as the number of points n increases, the maximal number of polygons is somewhere between 4.642n and 56n.
Let’s not overlook that many of the polygons from the above animations would make awesome corporate logos. If your mountain biking startup is in need of some edgy graphic design, call me.
Want more riddles?
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.