1

The question was asked in my today's quiz and I have no idea how to start with it. It's evident that we have to use pigeonhole principle somehow but how I am not getting. Question is " A 4×9 rectangular board is divided into squares each of which is coloured red or green or blue. Prove that the board contains a rectangle whose four corner squares are all the same colour. Thanks.

ogirkar
  • 2,681
  • 14
  • 27
  • I am getting that feeling. Can I approach by any different way. Please suggest. – ogirkar Sep 05 '19 at 21:33
  • Also; it seems to be false. – Servaes Sep 05 '19 at 21:33
  • If there were an answer (Donald's answer below shows there is not), you might start by noting that with three colors in four squares, each row will have at least two squares of the same color. Its a little bit counterintuitive in that the colors are the pidgeonholes and the squares are the pidgeons. – David Diaz Sep 05 '19 at 21:40

1 Answers1

6

Counter Example ... for instance ... Counter Example

Donald Splutterwit
  • 36,613
  • 2
  • 26
  • 73
  • Oh..how you come with this. Also how you got feeling that there will be contradictory example. – ogirkar Sep 05 '19 at 21:47
  • 3
    Each column must have at least two squares that are the same colours. These pairs can be in $\binom{4}{2}=6$ different configurations. There are $3$ colours, so there are $3 \times 6 =18$ ways to avoid any duplication of pairs. So I suspect the question should have been about a $4$ by $19$ rectangle. – Donald Splutterwit Sep 05 '19 at 21:53
  • Ok.I studied your comment. I unserstood how we will get 18 distinct pairs but how is this saying no rectangle with same corner colors...sorry you already have explained well but I am missing something. – ogirkar Sep 05 '19 at 22:15
  • 1
    See Joffan's Answer here https://math.stackexchange.com/questions/1919432/every-point-of-a-grid-is-colored-in-blue-red-or-green-how-to-prove-there-is-a/1919497#1919497 – Donald Splutterwit Sep 05 '19 at 22:44
  • 1
    Thanks ...I got it fully now – ogirkar Sep 05 '19 at 23:55