Colourings

INTRODUCTION

As we know, many tough combinatorial problems are based on a very basic step or strategy which can simplify the problem upto a tremendous extent. One of our important strategies in proving combinatorial problems is using colourings; i.e., to use colours to paint the problem and then proving it using a semi-contradictory argument.

Before proving colouring problems we must first come to some important terms that we need to know.

1. Colourings Of Graphs
First of all, I will introduce you briefly to the colourings of graphs. Though it is not very related to problem-solving, still we need to have some basic knowledge on this.

Before that, we need to know what a graph is. I will introduce us to the idea of a graph in brief. Actually; a graph G is defined as a figure, which can be 2-Dimensional (planar) or 3-Dimensional, which must consist of a set V(G) of vertices, a set E(G) of edges. We denote e as an edge with (x,y) as endpoints; and in order for the figure to be a graph we must have a mapping from each sets of vertices to the endpoints.

An edge is called a loop whenever we have x identical with y. A graph is called simple when it has no loops, and no two edges having the same set of endpoints. Not that every polygon can be called a simple graph.We will come to graphs later again.

We say that a graph G is properly coloured if we have no edge having two endpoints of the same colour. We denote the set of colurs with C; and hence for a polygon with an odd number of sides we have |C| = 2, where |X| denotes the cardinality of X or the number of elements in X.

We denote \chi (G) = |C|_{\text{min}}, i.e. the minimum number of colours required for a proper colouring. If we denote P_n as the polygon with number of sides = n, then we have \chi \left(P_{2n + 1}\right) = 2. This \chi (G) is said to be the chromatic number of a graph G. We also have the Four Colour Theorem, which can be stated equivalently as; if G is planar we must have \ka\chi (G)\leq 4. We will discuss about this later too, but now let us come to our main focus.

2. COLOURINGS
In case of combinatorial problems, the simpler, the better. Therefore we will show why colurings are simple.

We can cover up a chessboard with 32 numbers of 2\times 1dominoes in finitely many ways. A physicist M.E. Fischer calculated this number to be 12988816\ \lor \ \left(2^4\times 901^2\right). But that is not our point of concern. We try to modify the problem a bit. If 2 diagonally opposite squares are cut off from this chessboard, then in how many ways can we do the covering with 31 \ \ \ 2\times 1 dominoes?

Though it looks tough, we can explain it with a simple combinatorial argument. Let us consider the number of black and white squares. First of all, we had 64 squares; 32 black and 32 white. If we take out two diagonally opposite squares, then let both the squares be white in colour (WLOG). In that case, we see that in our newly arranged chessboard, we have 30 white squares and 32 black squares. If we were to cover it up with 2\times 1 dominoes, it would have covered 31 white and 31 black squares. but we don’t have 31 white squares, we have only 30 of them left. Therefore the colouring is not possible. \Box

Like this, we can prove many problems by just colouring and then contradicting.

\boxed{E 1.} A 10\times 10 chessboard cannot be covered by 4\times 1 straight tetrominoes.
Solution
We colour our 10\times 10 board with O; G; B; A (Orange, green, blue, ash/grey) as follows:
Image
Here each horizontal straight tetromino covers four squares of different colours, while the vertical ones cover four squares of the same colour each. After all horizontal tetominoes have been placed, we are left with a + 10; a + 10; a; a squares of colours O; G; B; A respectively. If such a complete covering would have existed, then we must have had a; (a + 10)\equiv 0(\mod 4) which is not possible. Therefore we are done. \Box

\boxed{E 2.} A a\times b rectangle can be covered by 1\times n rectangles if and only if n|a; \lor n|b.
Solution(from A. Engel-P.S.S)
We have,if n|a \lor n|b then our covering is obvious.
So we consider the case when n\not | a; \implies n = pn + q \ (0 < q < n). Now colour the board accordingly as in our previous diagram using the colours 1,2,\cdots n. There are bp + b squares of each of the colours 1,2,\cdots q; and bp squares of each of the colours 1,2,\cdots n. The h horizontal 1\times n tiles each covering one square of each colour, after being placed, we will have (bp + b - h) squares of each of the colours 1,\cdots,q and bp - h of each of the colours r + 1,\cdots, n. Thus n must divide their difference.
\therefore n|[(bp + b - h) - (bp - h)]\implies n|b.
Note
We can also state this for the space, whereas if an a\times b\times c block can be covered with n\times 1\times 1 bricks we have n|a \lor n|b\lor n|c.

