Tag Archives: proofs without words

Tiling a Chessboard with Dominoes (Opposite Colors Removed)

Posted on by

This is a natural follow-up to our first gallery entry on the impossibility of tiling certain chessboards with dominoes.

Problem: Suppose we remove two squares from a chessboard which have opposite color. Is it possible to tile the remaining squares with 2-by-1 dominoes?

Solution:

From Honsberger's Mathematical Gems I.

Notice that if we remove two squares of opposite color, then there is only one way to place dominoes on the remaining squares according to this scheme (one cannot tile a domino across the “walls”). Removing two squares of opposite color ensures there is an even number of squares between the removed squares, and so the dominoes will fit as desired. In other words, the two “paths” from A to B, starting on any side of A, contain an even number of squares, and so placing a domino every two squares will fill the path with a good tiling.

Not only does this method provide a positive answer to the solution, it gives a constructive answer. If we had some odd desire to do so, we could write an algorithm which tiles any chessboard where two squares are removed, (moreover, it would run in linear time). It’s not obvious at first whether such an algorithm exists, as the average human attempt to tile a board with two random squares removed would likely require some backtracking. In other words, human solutions would generally be heuristic in nature, but this analysis gives a solution that any person could utilize.

N Choose 2 is the Sum of the First N-1 Integers

Posted on by

Problem: Determine an arithmetic expression for $ \binom{n}{2}$.

Solution: The following picture describes a bijection between the set of yellow dots and the set of pairs of purple dots:

In particular, selecting any yellow dots and travelling downward along diagonals gives a unique pair of blue dots. Conversely, picking any pair of blue dots gives a unique yellow dot which is the meeting point (the “peak”) of the inward diagonals. If we say the bottom row has $ n$ elements, then the number of yellow dots is clearly $ 1 + 2 + \dots + (n-1)$, and the number of pairs in the last row is just $ \binom{n}{2}$.

This proof is typical of the most elegant combinatorial proofs: come up with a bijection between one set of objects whose size is unknown and another set of objects whose size is easy to determine. Such a method of proof is ubiquitous in elementary combinatorics, and it extends even further to determine things about infinite sets. In higher mathematics, bijections are quite frequently used (along with other structure-preserving conditions) to determine when two things should be deemed equivalent. This concept is called isomorphism, and much of mathematics is devoted to classifying all objects in a category up to an appropriate notion of isomorphism. One particularly long instance of this is the classification of finite simple groups, but one which is easier to understand, and studied extensively by mathematicians since time immemorial, is the classification of Euclidean isometries (see here for the case of $ \mathbb{R}^2$).

Möbius Transformations are Isometries of a Sphere

Posted on by

We present a video on Möbius transformations and the geometry of the sphere. Anyone who has taken or will take complex analysis (that means you engineers!) should watch this. It shows not only the beautiful correspondence between the two, but it reveals the intuition behind a lot of complex analysis, when more often than not a student is left in the dust of rigorous formulas.

In short, this is a proof without words that the Möbius transformations are in correspondence with rigid motions of the unit sphere in $ \mathbb{R}^3$. This 1-1 mapping is precisely Riemann’s stereographic projection. While we usually might see this in one context (showing $ \mathbb{R}^2$ is the one-point compactification of the plane), it is not often connected to all of our interesting transformations in such a picturesque way.

Möbius transformations lay the foundation for much of hyperbolic geometry and other advanced topics in complex analysis. They’re quite fascinating.

False Proof – 31.5 = 32.5

Posted on by

Problem: Show 31.5 = 32.5.

“Solution”:

Explanation: It appears that by shifting around the pieces of one triangle, we have constructed a second figure which covers less area! Since the first triangle has base length 13 and height 5, its area is 32.5. Clearly, the second figure has the same area minus a square of area 1, giving the second figure area 31.5.

In fact, by counting up the squares in each component, we do see that it is simply a shifting of pieces, so the areas of the two figures must be the same. Therefore, the fault lies in our first assumption: that the first figure is actually a triangle. Looking more closely, we see that the slope of the hypotenuse of the red component is $ 3/8$, while the blue triangle as slope $ 2/5$. If the first figure were a triangle, then the slope of the hypotenuse would be uniform. Since $ 2/5 \neq 3/8$, the first figure is not a triangle, and hence its area is not 32.5. In fact, counting up the area of each component, the areas of both figures are actually 32.

This false proof accentuates the need to question one’s intuition. In fact, nothing false was said by the picture alone. The two figures do truly have the same area. The falsity is entirely in the viewer’s interpretation of what the picture says (and the questionably moral intent of a trickster mathematician). So the lesson is: while intuition can be a useful and essential guide, it is often not rigorous enough to be proof, and it can create very dangerous false positives.