Can You See the Forest for the Trees?

Feast your eyes on an infinite grid of cylinders. (Or a grid that appears infinite.)

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. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.

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

You find yourself amidst what appears to be an infinite grid of trees. For the purposes of this puzzle, let’s suppose each tree is a perfect cylinder. You are at the point (0, 0), but there’s a tree with a radius of 0.25 units (and diameter 0.5 units) centered at every other point in the plane with integer coordinates.

Of course, you can’t actually see infinitely many trees. Most of them are obscured by the trees immediately around you. As you look around in all directions, how many distinct trees are you able to see?

Extra Credit

Once again, you are located at (0, 0) amidst an infinite grid of cylindrical trees. But this time, the trees are narrower, each with a radius of 0.1 units (and diameter 0.2 units).

When you look due east, your line of sight is 0.9 units, thanks to the tree centered at (1, 0). But if you look in other directions, it’s possible to see farther away.

How long is your longest line of sight? Assume you are looking level with the ground, so that this is a two-dimensional puzzle (rather than three-dimensional one).

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 a riddle posted by Mike Lawler, originally from the collection “Heard on the Street: Quantitative Questions from Wall Street Job Interviews” by Timothy Falcon Crack:

I have dropped 10,000 ants randomly onto a ruler that is one meter (i.e., 100 centimeters) long and oriented to point north-south. The ants are of very small size and mass. Each ant walks at a steady pace of one centimeter per second in a straight line parallel to the long edge of the ruler. Their initial direction is randomly either north or south. The ants are all from the same colony and possess and inherited vision problem: they have peripheral vision only. This means that they can collide with each other if they meet head on (although very small, they are large enough to collide). If two ants do collide head on, however, then they each turn around instantly and head back the way they came at their steady pace. With so many ants in one small space, a single ant may experience multiple collisions before it walks off the ruler. So, how long must you wait to be sure that all the ants have walked off the ruler?

Be warned, the ants may not need as much time as you initially think!

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Ari 🎻, from Oxford, United Kingdom. I received 41 timely submissions, of which 34 were correct—good for a very respectable 83 percent solve rate.

Last week’s puzzle involved braille characters, which are formed by raised dots arranged in a braille cell, a three-by-two array. With six locations for dots, each of which is raised or unraised, there are 2⁶, or 64, potential braille characters (including the empty cell with zero raised dots).

Each of the 26 letters of the basic Latin alphabet (shown below) has its own distinct arrangement of dots in the braille cell. What’s more, while some arrangements of raised dots are rotations or reflections of each other (e.g., E and I, R and W, etc.), no two letters are translations of each other. For example, only one letter (A) consists of a single dot—if there were a second such letter, A and this letter would be translations of each other.

Of the 64 total potential braille characters, how many were in the largest set such that no two characters consisted of raised dot patterns that were translations of each other?

Several solvers, including the team known as the “MassMutual Riddlers,” figured this out by starting with all 64 potential characters and removing those that were translations of each other. For example, as we already said, there were six arrangements that consisted of a single raised dot, which together accounted for just one pattern in the final set.

Here’s a summary of which arrangements were translations of each other, and how many of them therefore had to be removed from the final set:

• One dot had six possible arrangements, five of which had to be removed.

• Two dots arranged horizontally had three possible arrangements (the top row, the middle row, and the bottom row), two of which had to be removed.

• Two dots arranged vertically had four arrangements, three of which had to be removed.

• Two dots arranged vertically with a space between them had two arrangements, one of which had to be removed.

• Two dots arranged diagonally had two arrangements, one of which had to be removed. And because there were two possible diagonal arrangements (top-left and bottom-right vs. top-right and bottom-left), that meant two removals.

• Three dots arranged vertically had two arrangements, one of which had to be removed.

• Three dots arranged in an “L” shape had two arrangements, one of which had to be removed. And because there were four possible “L” arrangements, that meant four removals.

• Four dots arranged in a square had two arrangements, one of which had to be removed.

