wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Colored Equilateral Triangles
        
(Message started by: Yournamehere on Sep 20^th, 2002, 2:52pm)

Title: Colored Equilateral Triangles
Post by Yournamehere on Sep 20^th, 2002, 2:52pm

An old but good one:

Suppose every point in the Euclidean plane is colored either red or blue. Prove there exists an equilateral triangle with all three corners the same color.

Title: Re: New: Colored Equilateral Triangles
Post by Pietro K.C. on Sep 21^st, 2002, 8:39am

Suppose an equilateral triangle with vertices A, B and C; there are 4 possible colourings of the vertices with red or blue (which we shall refer to as 0 and 1), not counting rotational symmetry. They are: (0,0,0), (1,1,1), (0,1,1), (1,0,0). Therefore, the probability that a triangle will not have all vertices the same color is 1/2. Since there are an infinite number of equilateral triangles, the probability that NONE of them have same-color vertices is 0. So there is at least 1 (and in fact an infinite number of) equilateral triangle with vertices of the same color. ;D

Unless someone went out of their way especially to prevent that from happening, and went through the trouble of choosing a color for EACH point in the plane. But that would just be mean.

Maybe later I'll post a different solution I got. :)

Title: Re: New: Colored Equilateral Triangles
Post by Jamie on Sep 22^nd, 2002, 4:31am

This was quite a fun little puzzle. I solved it by contradiction: assume you can have such a layout and see what it looks like. Start by looking at any equilateral triangle. By considering rotational symmetry and the fact the problem is colour-symmetric we can say without loss of generality that it must look like this:

http://www-lce.eng.cam.ac.uk/~jpw20/images/trigrid1.jpg

Now, the two blue points mean that the opposite point must be red:

http://www-lce.eng.cam.ac.uk/~jpw20/images/trigrid2.jpg

Applying the same logic now to the two red points gives us another two blue points:

http://www-lce.eng.cam.ac.uk/~jpw20/images/trigrid3.jpg

Finally, the same step again applied to the two outermost pairs of blue points gives us another four red points, and an red equilateral triangle (actually 2):

http://www-lce.eng.cam.ac.uk/~jpw20/images/trigrid4.jpg

Title: Re: New: Colored Equilateral Triangles
Post by Jamie on Jul 14^th, 2003, 6:20am

I've been thinking about variants on this problem. Does it work for squares as well? It seems intuitive that it should, but I haven't been able to prove it yet. What happens if we're allowed 3 different colours? What about n?

Title: Re: New: Colored Equilateral Triangles
Post by tohuvabohu on Jul 16^th, 2003, 2:36pm

I think I proved the square variation, but it's too long to bother typing out. In short:
If there is no square, I can demonstrate that certain shapes must exist, such as 4 points of one color forming a T, and 6 points forming a line of 4 with an extra point below the second and above the third (or vice versa). Then it got tough. From that last shape I had to eliminate a number of possible extensions.

Here are a couple that I'll present as a simple puzzle. Find the square in each and see that none of the four points could be changed without creating a different square (Any .'s simply represent a point whose color I had not yet determined. In the last two puzzles, you have to find the . that can neither be colored 0 or 1).

100110 011101 010100 000001 101100 100111 11100 00111 01101 00000 10110 001... 011001 .01100 10101. 100001 .101.. ........ ..110... ..1011.. .000010. .101.... ..1.001. .0.11... ........

Title: Re: New: Colored Equilateral Triangles
Post by Jamie on Jul 16^th, 2003, 3:14pm

on 07/16/03 at 14:36:15, tohuvabohu wrote:

I think I proved the square variation, but it's too long to bother typing out.

Ah. Proof by Fermat. My favourite :)

Title: Re: New: Colored Equilateral Triangles
Post by James Fingas on Jul 17^th, 2003, 12:15pm

tohuvabohu,

I tried a different method, which didn't pan out. I'm not convinced either way. But here is a puzzle in response to your puzzles. Try and find a square in this one:

1111100010 0010101110 0100100100 0111001001 1100010011 1011010101 1110110001 1001101111

Title: Re: New: Colored Equilateral Triangles
Post by tohuvabohu on Jul 17^th, 2003, 1:13pm

Your puzzle has many squares. I found 6 in just a few minutes.
11111D0010 001D101110 010010D100 01A1D01001 AB00E10F11 B0BA01E1F1 1ACEC10F01 100C1E1111
A shares one point with B and one with C, and E shares one point with F. I didn't bother looking for any larger ones or tilted at any other angles.

Title: Re: New: Colored Equilateral Triangles
Post by James Fingas on Jul 17^th, 2003, 1:46pm

ah ... now I understand why we are getting slightly different answers ... I was only considering squares aligned with the grid. I guess the triangle question didn't get complicated enough that it would matter.