Can You Weave the Web?

A spider randomly picks two points within a square, connects them with silk, and extends the connection to the square's edges. Which points are most likely to be on the strand?

Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of myself and Ollie Roeder.

Each week, I present mathematical puzzles intended to both challenge and delight you. Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “Extra Credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.

I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.

This Week’s Fiddler

A spider weaves a web within a unit square (i.e., a square with side length 1) in the following haphazard manner:

First, the spider picks two points at random inside the square. In particular, it picks the points “uniformly,” meaning any point is equally likely to be picked as any other point.

Next, the spider connects the two points with a strand of silk and extends the strand to two sides of the square. For example, here is a web made of 10 silk strands that were picked as described:

Within the unit square, which point (or points) is most likely to be on a new strand of silk, whose two defining points have not yet been picked?

(While the probability that any specific point winds up being precisely on the new strand is zero, some points and regions are nevertheless more likely to be on the strand than others.)

This Week’s Extra Credit

As we just acknowledged, there exists a point (or points) in the unit square that is more likely than any others to be on the randomly selected silk strand.

At the same time, there exists a point (or points) in the unit square that is less likely than any others to be on the random strand.

How much more likely is a most likely point to be on the strand than a least likely point? More specifically, suppose the maximum of the probability density for being on the strand is p_max and the minimum probability density is p_min. What is the ratio p_max/p_min?

Making the ⌊Rounds⌉

There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing an article from Quanta Magazine, which discusses recent developments in the study of sum-free sets.

A sum-free set is a set where no two elements in the set add up to a third element in the set. Erdős previously proved that “any set of N integers has a sum-free subset of at least N/3 elements.”

That lower bound has now been meaningfully raised! Check out the article to find out more—it’s a good read.

Want to Submit a Puzzle Idea?

Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.

Standings

I’m tracking submissions from paid subscribers and compiling a leaderboard, which I’ll reset every quarter. All timely correct solutions to Fiddlers and Extra Credits are worth 1 point each. At the end of each quarter, I’ll 👑 crown 👑 the finest of Fiddlers. (If you think you see a mistake in the standings, kindly let me know.)

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Matt St. Hilaire 🎻 from Chicago, Illinois. I received 63 timely submissions, of which 57 were correct—good for a 90 percent solve rate.

Last week you explored a phenomenon known as a “river”, where spaces between words diagonally align from one line of text to the next. For example, the following text has an 11-line river in the middle:

Instead of English, you analyzed rivers in the (fictional) Fiddlish language, which included only three- and four-letter words. These words were separated by spaces, but there was no other punctuation.

Suppose a line of Fiddlish text was generated such that each next word had a 50 percent chance of being three letters and a 50 percent chance of being four letters. This line also had many, many, many words.

What was the probability that any given character deep into the line was a space?

You knew with certainty that the first three characters in the line had to be letters, and couldn’t be spaces. The fourth character had a 50 percent chance of being a space (when the first word was three letters long), and the same went for the fifth character (when the first word was instead four characters long). Beyond that, the probability a character was a space presumably bounced around a little before settling on some limiting value after many, many words.

So, what was this limiting value?

Well, if the line contained only three-letter words, then 25 percent of the characters would be spaces. And if the line contained only four-letter words, then 20 percent of the characters would be spaces. The answer had to be somewhere between 20 and 25, so perhaps it was the average? That would have been 22.5 percent, meaning the probability the character was a space would have been 9/40.

But that wasn’t quite right. While you expected the same number of three- and four-letter words to occur, the four-letter words took up more characters than three-letter words did. That meant you could expect spaces to occur slightly less frequently.

Let’s work through the math more carefully. Suppose you were looking at (a large number) N consecutive characters deep into a line. And suppose there were A three-letter words among these characters, which accounted for 3A letters and another A spaces. Since the number of three- and four-letter words should have been about equal in this large data set, you could similarly expect A four-letter words. These in turn accounted for 4A letters and another A spaces. All together, you had 3A + A + 4A + A = 9A characters, which meant N = 9A. And among these 9A characters, 2A of them were spaces. Therefore, the probability any given character was a space was 2/9, or about 22.2 percent. Sure enough, this was ever so slightly less than the 22.5 percent figure we previously hypothesized.

Several solvers were able to confirm this result numerically by computing the exact probability of a space at each location in the line. We already said the probabilities for the first through fifth characters were 0, 0, 0, 50, and 50 percent, respectively. There was also a recurrence relation at play here. For the k-th character to be a space, you needed the (k−5)-th character to be a space and you needed that space to be followed by a four-letter word; alternatively, you needed the (k−4)-th character to be a space and you needed that space to be followed by a three-letter word. So if p(k) was the probability the k-th character was a space, then p(k) = p(k−5)/2 + p(k−4)/2.

Using the initial probabilities and the recurrence relation, solvers like Michael Schubmehl plotted several more probabilities, finding they indeed appeared to converge to 2/9:

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Lowell Vaughn 🎻 from Bellevue, Washington. I received 44 timely submissions, of which 34 were correct—good for a 77 percent solve rate.

Fiddlish was written using a monospace font, meaning each character (including spaces) took up the same amount of horizontal space. As before, lines of text were very, very long, and each next word had a 50 percent chance of being three letters and a 50 percent chance of being four letters. Each line began with a new word (i.e., words at the end of a line were not hyphenated into the next line).

For Extra Credit, you supposed the 12th character of a specific line of text was a space. You wanted to know how long the river down and to the right from this space would be. For example, if the 13th character on the next line and the 14th character on the line after that were both spaces, but the 15th character on the very next line was not a space, the river would have had a length of 3. (By this definition, the length of the river was always at least 1.)

On average, how long did you expect the resulting river from the given space (again, the 12th character in its line) to be?