1

I have a suggestion for a solution to a question and I would appreciate if you could verfy it.

Question

Consider a $6\times 16$ checkerboard painted in 3 colors (let's say $0,1,2$ ). Prove that there is a rectangle whose four vertices are painted in the same color.

My solution

There are $6\cdot 16$ different squares, only $3$ different colors then by PHP there are at least $\left\lceil \frac{6 \cdot 16}{3} \right\rceil = 32$ different squares of the same color. You only need $4$ to finish the proof.

This question appeared in some test. If my solution is right then I think the question is too easy for a test. That's why I have to verify if it's correct.

Lior
  • 623
  • You need the four to be in the right place. For instance, if all of one row, and all of one column are green, you have 21 green squares and no rectangle with four green vertices. – mcd Jun 30 '23 at 18:06
  • The rectangle question refers to is one made up of four vertices each of which is in a (different) square of the checkerboard. – Anurag A Jun 30 '23 at 18:07
  • @mcd Sorry, I don't understand why you contradict my solution. – Lior Jun 30 '23 at 18:17
  • Lior, you say that "we only need 4 to finish the proof". So, can you edit in the details of how you will finish the proof? IE Why is there a "rectangle whose four vertices are painted in the same color"? $\quad$ mcd points out a case where we have more than 4 squares (actually 21) painted the same color, but such a rectangle doesn't exist. – Calvin Lin Jun 30 '23 at 18:23
  • @CalvinLin Actually, I do understand now why 4 isn't enough. I will have to think harder about why $21$ isn't enough. I have no clue how to solve this even I do understand what PHP gives if I use for it for every column or row. – Lior Jun 30 '23 at 18:37
  • 21 isn't enough because mcd gave a construction -> Take the first row and first column, color those 21 with the same color. Then clearly no rectangle exists. $\quad$ Without giving the crux away, think about what elements are sufficient (and maybe even necessary) to form a rectangle. The idea is to apply PHP to force there to be enough of these elements, of a particular type. EG We discovered "4 squares of that color" isn't sufficient, so holes = color and pigeons = squares won't allow us to naively/easily solve this. – Calvin Lin Jun 30 '23 at 18:41

0 Answers0