Monthly Archives: August 2012

Konig’s lemma

This post is about trees. Not real-life ones but mathematical trees, or more formally about acyclic connected graphs. Just as actual big skinny trees are tall, graph theoretic big skinny trees are also tall. The goal here is to prove this formally.

But first some definitions. A tree is called labeled if every vertex has been assigned a symbol, called its label. A fixed vertex in a tree may be labelled as r and referred to as its root. The level i in a tree is the collection of all vertices at a fixed distance i from the root. Admittedly these definitions are informal and may be formalized in terms of directed graphs.

An example of a labelled tree is given below:

Here r is the root and the vertex sets \{a,b\} and \{1,2,3\} are at level 1 and 2 respectively. Clearly this labeling is arbitrary and any other labeling is also possible.

We now prove our result. It is due to Konig, a Hungarian professor of mathematics, who had Erdos amongst his students. It is called a lemma because it was initially used by Konig to investigate another theorem (see this) . As often happens it has turned out to be a powerful tool to use on many other problems as well.

Lemma: If T is an infinite tree and each level of T is finite then T contains an infinite path.

Proof: Suppose T is a labeled tree with root r. Let L_0=\{r\}, L_1,L_2,\cdots be the levels of T. We construct our path by starting with r. Next we partition all vertices in levels higher then L_0 (i.e. all vertices in levels L_i where i>0) into as many finite parts as is the cardinality of L_1. In other words if L_1=\{v_1,\cdots v_n\} then we partition the vertices (there are infinitely many of them) in n parts: P_1,P_2\cdots P_n. This partitioning is done as follows: Any vertex w will be connected to r via some v_i owing to connectedness. We put w in P_i.

Now since we have partitioned infinitely many vertices in finitely many parts, one of the parts will contain infinitely many vertices.(This is also called the infinite pigeonhole principle). Let that part be P_j. Choose w_1=v_j as the next vertex in our under-construction path. Next we delete the vertex r and consider the component containing w_1. It is also an infinite tree with each level finite and having w_1 as its root. By a similar piece of reasoning, we get a vertex w_2 which is adjacent to w_1 and has infinitely many vertices corresponding to it. We continue building our path by choosing w_2 as a part of it. By induction we can continue and get an infinite path rw_1w_2\cdots. This proves the theorem.\Box

It should be noted that at each of the infinitely many stages of selecting the w_i we choose it out of a finite set: the finite set of vertices at that level each of which correspond to infinite parts in the current partitioning. There is no canonical way to make this choice. To ensure that this can be done we need to use a weak form of the axiom of choice: Let X\ne\emptyset and \mathcal{F}(X) be the collection of all finite subsets of it. Then there is a function f:\mathcal{F}(X)-\emptyset\to X such that f(x)\in x\forall x\in \mathcal{F}(X)-\emptyset. A curious fact is that Konig’s lemma in turn applies this weak form of the axiom of choice and so both of them are equivalent. While their equivalence can be established using the ZF axioms, obviously neither can be proved within ZF.

Advertisements

3 Comments

Filed under Combinatorics, Graph theory

1+2+3+…(n-1)=n(n-1)/2

Each unordered pair of green balls corresponds uniquely with a blue one. So the set of pairs of green balls has the same order as the set of blue balls. Since \tbinom{5}{2} pairs are possible and the blue balls are 1+2+3+4 in number so 1+2+3+4 = \tbinom{5}{2}=5(5-1)/2

Leave a comment

Filed under Combinatorics, Miscellaneous

The van der Waerden theorem

In this post I aim to prove van der Waerden’s theorem on arithmetic progressions.

The theorem states that \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if the set \{1,2\cdots W(k,r)\} is partitioned into r classes, one of the classes is guaranteed to contain an arithmetic progression of length k.