\boxed{E 3.} An art gallery is the shape of an n-gon. Find the minimum number of watchmen needed to guard the gallery.
Solution
This is known as the Art Gallery problem.
We join non-intersecting diagonals to form disjoint triangles. Now we colour the vertices of each triangle with distinct colours, so that we can make a proper colouring of each of the triangles (recall this term and prove it using induction). Now, the colour used least number of times will be our required number, which is equal to \left\lfloor \frac n3\right\rfloor.
This solution or theorem is known as Chvátal’s art gallery theorem.
For further research you can visit the wikipedia link I gave above.\Box

I will post more problems soon, I have to leave now. I am posting some Exercises and post more within 5-8 hours.

3. Exercises
1. Consider the following figure, where 14 cities are connected by roads.
Find a path passing through each city exactly once.
Note
In case of graphs, a path or walk means a proper way of starting from a vertex of a graph x_0 and walking along the edges, to reach a final point x_k is called a path. Thus a path can be written as \{x_0;e_1;x_1;e_2;\cdots; e_k; x_k\}.
A path is said to be simple if x_k \neq x_0, and a closed path if x_0 = x_k. I will come back to this topic again in future when discussing about graphs.
Image

2. Every point in the space is coloured with exactly one of the colours Red, Green, or Blue. The sets \text{R; G; B} consist of the lengths of those segments in space with both endpoints red, green, and blue respectively. Show that at least one of these sets contain all non-negative integers.

Experiment with an equilateral triangle
About a month ago, I was researching with colouring problems that are solved using the Pigeonhole principle and can be proved elegantly. However, I have only dealt with planar figures and there colourings only, so I hope to present my little (and flop) experiment that I made about a month ago.
But before that, I want you to get used to some problems on colourings that require the PHP to be proved elegantly.

The PHP states that if n + 1 balls are put into n boxed, we must have a box with more than 1 ball. This can be generalised as follows:
1. If we put kn + 1 balls into k boxes, we must have a box with more than n balls.
2. If the average of n positive numbers a_1; a_2;\cdots;a_n is a; then at least one of the numbers is greater than or equal to a. As a consequence we must have at least one of the numbers less than or equal to a.
However, our main point of concern is the first and most elementary form of PHP. In order to prove these theorems, we can assume the converse, and show that it leads to a contradiction. The proof is left to the readers.

