# Cut The Knot!

An interactive column using Java applets
by Alex Bogomolny

# From Lewis Carroll to Archimedes

September 1999

On March 29, 1879, Vanity Fair began offering its subscribers a new weekly puzzle invented by Lewis Carroll. In his own words [Carroll, pp 1275-6]:

The rules of the Puzzle are simple enough. Two words are proposed, of the same length; and the puzzle consists in linking these together by interposing other words, each of which shall differ from the next word in one letter only. That is to say, one letter may be changed in one of the given words, then one letter in the word so obtained, and so on, till we arrive at the other given word.

Later in the letter, Carroll mentions that he "was told there is an American game involving a similar principle. I have never seen it ..." Whatever the truth, the game's origins faded into obscurity and the game itself long since became part of the multilingual folklore. It recently took a mathematical turn, under the name of the Ship-Dock Theorem. The name originates with a particular puzzle, that of getting from SHIP to DOCK. Here's a couple of solutions: SHIP, SLIP, SLOP, SLOT, SOOT, LOOT, LOOK, LOCK, DOCK [Stewart, p 41], and a shorter one SHIP, SHOP, CHOP, COOP, COOK, COCK, DOCK [Gale, pp 11-112].

### Ship-Dock Theorem

In any solution of the problem, there must be a word at least two of whose letters are vowels.

Well, as it stated, the theorem might be incorrect. For it implicitly relies on the assumption that every English word contains at least one vowel. Which is simply not true. One of the more exotic counterexamples is the word nth - of a mathematical origin - that probably managed to slip into the English vocabulary before the current epidemic of innumeracy. (As a supportive counterexample, Nathan Bowler offers the following sequence with one possible blemish to an exacting eye: SHIP, SKIP, SKIS, SKYS, SAYS, SACS, SACK, SOCK, DOCK.)

Three quarters of a century after appearance of Lewis Carroll's puzzle, on March 17, 1953 [Gazalé, p 25], Frank Gray, a research scientist at Bell Labs, filed patent no. 2632058, for the Gray code encoding vacuum tube. n-digit (binary) Gray code is a sequence of strings of n symbols "0" and "1" such that any two consecutive strings differ only in a single position. Compare this to representations of 7 (0111) and 8 (1000) in the binary positional system that differ in all 4 positions.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

The Gray codes are widely used in industry to improve fidelity of telegraphic transmission, among other things. Martin Gardner [Knotted Doughnuts] popularized application of Gray codes to puzzle solving.

Mathematicians seem to have turned puzzle solving into a gainful occupation.

Here's one puzzle. In all, there are 2n binary strings of length n. If written one after another they will produce a cancatenated string of length n2n. This string is redundant in that there are numerous repetitions. For example, using the Gray ordering for n = 2, we get the string 00011110 in which "00" appears twice while "11" appears 3 times. How short may be a string to contain, as substrings, all binary strings of length n exactly once? The absolute minimum is 2n + n - 1. And, as was shown by N. G. de Bruijn in 1946, there are 22n-1 - n such arrangements [Stein, p 149]. One particular arrangement, known as the de Bruijn cycle is presented below [Knuth, v1, exercise 2.3.4.2-23, and Knuth, v2, exercise 3.2.2-17].

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Note that there are always enough zeros at the tail of the string to identify them with all but one zero at the front. This explains the name de Bruijn cycle. Such circular arrangement contains exactly 2n digits.

This was a difficult puzzle. It required not only ingenuity, but also a lot of advanced knowledge.

Here is an easier one. In a triangle, mark 1/3 of each side counting from vertices in a certain order. Connect those points to the opposite vertices. Prove that the area of the middle triangle thus obtained is 1/7 that of the given triangle. This is a well-known puzzle with multiple solutions. One straightforward solution that makes use of Ceva's and VanObel's theorems generalizes to the case where we mark 1/N-th of each side. The illustration below draws on the knowledge derived from those two theorems.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