Before proceeding further, lets look at a bit of history regarding this result. As per a recent book the theorem was conjectured independently by the mathematicians Schur and Baudet sometime around the 1920’s. (The exact dates are unknown). In 1926 van der Waerden, then a young scholar in Hamburg, heard of this conjecture (he believed it to be solely by Baudet) and proved it in the course of a remarkable discussion with his teacher Emil Artin and the mathematician Otto Schreier. The beauty of the proof was that it did not use any tools of advanced mathematics and yet was not simple by any means. Khinchin has referred to it as one of the three pearls of number theory.

Our proof here is not the same proof as originally given by van der Waerden, but a slightly slicker version based on the same idea. We start by making some preparations for the proof. For convenience we will take [n]=\{1,2\cdots n\}. Further we can very well uniquely identify a partitioning \{W_1,W_2,\cdots W_r\} of a set [W(k,r)]=\cup_{i=1}^rW_i by a function f with domain [W(k,r)] and range [r] where f^{-1}(i) equals W_i. Traditionally the numbers \{1,2\cdots r\} are called colors, every such function is called a r-coloring and the sets f^{-1}(i) are referred to as being colored i. Given a r-coloring a subset of [W(k,r)] is called monochromatic if every element in it corresponds with the same color. With these new definitions the van der Waerden theorem takes the form:

Theorem: \forall k,r\in\mathbb{N}\exists W(k,r)\in\mathbb{N} so that if [W(k,r)] is r-colored then there is a monochromatic arithmetic progression of length k.

We shall also use the notation a + [0,k)d for the arithmetic progression of length k (also abbreviated as a k-AP) given by the ordered set \{a<a+d<a+2d<\cdots a+(k-1)d\}

And now, on to the proof. As a first step towards proving the result we shall first introduce the concept of wheels. The next step will establish some technical lemmas concerning them and after that we will prove the van der Waerden theorem.

A wheel of radius k, degree n and base point or origin a is a n tuple: W= (a + [0,k) d_1,\cdots, a + [0,k)d_n) of k-AP's each of which has base point a. The AP's a + [1,k)d_i, 1 \le i \le n are called the spokes of the wheel. Assuming that all numbers under consideration have been colored a wheel is weakly polychromatic if all of it’s n spokes are monochromatic with distinct colors, and strongly polychromatic if it’s n spokes and origin are all monochromatic with distinct colors.

An example of a strongly polychromatic wheel of degree 8 and radius 5 is given below. In case of a weakly polychromatic wheel the origin, i.e. 1, can be of any of the colors of the spokes.

The 8 AP’s are:
1,2,3,4,5
1,10,19,28,37
1,4,7,10,13
1,7,13,19,25
1,6,11,16,21
1,8,15,22,29
1,5,9,13,17
1,3,5,7,9

A translation of a wheel W by a number r defined as the wheel obtained by adding a to each number in W.

We now move on to the next stage in our proof, where we shall establish some technical lemmas concerning wheels.

Lemma 1: If W= (a + [0,k) r_1,\cdots, a + [0,k)r_n) is a wheel of radius k and degree n and the k-1 translations W + r ,\cdots W+(k-1)r of W are all strongly polychromatic with the same colors, then the wheel \hat{W} = (a + [0,k)r , a + [0,k)(r_1 + r),\cdots a + [0,k)(r_n + r)) of radius k and degree n+1 is weakly polychromatic.

Proof: The integers a + (r_i + r), a + 2(r_i + r), \cdots a + (k-1)(r_i + r) respectively picked from W+r, W + 2r ,\cdots  W+(k-1)r are identical in color because the ith component of each translation is colored identically. So \forall i, 1 \le i \le n, a + [1,k)(r_i + r) is monochromatically colored and distinct from others. Similarly the AP of the base points a+r,a+2r,\cdots a+(k-1)r also has a distinct color. Thus we have a n+1 tuple of AP’s each of which is distinctly monochromatic if we ignore the base point a, or that \hat{W} is weakly polychromatic.

Two more lemmas whose proofs are obvious are:

