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 1$ dominoes 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:

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.

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.$

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.

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

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.

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.$

Wow, we have proved earlier that $T_1\in\{B\};$ and in this case we see that $\triangle TT_1F$ is our required triangle ; 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)

3 thoughts on “Colourings”

shanku says:

November 18, 2012 at 10:05

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.

shanku says:

November 18, 2012 at 10:52

The above not only prove the existence of a right triangle but an isosceles right triangle.

- Potla says:
  
  November 18, 2012 at 21:25
  
  Nice solution, thanks a bunch for your thoughts. 🙂

The Problem Solver's Paradise

A blog for math lovers

Colourings

3 thoughts on “Colourings”

Leave a comment Cancel reply

Share this:

Related

3 thoughts on “Colourings”

Leave a comment Cancel reply