Adding up the results, there were 5 + 2 + 3 + 1 + 2 + 1 + 4 + 1, or 19, translationally redundant arrangements of raised dots that had to be removed. That meant the largest set without any characters that could be translated into each other had 64−19, or 45 characters.

Among the 45, one character was essentially a blank piece of paper, with zero raised dots. If you excluded this and responded with an answer of 44, worry not—I still marked you as correct.

If you’re still not convinced this was the answer, solver 🎬 Andy Quick 🎬 sketched out one such set of 44 characters (excluding the one with zero raised dots):

A few solvers, such as Emilie Mitchell, arrived at the answer without resorting to such casework. Such alternate approaches came in especially as the size of the braille cell increased and the potential number of characters grew—and it just so happened that’s what last week’s Extra Credit was all about!

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Emilie Mitchell 🎻, from Nashville, Tennessee. For the Extra Credit, I received 29 timely submissions, 24 of which were correct. As it turned out, both of last week’s puzzles rounded up to an 83 percent solve rate. Interesting…

For Extra Credit, we quadrupled the challenge by doubling the size of the cell in each dimension. That meant you had a six-by-four array, where a raised dot could appear at each location in the array. Of the 2²⁴ total potential characters, how many were in the largest set such that no two characters were translations of each other?

Whittling down from 64—as in last week’s Fiddler—was one thing. But whittling down from 2²⁴, or 16,777,216, would have been downright painful. It was time for a different approach.

Indeed, as I said earlier, Emilie (this week’s winner) had one such approach. For each “equivalence class” of arrangements (i.e., a group of arrangements that could all be translated into one another), Emilie counted only the arrangement that was translated up and to the left as much as possible. Among these—aside from the one arrangement with zero raised dots—there had to be at least one raised dot in the top row and there had to be at least one raised dot in the leftmost column. (Otherwise, the arrangement could have been further translated up or to the left.)

One way this was possible was for the top-left corner dot to be raised, since it was in both the top row and the leftmost column. When this dot was raised, the remaining 23 dots in the grid could have been raised or unraised, meaning there were 2²³ or 8,388,608 distinct characters. 

When that corner dot was unraised, at least one of the remaining three dots in the top row had to be raised, and there were 2³−1, or 7, such ways could happen. Similarly, at least one of the remaining five dots in the leftmost column had to be raised, and there were 2⁵−1, or 31, such ways. Putting these together, there were 7·31, or 217, distinct ways to have raised dots along the top row and leftmost column (again, with an unraised top-left corner). For each of these 217 ways, there was still the three-by-five grid in the bottom right of the cell that could have had any set of raised or unraised dots. That meant there were 217·2¹⁵, or 7,110,656 distinct arrangements that were crammed into the top-left of the cell but with an unraised top-left corner.

Putting these two cases together, the total number of equivalence classes was 8,388,608 + 7,110,656 + 1 (if we include the empty cell), or 15,499,265. And yes, I also accepted 15,499,264 as a correct answer.

With this solution in hand, it was no surprise that a few solvers, including Laurent Lessard and Joe Kelley, attempted to find a general solution for a grid of m rows by n columns. Applying Emilie’s methodology to the general case, when the top-left dot was raised, there were 2^mn−1 equivalence classes. When it was unraised, there were (2^m−1−1)(2ⁿ⁻¹−1) distinct ways to raise at least one dot in both the top row and leftmost column, and then 2^{(m−1)(n−1)} ways to raise or unraise the remaining dots in the m−1 by n−1 rectangle in the bottom right. That meant there were 2^{(m−1)(n−1)}(2^m−1−1)(2ⁿ⁻¹−1) equivalence classes without a raised dot in the top left.

Once again, putting these two cases together, there were 2^mn−1 + 2^{(m−1)(n−1)}(2^m−1−1)(2ⁿ⁻¹−1) total equivalence classes—plus one more, if you counted the empty cell.

We can double-check this formula by plugging in the m = 3 and n = 2, the dimensions from last week’s Fiddler. Sure enough, the result was 44 (or 45, should you have chosen to add 1).

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.