Prove there exists $2\times 2$ checkerboard-colored square in a $100\times 100$ table colored black and white.

Question

"Each cell of a 100 × 100 table is painted either black or white and all the cells adjacent to the border of the table are black. It is known that in every 2 × 2 square there are cells of both colours. Prove that in the table there is 2 × 2 square that is coloured in the chessboard manner."

Source of problem

How to solve this problem?

Answer 1

Hint: Stick $99\times 99$ needles on this grid, each at a place where four cells meet in a corner. For each pair of needles at distance one apart, connect them with a piece of string if the the two squares touching the edge between them have different colors.

Each needle with have either $2$ or $4$ pieces of string tied to it (why?). If a needle has four strings, then the four squares surrounding it are colored like a checkerboard. So, assume to the contrary that every needle only has two strings. What would the resulting picture look like? Why is that impossible?

Further hint:

If every needle only had two strings, then the needles would be partitioned into "loops," where each needle is connected to a the next and previous in a circular fashion. What are the possible sizes of a loop?

For example, you can have a loop of size four where the four needles are the vertices of a cell. Can you have a loop of size $5$?

Answer 2

Step 1:First reduce the problem to a simpler,but proportional version of the problem Let's consider a 10 x 10 board where all the border lining boxes are black. now imagine painting inward as shown in the following figure. Click to see image

Then there would be way to colour the square in the middle without leaving one 2x2 square in one colour.Therefore one square(not the corners) should be changed to the opposite colour(i.e black) then this generates a 2x2 square coloured like the chess board when the entire board is coloured Click here to see picture

now returning to the original problem we must compute how many squares are left when we finish painting like bands.(step 1). As the board is 100 x 100, there are also 100 diagonal squares(just as there are 100 diagonal squares in the 10 x 10 grid) then at the dead-center of the square there will not be a square but set of 4 squares (see above image and compare). [this is because there are even no. of squares.] Then the same argument for the 10 x 10 square works.

Therefore there should be one 2 x 2 square painted like in chess board.