From: Fred Galvin Subject: Re: Interesting Pigeonhole Problem Date: Sun, 4 Feb 2001 17:00:05 -0600 Newsgroups: sci.math Summary: Ramsey-type coloring problem On Sun, 4 Feb 2001 markh931@my-deja.com wrote: > I came across the following exercise while browsing Brualdi's book > on combinatorics, and can't figure it out. Any takers? You are > given 6 points in the plane, no three collinear. Each of the 15 > different lines formed by these points is colored red or green. > Prove that there must be at least two triangles formed by these > points that are monochromatic. (One can be red and the other > green, or they can both be red or green.) I won't do your homework assignment for you, but I will give you some hints. The trick is to show that, among the 20 triangles formed by those lines, at most 18 are *not* monochromatic. And how do you figure the number of nonmonochromatic triangles? Here is your hint: observe that a nonmonochromatic triangle has 2 corners where red meets green. (If you can't figure out how to use those hints, you could use brute force: there are only so many ways to color 15 lines using blue and green.) To make the problem more interesting, determine the minimum number of monochromatic triangles possible if you have n points instead of 6. -- It takes steel balls to play pinball. ============================================================================== From: Fred Galvin Subject: Re: Interesting Pigeonhole Problem Date: Mon, 5 Feb 2001 01:29:02 -0600 Newsgroups: sci.math On Sun, 4 Feb 2001, Fred Galvin wrote: [quote of previous article deleted, except for this: --djr] > force: there are only so many ways to color 15 lines using blue and > green.) ^^^^ Oops, sorry, I mean red and green. -- It takes steel balls to play pinball.