4
$\begingroup$

This is a problem that I have spent a good 2 hours on but can seem to come up with any rigorous solution. If someone could provide one that would be great!

If we color 21 vertices of a 50-gon, how do we go about proving that will always exist 3 vertices such that if you connect them you get an isosceles triangle?

  • 0
    I've re-titled the question to be more accurate and hopefully generate more traffic; the original title was misleading, as the problem may not be of any particular interest to some readers.2012-08-28
  • 0
    Presumably the 50-gon is regular?2012-08-28
  • 0
    Depends on how many colors you are coloring with. If I have 50 different colors to choose from, then it obviously isn't true.2012-08-28
  • 0
    Sorry I should have been more clear. We have to connect 3 vertices of the same color, and all 21 are colored the same color. Also the 50-gon is regular2012-08-28
  • 0
    Do you mean that after you "color" 21 vertices, you can always find three *colored* vertices that form an isosceles triangle? Or do you mean that if you color 21 vertices one color and 29 a second color, you can always find three vertices *of the same color* that form an isosceles triangle?2012-08-28
  • 0
    (I'm interpreting it as an isosceles triangle with colored vertices) This is equivalent to choosing a set of 21 residues mod 50, and then finding $a,b,c$ in arithmetic progression. This reminds me of Roth's theorem on arithmetic progressions of length 3. Unfortunately, all known proofs give very bad bounds...2012-08-28
  • 0
    Yes MJD that is what I mean.2012-08-28
  • 0
    You should not answer a "Do you mean $X$? Or do you mean $Y$?" question with "Yes that is what I mean"!2012-08-28

1 Answers 1

7

Join alternate vertices of the $50$-gons to produce two $25$-gons. One of the two $25$-gons must have at-least $11$ colored vertices. Further partition this polygon into $5$ - regular pentagons by joining every fifth vertex. One of the pentagons must contain at least three colored vertices. But then those three vertices necessarily form an isosceles triangle.

  • 1
    Beautiful! There are probably clunkier pigeonhole principle arguments, but this is an amazingly elegant one. +1 for sure.2012-08-28