(Note that for N = 2, we get what may be called a proof without words for the fact that the area of the triangle (shown in red) formed by the medians of a given triangle equals 3/4 of the area of the latter. Another such pww appeared in the April's issue (1999) of Mathematics Magazine. )

Recently I ran into a puzzle [Kanga] whose relevance to the above was hard to miss. Given a triangle, extend each side by its own length in one direction following a certain order. Connect the newly obtained points. Prove that the area of the big triangle is 7 times that of the given one.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Of course, we can add 1, 2, 3, or, in general, N lengths to each side. The triangles so obtained have areas 7, 19, 37, or, in general, 3N² + 3N + 1 times greater than the given triangle. (This this #A003215 in the On-Line Encyclopedia of Integer Sequences.)

Arrange all integers in a hexagonal spiral pattern. In a moment, I'll have another chance to mention a spiral. For now, let's continue talking about numbers, the sequence 1, 7, 19, 37, ..., in particular.

This sequence can be found on the horizontal ray of integers emanating leftwards from the central 1 [Kanga]. (This should come as less of a surprise to Martin Gardner's fans. In deference to Gardner, these numbers are now called "hexes" after a discussion in Scientific American and later in Time Travel.)

Following A.R. Kanga, let's call an arrangement of numbers in a geometric pattern a number mosaic. Number mosaics often have wonderful and unexpected properties making them a worthy subject for investigation. A better known mosaic is Pascal's triangle with a multitude of already discovered and other, probably still concealed, properties. The ubiquitous multiplication table is another mosaic. Move your cursor over the applet below to see how you can obtain cubes and tetrahedral numbers as sums of highlighted entries.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

The names for cubes and tetrahedral numbers come from counting the number of dots arranged in natural 3D patterns. In two dimensions, we have a family of polygonal numbers, an object of fascination for the ancients and a curiosity nowadays.

### This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Polygonal numbers got their names from arrangements of dots in regular polygons. (If you do count the dots, note that, according to a centuries old tradition, hexes are not polygonal. Hexagonal numbers are defined by the formula N(2N - 1).)

For a given N, all regular N-gons are similar. The same is true for the circle - the figure approximated by regular N-gons as N grows without bound: all circles are similar.

Some shapes are self-similar in the sense that they are composed of smaller pieces each similar to the whole. This is true of an arbitrary triangle, Sierpinski gasket, and many other fractal sets. But the champion of self-similarity is the logarithmic spiral, first discovered by Descartes and later studied by Jacob Bernoulli who called it spira mirabilis (a wonderful spiral.)

In polar coordinates (r, θ), the logarithmic spiral is (redundantly) defined by the equation

r = Caθ,

for some constants C and a (a > 0). A turn of the spiral by angle θ0 changes the equation into

r = Caθ + θ0 = (Caθ0)·aθ,

which also represents rescaling by a factor of aθ0.

Bernoulli was so much impressed with the properties of the spiral that he requested an inscription - eadem mutata resurgo (The same but changed I shall arise) - to be engraved on his tombstone.

J.Bernoulli was not the only mathematician to be concerned with his tombstone. Archimedes, one of the three greatest mathematicians of all times, requested [Dunham, pp 103-105] his friends and relations to place over his tomb a sphere inscribed in a cylinder.

Following the Proposition 34 of his On the Sphere and the Cylinder, he placed the following corollary:

From what has been proved it follows that every cylinder whose base is the greatest circle in a sphere and whose height is equal to the diameter of the sphere is 3/2 of the sphere, and its surface together with its bases is 3/2 of the surface of the sphere.

A friend of mine, Bill Dettelback, has prepared a VRML 2.0 file depicting a cylinder with a sphere inside. Neither Archimedes, nor Lewis Carroll could have dreamed of this technology.

Etc.

### References

1. L.Carroll, Complete Works, Vintage Books, 1976.
2. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
3. W.Dunham, Journey Through Genius, Penguin Books, 1991
4. D Gale, Tracking the Automatic Ant, Springer, 1998.
5. M.Gardner, Time Travel and Other Mathematical Bewilderments, W.H.Freeman & Co., 1988.
6. M.Gardner, Knotted Doughnuts and Other Mathematical Entertainments, W.H.Freeman & Co., 1986.
7. M.J.Gazalé, Gnomon: From Pharaohs to Fractals, Princeton University Press, 1999.
8. Great Books of the Western World, v 11, Encyclopaedia Britannica, Inc., 1952.
9. A.R.Kanga, Number Mosaics, World Scientific Co., 1995.
10. D.E.Knuth, The Art of Computer Programming, v1, 2nd edition, Addison-Wesley, 1973.
11. D.E.Knuth, The Art of Computer Programming, v2, 2nd edition, Addison-Wesley, 1981.
12. S.K.Stein, Mathematics: The Man-Made Universe, 3rd edition, Dover, 1999.
13. I.Stewart, Nature's Numbers, BasicBooks, 1995.