How Many Ways Can You Raise the Dots?

A collision of geometric transformations, combinatorics, and braille.

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

Braille characters 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.

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 are in the largest set such that no two characters consist of raised dot patterns that are translations of each other?

Extra Credit

In addition to six-dot braille, there’s also an eight-dot version. But what if there were even more dots?

Let’s quadruple the challenge by doubling the size of the cell in each dimension. Consider 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 are in the largest set such that no two characters are translations of each other?

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 challenge posted by Michaela Epstein, who said it came from SNAP Math Fairs, who in turn said it came from Boris Kordemsky's “The Moscow Puzzles.”

Sixteen chocolates sit in a four-by-four box. Can you remove six from the box so that an even number is left in each row and each column? Here’s an illustration, courtesy of SNAP:

Once you’ve solved it, you can further challenge yourself by counting how many different ways you can choose six chocolates to remove such that an even number is left in each row and column. Counting ways to arrange dots in a grid … now where have I seen this before?

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Austin Shapiro 🎻, from Oakland, California. I received 86 timely submissions, of which 68 were correct – good for a 79 percent solve rate. Amazing job, everyone!

Last week, you were asked to consider the functions f(n) = 2n+1 and g(n) = 4n. It was possible to produce different whole numbers by applying combinations of f and g to 0. For example, f(0) = 1, f(f(0)) = 3, g(f(0)) = 4, f(f(f(0))) = 7, f(g(f(0))) = 9, f(f(f(f(0)))) = 15, and g(g(f(0))) = 16.

How many whole numbers between 1 and 1,024 (including 1 and 1,024) could you produce by applying some combination of f’s and g’s to the number 0?

Many solvers “brute forced” their way through this, seeing how many different numbers they could generate. Some even wrote computer scripts to make this work a little less painful.

However, there was indeed a clever way to find the answer without burning through reams of paper or silicon. As noted by solver Michael Lugo, one clue was the upper limit you were asked to consider: 1,024, which was a power of 2. Instead of working in our usual base 10, let’s take a look at the effect of the functions f and g in base 2 (also known as binary).

The function f multiplied a number by 2 and added 1. In binary, multiplying by 2 appends a “0” to the end of a number (just as multiplying by 10 does in base 10). So multiplying by 2 and adding 1 appended a “1” to the end of a number. Meanwhile, the function g multiplied a number by 4. In binary, multiplying by 4 (or 2²) appended “00” to the end of a number (just as multiplying by 100, or 10², does in base 10).

And so, thinking about the functions as appending digits rather than doing arithmetic, the original puzzle became the following: How many numbers in binary from 1 to 10,000,000,000 (i.e., 2¹⁰) could you produce by starting with 1 and then either appending “1” or “00” to the end?

Suppose you could make k_N−1 such numbers that were N−1 digits in binary (or “bits”), and k_N−2 such numbers that were N−2 digits in binary. To make a number that was N digits in binary, you could append a “1” to the end of the former k_N−1 numbers or a “00” to the end of the latter k_N−2 numbers. In other words, k_N = k_N−1 + k_N−2. Adding two numbers to get the next one in the sequence? There was something very Fibonacci happening here!

Working our way up from fewer digits to more digits, we had k₁ = 1, k₂ = 1, k₃ = 2, k₄ = 3, k₅ = 5, k₆ = 8, k₇ = 13, k₈ = 21, k₉ = 34, and k₁₀ = 55. Adding these all up meant there were 143 numbers you could make that were at most 10 bits long, or between 1 and 1,023 in base 10. Since it was also possible to make 1,024, the answer was 144.

Interestingly, 144 itself is also a Fibonacci number, which was no coincidence. That’s because the Fibonacci sequence exhibits the fascinating property that adding up the first N Fibonacci numbers is always one less than the N+2^nd Fibonacci number.

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Peter Ji 🎻, from Madison, Wisconsin. For the Extra Credit, I received 46 timely submissions, 32 of which were correct—good for a not-too-shabby 70 percent solve rate.

For extra credit, you again had the function g(n) = 4n, which was now accompanied by a new function, h(n) = 1−2n. How many integers between -1,024 and 1,024 (including -1,024 and 1,024) could you produce by applying some combination of g’s and h’s to the number 0?

Again, in binary, the function g had the effect of appending “00” at the end of a number. But this time around, h acted a little differently in that it didn’t reliably append any number of bits, apparently screwing up the Fibonacci approach.

First, h multiplied a number by -2, thereby appending a “0” and flipping the sign. So far, so good. But then h added 1, which could remove that newly added bit when the output was negative. For example, h(4) = -7, or, in binary, h(100₂) = -111₂. Here, both the input and the output consisted of three bits.

With this wrinkle, many solvers again turned to brute force via spreadsheets or computer code. But solvers like Laurent Lessard and Jeffrey Ling noticed that h only failed to increase the number of bits when the input was a positive power of 2 (e.g., when the input was 4, as mentioned above).

This led Jeffrey to prove a Fibonacci-like recurrence relation: y_N = y_N−1 + y_N−2 + (-1)^N−1, where y_N was the number of N-bit positive or negative integers you could generate with g and h. Starting with y₁ = 2 and y₂ = 1, Jeffrey computed the sequence up through y₁₀, added them all up, and then added two more to account for the extremes of -1,024 and 1,024. In total, there were 234 integers that could be reached.

Alas, this time around the answer was not a Fibonacci number, but rather one more than a Fibonacci number.

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.