In the 1950s, a Scottish mathematician named C. Dudley Langford looked at a stack of six blocks his young son had assembled (see Endnote #1) and noticed something interesting that would lead him to the mathematical discovery he’s remembered for today.
Langford noticed that between the two red blocks was one block, between the two blue blocks were two blocks, and between the two yellow blocks were three blocks. Being a mathematician, Langford immediately wondered “Could we do this with more than three colors?”
Can you figure out how to add two green blocks and arrange the eight blocks so that there will be one block between the red blocks, two blocks between the blue blocks, three blocks between the yellow blocks, and four blocks between the green blocks?
And, having succeeded with four colors, can you do it with five?
Langford’s problem is, for which positive integers n is it possible to take 2n colored blocks, with two blocks of each color, and stack them so that for all k between 1 and n there are exactly k blocks between the two blocks of color #k?
Or, if you prefer, for which positive integers n is it possible to write down a sequence of numbers consisting of two 1’s, two 2’s, …, and two n‘s, so that for all k between 1 and n there are exactly k numbers between the two k‘s? Such a sequence is called a Langford sequence.
I already showed you how to do build the stack of blocks for n=3 (corresponding to the Langford sequence 312132), and if you look at Endnote #2 you’ll see one way to do it for n=4. But no matter how you try, you won’t be able to do it for n=5. That is, there are Langford sequences of order 3 and 4 but there isn’t one of order 5.
WHY NOT?
Let’s assume for argument’s sake that there were a Langford sequence of order 5. Let a and b be the positions of the 1s, c and d the positions of the 2s, e and f the positions of the 3s, g and h the positions of the 4s, and i and j the positions of the 5s; for instance, if our Langford sequence of order 5 began 1 2 1 3 2 … we’d have a=1 and b=3 (since the 1s are in the 1st and 3rd positions), c=2 and d=5 (since the 2s are in the 2nd and 5th positions), etc.
We don’t know the values of a and b, but we know that they must differ by 2 (because the two 1s have a single number between them), so a and b are either both even or both odd; either way, the sum a+b is even.
In a similar way, we know that c and d differ by three, which means that one is odd and one is even, so that the sum c+d is odd. And for the same reason we know that e+f is even and g+h is odd and i+j is even.
Now this tells us that (a+b)+(c+d)+(e+f)+(g+h)+(i+j) is of the form even plus odd plus even plus odd plus even, which must be an even number (see Endnote #3). On the other hand, the ten numbers a, b, c, d, e, f, g, h, i, j are just the ten numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 in some scrambled order, and you can readily check that 1+2+3+4+5+6+7+8+9+10 is 55. So if you believe that a Langford sequence of order 5 exists, you must believe that 55 is an even number. But you don’t really believe 55 is even, do you? So you must admit that there isn’t a Langford sequence of order 5 after all.
GOTCHAS
Now, if you haven’t seen proof by contradiction before, this argument might seem suspiciously close to circular reasoning, where I “prove” a conclusion by sneakily assuming it at the beginning. But the circle here is actually more akin to the circle formed a snake devouring its own tail, for here what we assume is the negation of what we’re trying to prove, and we show that the assumption contains the seeds of its own destruction.
A different sort of objection is that the proof, although logically impeccable, is socially obnoxious. Imagine, for comparison, that you and I are discussing some moral issue that we disagree about, and I say “Let’s assume for argument’s sake that you’re right,” only to force-march you to some horrible consequence you don’t subscribe to (“… so, clearly you must believe killing babies is a GOOD thing!!”). My earlier show of open-mindedness is revealed to have been a sham all along, just a sneaky, troll-ish way of setting you up for a “Gotcha!” moment.
What renders proof by contradiction inoffensive in comparison with the aforementioned trolling behavior is that in math we are trolling ourselves. And, far from being shaming, the “Gotcha!” is often exonerating. The reason I can’t construct a Langford sequence of order 5 isn’t that I’m not clever enough — it’s that it can’t be done.
A third objection is “Wait, that’s not math; that’s just a trick!” I can imagine this objection being voiced by someone whose only experience of math is the dreariest kind of school math, such as endless drills of long division. To such an unfortunate student, math is all about method (“When you encounter thus-and-such a problem, here is what you do”), and it strikes the student as deeply unfair to present them with a problem without first teaching them how to solve problems of that type. Furthermore, the gimmicky numbering seems to descend from the sky like a deus ex machina, and after it’s done its work it disappears again to wherever it came from.
There’s a mathematical aphorism that a method is just a trick that works more than one time (though some versions of the motto use a higher cutoff than one). In the rest of this essay, I’ll show two more examples of the trick you just saw, and hopefully I’ll convince you that it contains the seeds of a method.
DE BRUIJN’S PUZZLE
Can you arrange nine 1-by-4 rectangles (which you are also allowed to rotate to become 4-by-1 rectangles) to tile a 6-by-6 square? Here, I’ll get you started by placing two of the nine rectangles:
Certainly it seems plausible that the nine rectangles can be arranged to cover the square, since the total area of nine 1-by-4 rectangles is 36, which is also the area of a 6-by-6 square. But no matter how you try to arrange the nine rectangles, there’ll always be at least one rectangle that sticks out beyond the confines of the big square, as well as some parts of the square that aren’t covered by any rectangle. Try it! But don’t spend too long trying, and don’t be hard on yourself for failing. It’s not that you’re not clever enough; it simply can’t be done.
But how do we prove that your failure wasn’t due to lack of cleverness? It takes a bit of cleverness to prove that! But if you’ve seen how we dealt with Langford sequences of order 5, the cleverness won’t come totally out of the blue. Let’s put numbers in the 1-by-1 squares that make up our 6-by-6 rectangle in diagonal stripes, like so:
I claim that if you place a 1-by-4 rectangle (pointing either horizontally or vertically) so that it covers four 1-by-1 squares, then the numbers in those squares add up to an even number that is not divisible by 4. (Such numbers are, or used to be, called “oddly even”: they’re even numbers, but when you divide them by two you get an odd number. They are precisely the numbers that leave a remainder of 2 when you divide them by 4.)
Check it out: if you put a 1-by-4 rectangle anywhere on the square, add the numbers that it covers, and divide by 4, the remainder will be 2. (In the picture, we have 4+5+6+7=22 and 8+9+10+11=38, both of which are oddly even.)
You don’t have to exhausitvely try all the possible positions of the rectangle to see why my claim is true. Notice that when you slide a rectangle one square to the right or one square downward, all four numbers covered by the rectangle increase by 1, so that the sum increases by 4, which means that if the old sum was oddly even, the new sum must be oddly even too. So, in the case of a horizontal rectangle, it’s enough to verify that 1+2+3+4 (the sum of the numbers covered by a 1-by-4 rectangle in the upper left corner of the square) is oddly even. The same argument works for a vertical rectangle. So I’ve shown that no matter where you put the small rectangle, the sum of the four numbers it covers will be oddly even.
How does this help us? Well, let’s assume for argument’s sake that we can tile the big square with nine small rectangles. Each of the small rectangles covers numbers whose sum is oddly even, so if we take the grand total of all the covered numbers, we get a sum of nine oddly even numbers. And that sum must again be an oddly even number (see Endnote #4).
You’re probably guessing the form that the “Gotcha!” will take: I’m about to claim that if we add up the 36 numbers in the square, we get a total that isn’t oddly even. You’re right about that. But being lazy, I don’t want to add up those 36 numbers. Yet I still want a way to convince you that their sum isn’t oddly even.
In fact, I’m going to convince you that the sum is “evenly even”, i.e., a multiple of four). And I’ll prove this using a different way to tile a 6×6 square, namely, using nine 2×2 blocks.
Each 2×2 block contains (for some i) the numbers i–1, i, i, and i+1, whose sum is 4i, which is a multiple of 4. Since each block-sum is a multiple of 4 the sum of the nine block-sums will also be a multiple of 4.
So, having used the purported tiling of the 6×6 square by nine 1×4 rectangles to show that the sum of the thirty-six numbers leaves remainder 2 when you divide it by 4, and having used the tiling of the 6×6 square by nine 2×2 squares to show that the sum of the thirty-six numbers leaves remainder 0 when you divide it by 4, you’re faced with a choice: Do you want to believe in the first tiling or the second? Since the first tiling is something you haven’t been able to construct, and the second tiling is something I actually showed you, I’m pretty sure what choice you’ll make.
ANOTHER TILING PUZZLE
The following puzzle is one I devised; it’s a birthday present to my friend Michael Larsen (see Endnote #5).
Here’s a region called an Aztec diamond of order 3:
Michael and I (along with Noam Elkies and Greg Kuperberg) counted the ways to tile an Aztec diamond of order n with 1-by-2 rectangles, and if you want to know more about that, you can read my earlier essay “My life with Aztec diamonds” or watch a nice Mathologer video (see the References). But domino tilings are so twentieth century; let’s try something new.
Here’s a way to tile the Aztec diamond of order 3 using 1-by-4 rectangles and other tiles that look something like the letter S or the letter Z.
Solomon Golomb dubbed tiles made of four 1×1 cells tetrominos. I’ll call 1-by-4 rectangles (in either orientation) straight tetrominos, and S- and Z-shaped tetrominos (in any orientation) skew tetrominos.
We can tile the Aztec diamond of order 4 with straight tetrominos and skew tetrominos:
But what about the Aztec diamond of order 5?
It has area 60, and each tetromino has area 4, so there could conceivably be a way to use 15 straight or skew tetrominos to tile the Aztec diamond of order 5. Yet no matter how you try, you’ll fail.
Do you think you were insufficiently clever to find the tiling? Or do you think there’s a trick that shows that nobody, no matter how clever, could succeed where you failed?
My next picture probably won’t surprise you:
I claim that no matter how you place a straight tetromino on this board, you’ll cover four consecutive integers. Also, no matter how you place a skew tetromino on this board, you’ll either cover four consecutive integers or you’ll cover two consecutive integers with each occurring twice (such as 1+1+2+2 or 2+2+3+3). In either case, the sum will be an oddly even number.
What about the sum of all 60 numbers? You can’t dissect an Aztec diamond into 2×2 squares as we did in solving De Bruijn’s puzzle. Are we going to have to hunker down and add up those 60 numbers? Fortunately, there is once again a nice way to divide the grid-cells up to into foursomes, but this time the cells in a foursome won’t form a contiguous block. Cut the Aztec diamond into quadrants and imagine mirrors along the boundaries, so that each grid cell in the northeast quadrant has mirror images in the other three quadrants. (For instance, the boldface 5 is mirrored by the boldface 2, 7, and 10.)
I claim that any grid cell in the northeast quadrant (call it the primary cell) and its three mirror images cover numbers that add up to a multiple of four. To see this, start the primary cell at the lower left corner of the northeast quadrant. Then the primary cell and its mirror images form a 2×2 block, and we already saw that the numbers in such a block add up to a multiple of four.
Now imagine taking that grid cell in the northeast quadrant and sliding it one step east, with its three mirror images sliding too.
Two of the cells slide east and two slide west, so two of the numbers increase by 1 while the other two decrease by 1, with a net change of zero. The same invariance is observed if you take primary cell and slide it one step north, or if you apply multiple sliding moves.
So, dividing the Aztec diamond into foursomes of cells related by mirror symmetry, we get foursomes whose associated numbers add up to a multiple of four. Adding all 15 such sums, we find the sum of all the numbers must also be a multiple of four.
But we saw earlier that if there is a way to tile the Aztec diamond of order 5 with straight and skew tetrominos, then the sum of the numbers is not a multiple of four. So there’s no way to tile the Aztec diamond of order 5 with straight and skew tetrominos.
CAN WE GENERALIZE?
I still haven’t told you the answer to Langford’s problem, which asks: for which positive integers n is it possible to take 2n colored blocks, with two blocks of each color, so that for all k between 1 and n there are exactly k blocks between the two blocks of color #k?
You can easily convince yourself that there’s no such structure when n=1 or n=2; we saw that such structures do exist when n=3 or n=4; and we reasoned that they don’t exist when n=5. Using the same reasoning (but with algebra instead of arithmetic) you can show that if n leaves remainder 1 or 2 when you divide it by 4, then there is no Langford sequence of order n. This leaves open the question of values of n that leave remainder 3 or remainder 0 when you divide n by 4. It was shown by Davies that in those cases, you can always construct a Langford sequence of order n.
A similar situation prevails for the Aztec diamond tiling problem. If n leaves remainder 1 or 2 when you divide it by four, then the argument I gave shows that the tiling is impossible; and it’s fairly easy to show that when the remainder is 3 or 0, then a tiling of the desired kind exists. Below I show a tiling for n=11 that fills the bill. (Actually, it shows only the top half of diamond; to get the bottom half, flip the picture.) By adding two extra rows, each consisting of six straight tetrominos, you get a tiling for n=12. It’s not hard to continue the pattern for n=15, 16, 19, 20, etc.
What about generalizing De Bruijn’s puzzle? Here the answer is that an m-by-n rectangle can be tiled with 1-by-4 (and 4-by-1) rectangles if and only if at least one of the two numbers m,n is a multiple of 4. This was first proved by De Bruijn himself. Golomb’s book “Polyominos” is one place you can turn to for Golomb’s proof. But with the trick I’ve taught you, you should be able to prove it for yourself.
Golomb turned polyominos into a board game (featured in the movie “2001: A Space Odyssey”), but the success of the game was eclipsed by the Tetris craze. I’ve sometimes wondered whether Golomb ever regretted failing to invent Tetris.
THE LONG-DELAYED GATHERING
I could have learned about Langford’s problem from Martin Gardner’s famous “Mathematical Games” column in Scientific American, but I didn’t (I was only seven at the time and not yet hooked on his column); instead, I learned about it last week at a gathering held in Atlanta, Georgia in honor of Gardner, although I wasn’t there. These gatherings, usually held every two years or so, have been going on since 1993, and the fourteenth Gathering for Gardner was scheduled to take place in the Spring of 2020 when the coronavirus pandemic led to its postponement (see Endnote #6). It was postponed several times and finally held in hybrid format earlier this month. Speaker John Miller gave a six-minute talk about the Langford problem. In the references I give a link to Miller’s essay on Langford’s problem (as well as a reference to Gardner’s original article mentioning the Langford problem).
There were dozens of stimulating talks at the fourteenth Gathering for Gardner, aka G4G14, and I could write an essay about many of them. I singled out Miller’s because it ties in with a general theme that interests me: the difference between tricks and methods.
Come to think of it, the idea of tricks in math ties in with one of Gardner’s other main interests: magic. One difference between a magic trick and a math trick is that when a magic trick is explained, some of the wonder goes away; there’s a feeling of disenchantment. Consequently, magicians are reluctant to explain their tricks. In contrast, we mathematicians are only too happy to explain our tricks, which provide both surprise and enlightenment. If you’re a fan of this kind of trick, Gardner’s books “Aha! Gotcha” and “Aha! Insight” are likely to please you.
The art of solving hard math problems is in part a matter of learning lots of tricks. A really good problem doesn’t come with a roadmap guiding you to a solution; you have to find your own path. But that doesn’t mean you have to be clever. It can be enough to have a good memory, so that you can say “Hey, this problem reminds me of problem X; I couldn’t solve problem X, but someone showed me a clever solution using method Y, so maybe method Y will work with this new problem!”
I don’t know an all-purpose method for solving math problems, but here’s the closest thing I know. To turn yourself into the kind of person who solves math problems, tackle as many problems as you can and learn all the different tricks that other people have come up with. Then, when you’re faced with a new problem, you’ll be able to think of three or four problems with a similar feel, and your experience with those problems will dictate three or four different approaches to solving the problem before you.
Once in a great while (once in a career, maybe) you may stumble upon a trick that nobody’s thought of before. And who knows? Every method was once a trick; maybe someday your trick will grow up to become a method.
ENDNOTES
#1: The Langford story belongs to a genre that I love: the math-parent story. I told one such story in the first year of my blog (“Lessons of a square-wheeled trike”) and more recently I’ve told two more in which I play the role of the parent (“The paintball party and the habit of symmetry” and “Here there be dragons”); if you know of others, from mathematical history or your own life, please post details in the Comments!
#2: One sequence that does the job is 41312432.
#3: If it helps, imagine we have five piles of cookies whose sizes are even, odd, even, odd, and even, respectively, and we want to share the cookies fairly between two children. We can divide the first, third, and fifth piles neatly in two, but when we try to do it for the second pile there’s one cookie left over, and likewise for the fourth pile. What to do? Take those two left-over cookies and give one to each of the children. There are no cookies left over, and each child has received equally many, so the total number of cookies was even.
#4: Again, think about cookies, but this time we’re dividing them among four kids. Each of the nine piles leaves a remainder of 2 when we divide it by 4. This leaves 9 times 2, or 18, leftover cookies. When we try to divide the 18 cookies four ways, there will be 2 left over.
#5: My present to Michael consisted of not just a single puzzle, but a whole bunch of questions inspired by our past work, most of which I don’t know the answer to. Just as Samuel Butler quipped that a chicken is an egg’s way of making another egg, sometimes a theorem is a problem’s way of making new problems.
#6: I’d originally planned to attend in person; indeed, my essay “What Proof is Best?”, which prominently features the number 14, was an expanded version of the talk I’d planned to give. Ultimately I decided to attend the fourteenth Gathering for Gardner remotely rather than in person.
REFERENCES
R. O. Davies, “On Langford’s Problem. II.” Math. Gaz. 43, 253–255 (1959).
Martin Gardner, “Aha! Gotcha” (1982).
Martin Gardner, “Aha! Insight” (1978).
Martin Gardner, “Mathematical Magic Show”, chapter 5, problem 6.
Solomon Golomb, “Polyominoes” (1965).
Mathologer, “Why do physicists play with dominos?” (video)
John Miller, “Langford’s Problem, Remixed”
James Propp, Some 2-adic conjectures concerning polyomino tilings of Aztec diamonds, https://arxiv.org/abs/2204.00158
mathenchant.wordpress.com 