Lemma 2: If W is a weakly polychromatic wheel of radius k, then either W is strongly polychromatic, or contains a monochromatic AP of length k.

Lemma 3: A strongly polychromatic wheel cannot have degree r where r is the total number of colors.

With the necessary machinery in our arsenal we now attack the van der Waerden theorem proper.

Proof of the van der Waerden theorem: We shall use double induction. The first (outer) induction is on k. Clearly for k = 1,2 and any r the result holds. Let us suppose that W(k-1,r) exists for all r. Now we

Claim: For any n\in\mathbb{N},\exists N=N(k-1,r,n)\in\mathbb{N} such that given any r-coloring of [N], there exists either a monochromatic AP of length k, or there exists a strongly polychromatic wheel of radius k and degree n.

To prove the claim we use (an inner) induction on n. The case n = 1 is trivial if we use the outer induction hypothesis. Suppose the result holds for n-1, that is, N_1 = N(k-1,r,n-1) exists. Now by the inner hypothesis any block of integers of length N_1 contains either a monochromatic AP of length k (in which case we are done) or a strongly polychromatic wheel of radius k and degree n-1. In the second case let N_2 = 2W(k-1, r^{N_1}) which exists by the outer hypothesis, color the first N_1N_2 integers and consider N_2 consecutive blocks of length N_1. Since there are r^{N_1} colorings of each block, by the outer hypothesis there must be an AP of k-1 identically colored blocks: B+d, B+2d,\cdots B+(k-1)d.

Now as |B| = N_1 = N(k-1,r,n-1) so inside each block, there is either a monochromatic AP of length k in it, (which proves the theorem) or a strongly polychromatic wheel of radius k and degree n-1. Ruling out the former case means that each block B + d, \cdots B +(k-1)d contains a strongly polychromatic wheel of degree n-1. Since these blocks are identical in color so we have a AP of strongly polychromatic identical wheels. In this case, by lemma 1, the AP of blocks contains a weakly polychromatic wheel W of radius k and degree n. By lemma 2, W is either strongly polychromatic or contains a monochromatic AP of length k. In either case we have proved our claim.

The proof of van der Waerden’s theorem is trivial now. Choose W(k,r) = N(k-1,r,r). Now an r-coloring of [W(k,r)] contains either a monochromatic AP of length k or a strongly polychromatic wheel of degree r. The latter case is not possible due to lemma 3.\Box

1 Comment

Filed under Combinatorics, Ramsey theory

Mathematics and brainvita

In this post, I will analyse the single player game brainvita (also known as peg solitaire). The game is described by having a board with holes having the pattern:

Initially all holes except the central one are filled with pegs. The player may jump a peg horizontally or vertically over another peg into an empty hole. The jumped peg is then removed by the player. The objective is to finish the game with just one peg left.

The aim of this post is to show that there are (at most) 5 ending board positions in brainvita. In other words, assuming the player wins, his last peg left on the board can be only among 5 fixed board positions.

The proof uses abstract algebra. Suppose that the pegs correspond to coordinates in the plane in the natural fashion described below: The central peg is at (0,0), and all others have integer coordinates as well. For convenience adjacent pegs may be taken a unit distance apart. Some coordinates are described below:

Now consider all possible ways of placing pegs on the board. There are 2^{33} of them. Many of these ways are impossible to reach in a valid game. Regardless of this fact, let W be the set of all possible ways and for a given w\in W, let C_w denote the set of all the coordinates where there is a peg in w. Now define a function f:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} by f(w)=\sum_{(m,n)\in C_w}x^{m+n} where \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} is the finite field on 4 elements. (If there are no pegs on the board we define f to be 0.)

