Coloring proofs are one of long known strategies, which have obtained new “colors” together with modern data-rich problems. The main idea of the coloring strategies is:
to group the given data according to some features and assign colors to groups.
If you are a data scientist or have studies some basic data science course, then this should sound familiar. For better understanding, let’s see some fundamental demo problems.
1.Bugs
Problem:
In each cell of the 5x5 board there is a ladybug. At some point, all the ladybugs crawl onto adjacent (horizontal or vertical) cells. Will this necessarily leave an empty cell?
Beetles are big for illustration purposes only. It is assumed that one cell could fit several beetles.
Solution:
First, if you pay close attention to where a ladybug can crawl, that should give some idea.
If the picture above didn’t ring a bell, then maybe imagine it like this:
So, if the board was painted in black and white, like a chessboard, then a ladybug sitting on a white cell can crawl to a black cell only, and a ladybug sitting on a black cell to a white cell only. Okay, this seems to be some an extra information about our problem. And we are obtaining this extra piece of information by visualizing the 5x5 board as “chessboard”. Then let’s re-state our problems with this extra detail:
In each cell of the 5x5 chessboard, which is painted in black and white colors, there is a ladybug. At some point, all the ladybugs crawl onto adjacent (horizontal or vertical) cells. Since cells adjacent to white cells are black and cells adjacent to black cells are white, ladybugs that are sitting on black cells will crawl to white cells and from white to black. Will this necessarily leave an empty cell?
So, at this point, just counting ladybugs by cell colors, should make the answer obvious.
12 ladybugs are sitting on white cells, 13 on black cells. What will we observe when the crawling happens? 13 ladybugs that were sitting on black cells need to move to white cells, number of which is only 12. So there must be several ladybugs in one the white cells. Similarly, 12 ladybugs that were sitting on white cells need to move to black cells, number of which is 13. These 12 ladybugs can’t fill 13 black cells, there will always be 1 empty black cell.
Answer:
There will always be 1 empty black cell.
2.Tetrominoes
Problem:
Is it possible to cover 10 by 10 chessboard by 25 straight tetrominoes?
Solution:
Since 10 is not divisible by 4 we encounter difficulties. Here you can get your pen and paper or in your imagination, try to do the covering. 10x10 has 100 cells and 25 straight tetrominoes have 100 cells. You need to perfectly cover all 100 cells of the 10x10 board, without overlapping, without breaking tetrominoes or using more than 25, etc…
I will go ahead and give you the answer, it is impossible. But how do you prove that it is impossible?
Here a simple coloring trick comes to help: let’s color the 10x10 board with 4 colors in the following way:
This coloring has a very interesting property: No matter how you place the tetromino on the board, it will always cover one of each of colors.
If we assume that it is possible to cover the board with 25 tetrominoes, then we have to cover with 25 tetrominoes, 25 of each colors, 25 red, 25 white, 25 blue, 25 green.
However, if we look at the board above, there are 26 red cells, which means we need at least 26 tetrominoes to cover the 10x10 board. So, it is not possible to do it with 25 tetrominoes.
The ideas above are like building blocks of larger and complex challenges. It takes some effort to be able to use them in your large scale applied tasks.