Combining three books into a single volume, this text comprises Multicolor Problems, dealing with several of the classical map-coloring problems; Problems in the Theory of Numbers, an elementary introduction to algebraic number theory; and Random Walks, addressing basic problems in probability theory.
The book's primary aim is not so much to impart new information as to teach an active, creative attitude toward mathematics. The sole prerequisites are high-school algebra and (for Multicolor Problems) a familiarity with the methods of mathematical induction. The book is designed for the reader's active participation. The problems are carefully integrated into the text and should be solved in order. Although they are basic, they are by no means elementary. Some sequences of problems are geared toward the mastery of a new method, rather than a definitive result, and others are practice exercises, designed to introduce new concepts. Complete solutions appear at the end.
Read an Excerpt
Multicolor Problems, Problems in the Theory of Numbers, and Random Walks
By E. B. Dynkin, V. A. Uspenskii
Dover Publications, Inc.Copyright © 2006 Dover Publications, Inc.
All rights reserved.
Coloring with Two Colors
1. SIMPLE TWO-COLOR PROBLEMS
Problem 1. Let n straight lines be drawn in the plane. Prove that the map formed by them can be properly colored with two colors (Fig. 4).
Problem 2. Let n circles be drawn in the plane. Prove that the map formed by these circles can be properly colored with two colors (Fig. 5).
Definition. If a plane is partitioned into triangles in such a way that any two triangles either have no common point, or have a common vertex, or have a common side, such a partition is called a triangulation.
Definition. If at the vertices of a triangulation the digits 0, 1, and 2 are placed in such a way that the vertices at the two ends of the same side are numbered with different digits (Fig. 6), such a numbering of vertices is called proper.
Problem 3. Prove that a triangulation with proper numbering of vertices can be colored with two colors, assuming that it extends indefinitely over the plane.
Problem 4. If on a map there is a region for which the number of boundaries is not divisible by m, while the number of boundaries of each other region is divisible by m, then the map cannot be properly colored with two colors.
2. PROBLEMS ON SQUARE BOARDS
The customary coloring of the squares of a chessboard serves as an example of a proper coloring provided we disregard the region outside. The problems on the chessboard that we introduce here will help us later on to solve the general two-color problem.
A knight can, under the rules of chess, go in one move from the square S to any one of the squares S1-S8 (Fig. 8). A rook can go in one move from square S to any square in the corresponding row or column (Fig. 9). In solving problems, we agree to regard a rook going from a square S to a square S' (Fig. 9) as visiting all the intervening squares as well.
Problem 5. With a knight, make the rounds of all the squares of a "chessboard" consisting of 5 × 5 squares in such a way that the knight lands on no square twice.
Problem 6. Number the squares of a 25-square "chessboard" in the order in which the knight rested on them in the previous problem. Shade all the squares that have an even number. Show what coloring results if the same operations are carried out, not on a 25-square "chessboard," but on one with an arbitrary number of squares, which a knight can visit as indicated in Problem 5.
Problem 7. Is it possible for a knight to touch once each of the squares of a 49-square board and on the last move to come to a square neighboring the square from which he started?
Problem 8. Prove that in one circuit a knight cannot visit all the squares of a 49T square board if he starts from the square S (Fig. 10).
Problem 9. A knight has made n moves and has returned to the square from which he started. Prove that n is even.
Problem 10. Prove that a rook cannot move from corner A of a 64-square chess-board to the diagonally opposite corner B by visiting every square once and only once (Fig. 11).
3. PROBLEMS INVOLVING EVEN AND ODD NUMBERS
Problem 11. Can one arrange all 28 dominoes of a (double-six) set in a single chain so that the number 6 is at one end and the number 5 at the other?
Problem 12. Every human being who ever lived on the earth has, in the course of his life, shaken hands some completely definite number of times. Show that the number of human beings who have shaken hands an odd number of times must be even.
Problem 13. At a meeting, 225 persons were present. Friends shook hands with each other. Prove that at least one of the participants present at the meeting shook hands with an even number of people.
Problem 14. In Figure 12, six points A, B, C, D, E, F are shown, and each of these points is connected with three of the remaining five. Prove that if instead of six there are given only five points, then it is impossible to draw curves connecting them in such a way that each of the points is connected to exactly three of the remaining points.
4. NETWORKS AND MAPS
We shall now define several terms that we have been using intuitively up to now. Before doing so, let us consider an arbitrary network of curves in the plane and introduce a new term.
Definition. If from a particular point of this network one can move away along curves of the network in k different directions, then we shall say that the multiplicity of this point is k.
For example, for the network represented in Figure 13, the multiplicity of the point A is 1, the multiplicities of the points B and F are each 2, the multiplicities of the points D and E are each 3, and, finally, the multiplicity of the point C is 7.
Definition. Any point of the network whose multiplicity is different from 2 is a vertex of the network.
The network of Figure 13 has, by this definition, four vertices, A, C, D, and E.
Definition. The arc of any curve of the network between two adjacent vertices is called a boundary.
In this way, each boundary contains two vertices. (In special cases, these two vertices can coincide to become one.) In our network (Fig. 13), there are seven boundaries: ABC, ED, CaE, CbE, CcD, CdD, and CFC. In the last of these, the two vertices containing between them the boundary CFC coincide. We shall denote the number of vertices of a network by v, and the number of boundaries by b.
Problem 15. Construct a network of curves for which
(a) v = 3, b = 5;
(b) v = 7, b = 11.
Problem 16. Let a network of curves have b boundaries and v vertices with the multiplicities k1, k2, ..., kv. Prove that
k1 + k2 ··· + kv = 2b.
Problem 17. Prove that in any network of curves the number of vertices having odd multiplicities is even.
Notice that not every network of curves can be called a map.
Definition. A map is a network such that every boundary must necessarily separate two neighboring regions.
Hence, for example, there can be no vertices of multiplicity 1 on a map. In Figure 13, the boundary ABC, which goes out from the vertex A of multiplicity 1, does not separate any two regions. We shall denote the number of regions of a map by r and count the outside region along with the others.
Problem 18. Construct a map for which
(a) v = 5, b = 8, r = 5;
(b) v = 11, b = 19, r = 10;
(c) v = 6, b = 12, r = 9.
Problem 19. A map has b boundaries and r regions, which have n1, n2, ..., nr boundaries, respectively. Prove that
n1 + n2 + ··· + nr = 2b.
Problem 20. Prove that, in an arbitrary map, the number of regions having an odd number of boundaries is even.
Note. We have agreed to call vertices those points of a network of curves having a multiplicity different from 2. Sometimes, however, it is convenient to consider as vertices also certain points of multiplicity 2. As before, a boundary is a section of any curve lying between two successive vertices. For example, the map in Figure 14 has 9 vertices, A, B, C, D, E, F, G, H, I, and 11 boundaries, AB, BC, CD, DE, EG, GF, FA, BI, IH, HD, HG. It is easy to verify that the statements and solutions of all the problems formulated earlier are still valid under the new meaning of vertex.
5. GENERAL TWO-COLOR PROBLEMS
By analogy with the chessboard, we now introduce a rook on an arbitrary map. The rook goes through the various regions, being able to go in one move from any region into any neighboring one (in Fig. 15, from S to any one of Sl, S2, S3, S4, S5).
Problem 21. With a rook, make a tour of all the regions of the map represented in Figure 16 without visiting any region twice. Number the regions in the order in which the rook visited them, and shade those regions that are given an even number.
Problem 22. Prove that it is impossible for a rook to tour all the regions of the map represented in Figure 17 without visiting at least one region twice.
Problem 23. Let a map be properly colored with two colors. Prove that all of its vertices have an even multiplicity.
Problem 24. Suppose all of the vertices of a map have an even multiplicity. A rook tours a series of regions (not necessarily all) of this map, without visiting any one of them twice, and returns to the region from which it started. Prove that the rook has made an even number of moves.
Problem 25. As in Problem 24, suppose all of the vertices of a map have an even multiplicity. A rook tours a series of regions of this map and returns to the region from which it started. (This time, in the process, the rook could have visited some regions more than once.) Prove that the rook has made an even number of moves.
Problem 26. Let all vertices of a map have an even multiplicity. Let a rook go along a certain path from the region S0 to the region S1 in p moves, and along another path in q moves. Prove that the numbers p and q are either both even or both odd.
Problem 27. Let all vertices of a map have an even multiplicity, including 2. Prove that the map can be properly colored with two colors (compare with Problem 23).
Problems 23 and 27 yield the following theorem, which completely solves the problem of the proper coloring of a map with two colors:
Theorem. A map can be properly colored with two colors if and only if all of its vertices have an even multiplicity, including 2.CHAPTER 2
Coloring with Three Colors
6. A SIMPLE THREE-COLOR PROBLEM
Problem 28. Suppose n circles are drawn in a plane. In each circle let a chord be drawn so that chords of two different circles have at most one point in common. Prove that a map obtained in this way can always be properly colored with three colors. (Figure 18 is an example of such a map.)
7. PROBLEMS ON HEXAGONAL BOARDS
The hexagonal board pictured in Figure 19 has the same significance for the three-color problem that the chessboard has for the two-color problem. Unlike the ordinary chessboard, it is not composed of squares, but rather of regular hexagons, and can be properly colored with three colors, say white, black, and red (Fig. 20), provided we disregard the region outside. For such a board, we could devise rules of play analogous to those for ordinary chess. We limit ourselves to introducing a playing piece that we shall call a camel. In one move, the camel can go from a region in any of the three directions shown by arrows in Figure 19: up, down to the left, or down to the right; that is, it can go from region S to any one of the regions S1, S2, or S3. In Figure 20, the path of a camel from the bottom corner of the board to the top, and from the top to the bottom is shown.
Our hexagonal board itself has the form of a hexagon. An "edge" of this large hexagon, or a "side" of the board, may consist of any number of hexagonal regions. (In Figure 19 a side of the board consists of five hexagonal regions.)
Problem 29. Determine the number of regions in a hexagonal board whose sides have five, six, and m hexagons.
Problem 30. Draw a hexagonal board with three regions on a side. Find a path for a camel starting in the center region and visiting all the regions on the board without touching any region twice.
Problem 31. Number all of the regions on the board in the order in which the camel touched them in Problem 30. Color black all regions numbered with multiples of 3, and red all regions whose numbers give remainder 1 when divided by 3. What kind of coloring results? What coloring do we obtain when we carry out the same process on another board, with a different number of regions on a side, that can be toured with a camel as indicated in Problem 30?
Problem 32. Suppose that a camel has made n moves and has returned to the region from which it started. Show that n is divisible by 3.
Problem 33. Prove that if a camel starts out from a corner region, it cannot tour a hexagonal board with three regions on a side, visiting every region only once.
Problem 34. Is it possible for a camel to tour all the regions of a hexagonal board with m regions on a side, touching each region only once, and arrive, on the last move, in a region neighboring the region from which it started?
8. DUAL DIAGRAMS
Let us mark the center of each region of the hexagonal board shown in Figure 19 and join the centers of each pair of adjoining regions by a line segment. If we erase the edges of the hexagonal regions, leaving only the centers and the line segments that connect them, we obtain the diagram in Figure 21. Points in Figure 21 correspond to regions of the board in Figure 19. The diagram we have drawn is very convenient for solving problems involving the path of a camel. (The directions in which a camel can move are shown by arrows.)
Problem 35. Prove that it is impossible for a camel to tour all the regions of the hexagonal board in Figure 19 (or, what amounts to the same thing, all the points of the diagram in Figure 21) without visiting some region twice.
Definition. Diagrams related as are Figures 19 and 21 are dual to each other.
A system of 25 points, connected by straight lines with arrows, is shown in Figure 22. A board dual to this diagram is shown in Figure 23. This board is composed of regions of two kinds, octagons and squares. If we mark each octagon and each square at the center, join the centers of neighboring regions, and erase the boundaries of the regions, we obtain the diagram in Figure 22 again.
Problem 36. Devise a camel's tour of the diagram in Figure 22 so that no point is visited twice. Number the points of the diagram in the order in which they were touched and replace each number by its remainder when divided by 3. Color black all regions of the board in Figure 23 that correspond to points numbered 0 in Figure 22 and color red all regions corresponding to points numbered 1.
Problem 37. Prove that it is impossible for a camel to tour all of the regions of the board in Figure 23, touching each region only once, if it starts its tour in an octagonal region.
We can consider the paths of camels on diagrams considerably more general than the diagrams shown in Figures 21 and 22. We recall that by a triangulation of a polygon we mean a decomposition into triangles, any two of which have either a vertex, a side, or no point at all in common (see first definition in section 1). Let us assume that some polygon (or even the whole plane) is triangulated, and that the triangles into which it (or the plane) is partitioned are properly colored with two colors, white and black (see, for example, Figure 24). A playing piece that moves along the sides and vertices of the triangles, going in one move from any vertex to one of its neighboring vertices (that is, end points of the same side), will again be called a camel. Furthermore, the direction of motion will be such that, as the camel moves along a side, a black triangle always lies to the right and a white one to the left. In Figure 24 the possible directions of a camel's motion are indicated by arrows.
Excerpted from Mathematical Conversations by E. B. Dynkin, V. A. Uspenskii. Copyright © 2006 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
ContentsSection I: Multicolor Problems,
Chapter 1. Coloring with Two Colors,
Chapter 2. Coloring with Three Colors,
Chapter 3. The Four-Color Problem,
Chapter 4. The Five-Color Theorem,
Solutions to Problems,
Section II: Problems in the Theory of Numbers,
Chapter 1. The Arithmetic of Residue Classes,
Chapter 2. m-adic and p-adic Numbers,
Chapter 3. Applications of m-arithmetic and p-arithmetic in Number Theory,
Chapter 4. Further Remarks on the Fibonacci Sequence and Pascal's Triangle,
Chapter 5. The Equation x2 2 5y2 5 1,
Solutions to Problems,
Section III: Random Walks,
Chapter 1. Probability,
Chapter 2. Problems Concerning a Random Walk on an Infinite Line,
Chapter 3. Random Walks with Finitely Many States,
Chapter 4. Random Walks with Infinitely Many States,
Solutions to Problems,