Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
Lately, I've been reading Kurt Gödel's biography by John Dawson. The book is lucid and informative. Like every absorbing reading, it overflows one's expectations. Gödel earned his Ph.D. in early 1930. Three important results were established in his dissertation: the completeness of the first-order calculus, the independence of the axioms he employed, and a compactness theorem that derived satisfiability of a countable set of first-order formulas from that of its every finite subset. None of this was enough to qualify him for gainful employment in the academic field. For this, among other requirements, he had to write another major paper.
Being extremely confident in his mathematical ability, Gödel chose to tackle the second Hilbert problem of proving the consistency of the axioms of arithmetic a positive claim. By his own account, he set out to advance Hilbert's program. But the result he found towards the fall of 1930 that is now known as Gödel's first incompleteness theorem, was profoundly negative: there exist arithmetic statements that are formally undecidable, the statements that neither can be proven nor disproved in arithmetic. (Later, he also showed that the consistency of arithmetic can be formulated in arithmetic terms and therefore provides an example of such an undecidable statement. This is known as Gödel's second incompleteness theorem.)
Gödel presented his results at the Conference on Epistemology of the Exact Sciences on September 6, 1930. It appears that, except for John von Neumann, no one present (R. Carnap, H. Hahn, H. Reichenbach among others) grasped the significance of Gödel's talk. For the reader's benefit, Dawson gives a very clear exposition of Gödel's discoveries. By late November, von Neumann obtained an unprovability result of his own, only to find out that he was anticipated by Gödel by a few days. On several occasions thereafter, von Neumann lectured on Gödel's results rather than on his own. The story is most fascinating, as are many others in the book. If you want to learn more, you should probably do your own reading. Right now, I am concerned with a small detail to which the reader is treated at the beginning of the book.
Throughout his primary school career Gödel received the highest marks on all his subjects. The extent of drill work in arithmetic at his time can be gauged from a page from his first arithmetic workbook. A concept shines through that subtraction reverses the result of addition, but the exercise itself is pure rote memorization by repetition and would be frowned upon by most present day math educators. Nonetheless, I think the page might make a good poster for a mathematics class.
First, Kurt Gödel performed the exercise as a 6-7 year old child. At this age, kids love repetition, which for them is very much a conceptual activity. I believe it just can't be helped. Repetition and practice constitute an integral and necessary part of the learning process. Gödel did it...
Second, the poster may serve as a backdrop for introductory philosophical remarks about mathematics. Gödel has proven that not everything in mathematics is provable. By implication, one first conceives an idea, then proves it if at all possible.
Third, it's OK to be mistaken. It's good to keep one's mind open while pursuing an idea. Who knows? The idea may metamorphose into its opposite as the result of one's efforts.
But let's return to repetition and practice. Are there repetitive activities that go beyond ("mindless" would be the usual adjective) memorization? Why, there's a great deal of them, of course. Repetition is a life line of computational mathematics. Iterative processes serve as one example.
Given a number and a set of rules to be performed that result in another number. Apply the rules to the new number and get a third one, and so on. Iterations may apply to a group of numbers or other mathematical objects. See, for example, the Candy game and Integer Iterations on a Circle. Following are three additional examples.
Start with a number and count the number E of even and the number O of
odd digits [Ecker]. Write them down next to each other
followed by their sum
(In the applet below and other applets on this page, most of the numbers are clickable so that you can change their values. The starting number may be looked at as a string of individual digits or as a long number depending on whether the Autonomous digits button is checked or unchecked.)
The proof that the iterations always settle on the magic number 123 is
simple but not exciting. Let's denote the above prescription applied to
number n as f(n). If n has four digits, f(n) has three and may be only one
of 044, 404, 134, 314, 224. If n has 5 digits, then f(n) still has 3 of
them. The first time f(n) may have 4 digits is for n with at least 10
digits. This is also when f(n) may get 5 digits. The possibility of a 6
digit f(n) arises for numbers with at least 20 digits. Without formalizing
the argument, it is clear that
With the exception of bases 2, 3, and 4, the iterations always settle on
number 123. In base 4, I could only find two terminating points: 1310
We get more work intensive (but this is not the main point of
course) iterations by summing up powers of digits [Ecker, Barbeau, p. 121]. In the
decimal system, squaring of digits may only result in cycles. Raising
digits to the third power and adding up leads to one of 5 points: 1, 153,
370, 371, 407. Modulo 3 those numbers are 1, 0, 1, 2, 2. All whole numbers
divisible by 3 eventually settle on 153. Function f in this case has the
property that it preserves the value modulo 3. For example, all iterates of
a number equal 2 modulo 3 are equal 2 modulo 3. Far as I can judge, such
numbers settle on either 371 or 407. On the other hand, there are cycles of
numbers equal to
calls such points that terminate iterations black holes. They
necessarily are fixed
points of the corresponding function. The function f that is the
sum of squares of the digits of a given number does not have a fixed point
in base 10. In other bases, it may. For example, in base 3,
All of the above iterative processes pose some problems. For example,
which of the known fixed points are attractive
and which are repelling,
or whether it is possible (with the sum of the third powers) to
differentiate between starting points that converge to 371 from those that
converge to 407? I do not know how difficult those problems might be. But
there is one curious problem that has been around from the 1930s that even
Paul Erdös (1982) has judged as being too difficult for the present
state of mathematics. It still is. The problem was proposed [Gardner, p. 203] by Lothar Collatz and is known as the
Collatz Conjecture, but also as the
Define f(n) = n/2 if n is even, and f(n) = 3n + 1, if n is odd. Collatz conjecture claims that regardless of the starting point the iterations settle eventually into a 3-cycle: 4, 2, 1, 4.
As a variant, an even number may be stripped entirely of its even factors (not just divided by 2) which leads to a shorter 2-cycle 4, 1, 4. For small numbers convergence is sufficiently fast to be observed even if calculations are carried by hand. The first number that takes more than 100 iterations is 27. Then such numbers become more frequent: 27, 31, 41, 47, 55, 62, ...
Well, let's sum up. Unlike first-order theories, the tool chest of a mathematics educator can never be complete. We should be always looking for novel ways to make practice more meaningful and less odious for students. Playful iterative processes are likely to fit the bill. Of the three discussed above, the first and the third may be offered even in elementary school; all are certainly suitable for middle school. Each provides an opportunity for practice but also for some investigations of substance. Quite a few patterns may be grasped from experimentation, some of which can be confirmed by rigorous reasoning, but not all. Students may be surprised to learn how easy it is at times to get to the front lines of modern mathematics.
Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. He can be reached at email@example.com
Copyright © 1996-2001 Alexander Bogomolny