The function f has the property that for any given way w of placing pegs on the board, if a legal move is performed to yield another way w' then f(w)=f(w'). To see this, suppose that in the way w there were pegs at (m,n) and (m+1,n) positions and the hole at the (m+2,n) position was empty. A legal move may be performed by jumping the (m,n) peg over the (m+1,n) peg to yield a way w' where the holes at (m,n) and (m+1,n) are empty and there is a peg at (m+2,n). Clearly the only change between f(w) and f(w') occurs on account of these three coordinates and f(w)-f(w')=x^{m+n}+x^{m+1+n}-x^{m+2+n}. But as x^{m+n}+x^{m+1+n}-x^{m+2+n}=x^{m+n}(1+x-x^2)=x^{m+n}.0=0 in \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} so f(w)-f(w')=0 following which f(w)=f(w'). The same holds if instead of moving a peg to the right we had moved it above, below or to the left. Moreover all this is regardless of the fact whether the way w can actually be reached by a valid sequence of moves in the game.

Now we define another function g:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} by g(w)=\sum_{(m,n)\in C_w}x^{m-n} (the no pegs way means g is 0) and by a similar piece of reasoning conclude that g also has the same property enjoyed by f. It is also easy to observe that both f and g are onto functions and so f(W)\times g(W) has 16 elements.

Next we partition the set W as follows. Any w\in W corresponds with a pair (f(w),g(w)) and so with exactly one among the 16 elements of f(W)\times g(W). In this way all the 2^{33} elements of W are partitioned in 16 parts. Further each part has the curious property that for any w in that part, any sequence of legal moves will never change the value of (f(w),g(w)) and so the resultant w' will also be in the same part. It is now obvious that among these 16 parts one and only part consists of all the w's which can actually occur in a game of brainvita. All other w's correspond to ways which can never occur in a legal game.

What is the value of (f(w),g(w)) that this one special part corresponds to? The initial board (assuming it corresponds with i\in W) is set up so that f(i)=g(i)=1. So any way w that arises during the game also has f(w)=g(w)=1. Assume now that the game has been successfully finished with a single peg at (m,n), and that this corresponds to the way w^*. We therefore have f(w^*)=g(w^*)=1. But by definition f(w^*)=x^{m+n} and g(w^*)=x^{m-n}. So we must have x^{m+n}=1. Since the multiplicative group \{1,x,x^2\} is cyclic of order 3 so as a consequence of Lagrange’s theorem we must have 3|(m+n). Similarly we have 3|(m-n). Combining these facts together we have 3 dividing both m and n. The only five coordinates which satisfy this condition are (-3,0),(0,-3),(3,0),(0,3) and (0,0). So the player has to end up at one among these 5 positions. This completes the proof.

It should be noted that we have only found an upper bound on the number of positions the final peg can end up at. However by explicitly giving a sequence of moves for each of these 5 coordinates it is possible to show that all these endings are indeed possible.

1 Comment

Filed under Algebra, Game Theory

Two one sentence proofs

Continuing in the same vein here are two one sentence proofs.

Theorem: For x,y\in\mathbb{C}, n\in\mathbb{N} we have (x+y)^n=\sum_{k=0}^{n}\tbinom{n}{k}x^ky^{n-k}.

Proof: The coefficient of x^ky^{n-k} in the left hand side of the given expression, i.e. in \underbrace{(x+y)(x+y)\cdots (x+y)}_{\text{n terms}}, is obtained by selecting exactly k parenthesis out of the total n available to yield the x's, (the remaining parenthesis yield the y's), which can be done in \tbinom{n}{k} ways following which the coefficient is exactly \tbinom{n}{k}.\Box

Theorem: \sqrt{2} is irrational.

Proof: If \sqrt{2}=m/n is in lowest terms then \sqrt{2}=(2n-m)/(m-n) is in lower terms.\Box

Remark: The above proof generalizes to the case when k is a non-square positive integer. Indeed, if j<\sqrt{k}<j+1 then assuming that \sqrt{k}=m/n is in lowest terms also implies that \sqrt{k}=(kn-jm)/(m-jn) is in lower terms.

Leave a comment

Filed under Combinatorics, Miscellaneous

A visual proof of the Pythagoras theorem

3 Comments

Filed under Geometry