## estudier 3 years ago A lattice of 21 dots, some red, some blue, in 3 rows of 7. Show that some 4 dots of 1 colour form the vertices of a rectangle.

1. UnkleRhaukus

|dw:1350302056370:dw|

2. estudier

Yes, like that, thank u for drawing it:-)

3. UnkleRhaukus

each row must have either more red, or more blue dots

4. UnkleRhaukus

therefore two of the rows has four or more of a certain colour

5. estudier

In total, there are 21 dots, so at least 11 are red or at least 11 are blue..

6. UnkleRhaukus

i get a minimum of 8

7. UnkleRhaukus

|dw:1350302644089:dw|

8. estudier

OK, maybe we can assume that 11 are blue and go from there....

9. UnkleRhaukus

|dw:1350302783459:dw|

10. UnkleRhaukus

|dw:1350302833654:dw|

11. estudier

Clearly, there are some different cases to consider.....

12. UnkleRhaukus

i dont know how to be general

13. estudier

There is some symmetry so we could assume that the top row has 7,6,5 or 4 blue dots.

14. sara12345

1 blue 20 red is also possible is it, it wont work.. just trying to understand the question

15. estudier

Then you are just working with reds instead of blues but the problem is still the same.

16. sasogeek

is this some sort of probability question?

17. estudier

Um...no.

18. sara12345

looks it is related to counting

19. estudier

Reasoning, I guess...

20. sasogeek

is it necessary that the dots along the edge of the rectangle be the same colour as the dots at the vertices?

21. estudier

Only that 4 dots of 1 colour are the vertices..

22. sara12345

|dw:1350303695070:dw|

23. sara12345

atleast 2 are of red or blue dots in each column

24. sara12345

|dw:1350303798138:dw|

25. estudier

That's right, you may just as well stick to one colour, it is simpler......

26. sara12345

in the second column only one way is possible for not to have a rectangle

27. sasogeek

there's an odd number of rows and an odd number of columns, is that a clue to anything?

28. sara12345

|dw:1350303894487:dw|

29. sara12345

but third column we cant escape a rectangle !

30. sara12345

is this ok proof ?

31. estudier

I think we should first start with the simplest case, which is when the complete row (say the top one) is all one colour......

32. sara12345

oh yeah we need to exhaust all cases

33. sara12345

begin from right side

34. sara12345

|dw:1350304093421:dw|

35. estudier

For that case, the question becomes where are the 4 remaining dots?

36. sara12345

next, to escape rectangle, we can have all 3b (or) 1r and 2 b

37. sara12345

so next column we cant have a rectangle, so lets see 3rd column for each of those

38. sara12345

|dw:1350304238693:dw|

39. sara12345

anthing in third column would make a rectangle when 3bs are there in 2nd column

40. sauravshakya

Do we count square as a rectangle?

41. estudier

Yes.

42. estudier

For the first case, we can say that the second row has at least 2 dots, right?

43. estudier

For if not, they are in the third row instead....

44. sara12345

or else if we just prove two exact same columns exist that would be enough

45. estudier

Take these 2 and the 2 above them in the first row and you get a rectangle.

46. sasogeek

what's the worst case scenario? in terms of number of dots for both colours... 11 of colour A and 10 of colour B... one colour must have even dots, and another odd dots the square would result from the colour with even dots what's the smallest rectangle we can have, what's the largest..... i'm only thinking, idk if it helps or makes any sense but it's what i can contribute to the solution xD hope it helps

47. estudier

The other 3 cases are not quite as easy but the reasoning is similar kind to that in the first case

48. sara12345

i see we can have all 7 unique columns

49. estudier

For the second case, you may as well assume that the first 6 are blue and then try to visualize where the remaining 5 are....

50. estudier

Hmm...not much interest in this, I will close it.....

51. MrMoose

If we take an arbitrary row of reds and blues, only 2 of the colors of the row on top of it may be the same (1 red and 1 blue), otherwise you get a rectangles: |dw:1350619459441:dw| leads to a rectangle

52. MrMoose

so, throughout the whole figure, you may only have 4 columns with consecutive colors: |dw:1350619522881:dw| (points arbitrarily chosen for demonstration)

53. MrMoose

Therefore, you must have at least 3 columns with alternating colors. These come in 2 states: R and B B R R B

54. MrMoose

therefore, by the pigeonhole principle, at least 2 of the columns share the same state

55. MrMoose

If two columns share the same state, they form a rectangle

56. MrMoose

QED