Coloring problems are, I think, one of the most elegant ways of visualising a problem, that might otherwise be impossible or increasingly difficult to handle.
Here I present a problem, and my coloring solution that really lifted my spirits.
The problem was something like this:
On a grid, two squares are said to be neighboring if they share a common side. There are 65 bugs, each occupying a single square. At t=0, each bug moves to any of the neighboring squares of the square it was previously in. After t=0, each of the bug moves into a square that is to the right of it, or to the left of the square it is presently in. The orientation of the bug, is decided in the following way,
Suppose a bug is at the square at first, and at t=0, it decides to move into square (It could have moved to or or as well at t=0). The head of the bug is shown by the pointer at its tip. Now it is facing east and it has two options, either to move to or to , which are to the left and right of it at this moment.
( Note that the initial position of the pointer of the bug is pointed towards but then it decides to go towards the right, this is because at it's choices are totally random, so it can actually go to any of the neighboring squares.)
We need to prove that at some point of time t, there will exist a square containing more than one bug.
First we begin by noting that by the given move scheme, the bug will be on or or or square after 2 moves, So after 2 moves, the bug will have moved one place along a diagonal in any direction.
According to that scheme here is my coloring:
We set the notation by defining that the set of all squares colored red is , that consisting of orange colored squares is , and correspondingly and for those containing yellow and green colored squares.
We note that all the bugs from will migrate to after 2 moves and vice versa, and all the bugs from will migrate to after 2 moves and vice versa.
So we have by our colouring ||=25, ||=16, ||=20, ||=20. Now by Pigeon-Hole Principle we have that there are 65 bugs and 4 kinds of coloured squares they can be put in.
So there are at least bugs all of which occupy squares of the same color.
In the next two cases we are going to talk about these bugs exclusively.
If they are all initially in , then we are done, because 17 bugs in 16 squares ensures more than one bug in at least one square by the Pigeon Hole Principle.
If all of them initially in , then after 2 moves all will be in , whence we are done again, by the Pigeon Hole Principle as in Case 1.
Another case can happen for which we make the following couple of observations.
After one move, a bug from or will always land in or .
So, in the third case, we apply Pigeon Hole Principle in the following way:
We have 65 bugs and two classes of colored squares (consisting of the squares from and ) and (consisting of the squares from and ). So there must be at least 33 bugs in one of the two classes and .
If the 33 bugs are in class then there are a total of 33 bugs in and , so by Pigeon Hole Principle again, there is at least 17 bugs in one of them, and the first 2 cases ensure that more than one bug can be located in the same square in such cases.
If the 33 bugs are in then after one move they will have moved to , by the observation given above. So after one move we have 33 bugs in A, whence the argument immediately before this ensures more than one bug in one square.
Hence we are done!
Note An interesting thing to note from this proof is that we can achieve the goal of having more than one bug in one square after a maximum of three moves. So at t=3 we can actually ensure that there is more than one bug in some square.
That's the beauty of coloring proofs, a way to visualize.