Now, we might be given problems on colourings like:
\boxed{E1} If the plane is coloured with two colours, then there exists at least one line with its endpoints and its midpoint of the same colour.
Solution
After drawing a diagram it is obvious. Since there are infinitely many points in the plane, we can get two points of the same colour always in the plane.
Denote them by A(r); B(r) where r signifies red and b signifies blue. (say). Now let us see what its midpoint D is. If D is r, we are done. So WLOG assume D to be blue. Now, we produce the line AB to both sides at a length of AB. Now we get a new line D_1D_2. If D_1\lor D_2 = r, we are done since in both cases we get a line(r) \ D_1AB \ \lor \ D_2BA.
dot((0,0));dot((2.5,0));dot((5,0));dot((-2.5,0));dot((-5,0));label("$D(b)$", (0,0), N);label("$D_1(b)$", ...
So both of D_i are blue and we have a new segment D_1DD_2 of our required type. Hence proved. \Box

\boxed{E2} If all points of the plane are coloured red or blue, show that there exists an equilateral triangle with three vertices of the same colour.
Solution
We must have a line with its endpoints and its midpoint of the same colour, as according to E1.
dot((0,0));dot((2.5,0));dot((5,0));dot((-2.5,0));dot((-5,0));dot((0, 4.3));label("$D(b)$", (0,0), S);label("$A...
Let ADB be a line segment with A,D,B blue. Draw an equilateral triangle ABC on this, forcing C to be r in colour. Now lets take the midpoints E,F of AC, AB respectively. Then we again have forced E;F to become r (else we get \triangle EDC and \triangle FDB as the required triangles). In this case too we are forced to get \triangle CEF as our required triangle with all vertices red in colour. Hence we are done. \Box

\boxed{E3} (My inspiration to this experiment: Indian National MO 2008) If all the lattice points of the plane are coloured with three colours: b;r;g (standing for blue, red, green respectively) show that we have at least one right triangle with three vertices of different colours; given that (0,0)\in \{R\}\land (0,1)\in\{B\}.
Solution(Official solution)
Consider the lattice points on the lines y = 0 and y = 1 other than (0, 0), (0, 1). If any one of them , say A = (p, 1) is coloured green, then we have a right triangle with (0, 0), (0, 1) and A as vertices, all having different colours.
If not, then the lattice points on y = 1 and y = 0 are all red or blue. Now consider three different cases:
Case 1
Suppose the point B = (c, 0) is blue. Consider a blue point D = (p, q) in the plane. suppose p\neq 0. If it’s projection (p, 0) on the axis is red, then (p, q),(p, 0), (c, 0) are the required vertices.
If (p, 0) is blue, then we can consider the vertices (0, 0), (p, 0), (c, 0) are the vertices of the required RAT.
If p = 0 then the points D, (0, 0) , (c, 0) form the required RAT.
Case II
A point D = (c, 1) on the line y = 1 is red. The logic is similar to case I.
Case III
Suppose all the lattice points on the line y = 0 are red and all the points on the line y = 1 are blue.
Consider a green point E = (p, q) where q\neq 0, 1.
Consider an isosceles RAT EKM with \angle E = 90^{\circ} such that the hypotenuse KM is a part of the x- axis. Let EM intersect y = 1 in L . Then K is a red point and L is a blue point. Hence EKL is a desired right triangle. \Box
My Solution
Image
Image
:)
So now that we all know how I have been inspired to perform an experiment, why not lets come to the point?

Here; I thought about a small trick. The problem I thought about was to prove that:
There exists a right triangle with three vertices of the same colour, if we have the plane coloured with red and blue.
Solution
According to our above problem, there must exist an equilateral triangle with all its 3 vertices of the same colour. Refer to figure 1. Let the triangle be \triangle ABC(r) and let D be the midpoint of segment BC. But, as we see, we must have D\in\{B\}, because if D were to be red, we could have found a triangle ADB or ACD satisfying our requirements. Now join A(r) and D(b).

As in our figure, let E and F be the midpoints of AC and AB segments respectively.Consider right triangle EBC. If E would have been red, we would have done; since BE is also an altitude of equilateral \triangle ABC. So E; F\in\{B\} is forced again.
Now let us join EF; and let it intersect AD at O. If O were to be blue, we could have found \triangle DOE or \triangle DOF to fulfill our requirements. So again we see that O has to be red in colour.
Image
Now, if \angle BOC = 90^{\circ}, we would have been done. But \triangle ABC is equilateral, so why not find out about this angle? Well, we can let the triangle have equal sides of length a units, so that AO = OD = \frac 12 AD = \frac {\sqrt 3}{4}a. Also DC = \frac a2. Note that from \triangle DOC we have
\tan \measuredangle DOC = \frac {\frac a2}{\frac {\sqrt 3a}{4}} = \frac 2{\sqrt 3};
So we get \angle DOC = \tan^{ - 1}\left(\frac 2{\sqrt 3}}\right), therefore we have
\angle BOC = 2\tan^{ - 1}\left(\frac 2{\sqrt {3}}\right)\approx 98.2132\cdots ^{\circ}; which is not 90^{\circ}. :( -, how can we proceed?
No, never give up hope. We now try to walk a bit farther towards our goal. Let us consider \triangle AEF, as in Figure 2. Note that if any point on EF would have been red, we would have been done. So it is completely forced that all points on EF except O are blue in colour.
What else can we say? we want a right triangle, am I correct? So why not try to make one? Let us take a point O_1 on AO which satisfies \angle FO_1O = \angle EO_1O = 45^{\circ}; so we must have O_1\in \{R\}. How funny, now we have three points in a row that are red. But have we done yet?
The answer is unfortunately “no”. We still have a bit to go, but we can feel it that we are near to our goal.
OK, last try. Refer to Figure 3.
Draw a line O_1T parallel to FE such that T is on AE. Again we have forced T\in\{B\}. Now we can almost finish our proof if proceeded a bit more. Let us draw a right angle \angle T_1TE with T_1 on EF. We can show that such a point exists since \angle O_1PE = 120^{\circ} and due to the acuteness property we force T_1 to be in the same side of EF with respect to O_1T.
Image
Wow, we have proved earlier that T_1\in\{B\}; and in this case we see that \triangle TT_1F is our required triangle :o ; and we are done. :lol: \Box

A really nice problem that I made, isn’t it? The solution might be lengthy and not elegant, but still, it is an interesting solution, all the same.

(To be updated)

Advertisements

3 thoughts on “Colourings

  1. There is a simpler proof.
    Take 2 points A and B of the same color, say blue. Complete the square on AB.Let C and D be the other two vertices. If any one of C and D is blue we are done. Say both C and D are red.Then consider the color of the centre of the square O. Depending on its color, either of the triangles AOB or COD, which are right-triangles, will be of the same color vertices. And we are done.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s