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.

  • $\begingroup$ I am getting that feeling. Can I approach by any different way. Please suggest. $\endgroup$ – Believer Sep 5 '19 at 21:33
  • $\begingroup$ Also; it seems to be false. $\endgroup$ – Servaes Sep 5 '19 at 21:33
  • $\begingroup$ 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. $\endgroup$ – David Diaz Sep 5 '19 at 21:40

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

| cite | improve this answer | |
  • $\begingroup$ Oh..how you come with this. Also how you got feeling that there will be contradictory example. $\endgroup$ – Believer Sep 5 '19 at 21:47
  • 3
    $\begingroup$ 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. $\endgroup$ – Donald Splutterwit Sep 5 '19 at 21:53
  • $\begingroup$ 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. $\endgroup$ – Believer Sep 5 '19 at 22:15
  • 1
    $\begingroup$ See Joffan's Answer here math.stackexchange.com/questions/1919432/… $\endgroup$ – Donald Splutterwit Sep 5 '19 at 22:44
  • 1
    $\begingroup$ Thanks ...I got it fully now $\endgroup$ – Believer Sep 5 '19 at 23:55

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.