2
$\begingroup$

Suppose that each square of a $4 \times 7$ chessboard is colored either black or white. Prove that with any such coloring, the board must contain a rectangle (formed by the horizontal and vertical lines of the board) whose four distinct unit corner squares are all of the same color?

Any hints on this problem, I guess it could be solved with a clever application of the pigeonhole principle, but I have some difficulty seeing what the objects and what the bags are in which to put the objects to apply the pigeonhole principle, and then argue that such an coloring must exist. It is taken from a textbook on discrete mathematics, and in the text a version of the Monotone Subsequence Theorem by Erdös/Szekeres is proven (using the pigeonhole principle). Hence, I guess it is somehow related to this.

$\endgroup$
2
$\begingroup$

Consider the case where we have a monochromatic row ($4$ black squares) the next rows must either have $1$ or $0$ black squares and in order to avoid both a white or black rectangle, we can only add one more row.

Now consider the case where the first row has $3$ black squares, one can rapidly show that there are three more rows that we could add before a fifth row would cause a monochromatic rectangle.

Best we can do is have the following $6$ rows each containing $2$ black & $2$ white squares, and a seventh row will cause a monochromatic rectangle.

enter image description here

$\endgroup$
  • $\begingroup$ Thanks, got it. I somehow misunderstood the question, I thought a rectangle meant a single unit square, and the corners where the four "orthogonally" adjacent unit squares, hence I somehow thought about mapping the $2\times 5$ inner unit squares according to the coloring of their surrounding and was stuck in this line of thought. But yes, havent tried to built a counterexample, for example simply adjacent black and white rows, to show myself that I misunderstood the question. $\endgroup$ – StefanH Feb 5 '18 at 11:28
4
$\begingroup$

Let's say the chessboard has $4$ columns and $7$ rows. Each row must land in (at least) one of the following $6$ bags:

  1. First and second squares are black.
  2. First and third squares are black.
  3. Second and third squares are black.
  4. First and second squares are white.
  5. First and third squares are white.
  6. Second and third squares are white.

By the pigeonhole principle, two rows are in the same bag, and that gives you your rectangle with all four corner squares of the same color.

Note that you only need a $3\times7$ chessboard for this to work.

$\endgroup$
  • $\begingroup$ Thank you, very elegant, but I have to accept the other answer as it is totally fine and was given earlier. But as you have more upvotes I guess this is fair in the end, so both of you have the same credits. $\endgroup$ – StefanH Feb 5 '18 at 11:30
0
$\begingroup$

isnt there a trivial case?

"the board must contain a rectangle (formed by the horizontal and vertical lines of the board) whose four distinct unit corner squares are all of the same color?"

Each square of the board is a rectangle and every corner of the square must be the same color because it is only one square, a solid color

$\endgroup$
  • $\begingroup$ I guess by saying "four distinct unit corner squares" the problem implies that we just look at rectangles containing at least four distinct unit squares. Otherwise, surely this would be trivial $\endgroup$ – StefanH Feb 10 '18 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.