Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

estudier Group Title

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.

  • one year ago
  • one year ago

  • This Question is Closed
  1. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350302056370:dw|

    • one year ago
  2. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  3. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  4. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  5. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  6. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i get a minimum of 8

    • one year ago
  7. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350302644089:dw|

    • one year ago
  8. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  9. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350302783459:dw|

    • one year ago
  10. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350302833654:dw|

    • one year ago
  11. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  12. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i dont know how to be general

    • one year ago
  13. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  14. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  15. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  16. sasogeek Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    is this some sort of probability question?

    • one year ago
  17. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Um...no.

    • one year ago
  18. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    looks it is related to counting

    • one year ago
  19. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Reasoning, I guess...

    • one year ago
  20. sasogeek Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  21. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  22. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350303695070:dw|

    • one year ago
  23. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    atleast 2 are of red or blue dots in each column

    • one year ago
  24. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350303798138:dw|

    • one year ago
  25. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  26. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  27. sasogeek Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  28. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350303894487:dw|

    • one year ago
  29. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    but third column we cant escape a rectangle !

    • one year ago
  30. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    is this ok proof ?

    • one year ago
  31. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  32. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    oh yeah we need to exhaust all cases

    • one year ago
  33. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    begin from right side

    • one year ago
  34. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350304093421:dw|

    • one year ago
  35. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  36. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  37. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  38. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1350304238693:dw|

    • one year ago
  39. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  40. sauravshakya Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Do we count square as a rectangle?

    • one year ago
  41. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes.

    • one year ago
  42. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  43. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  44. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  45. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  46. sasogeek Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • one year ago
  47. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  48. sara12345 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    i see we can have all 7 unique columns

    • one year ago
  49. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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....

    • one year ago
  50. estudier Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • one year ago
  51. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • one year ago
  52. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  53. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  54. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  55. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  56. MrMoose Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    QED

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.