From: Fred Galvin <galvin@math.ukans.edu>
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 <galvin@math.ukans.edu>
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.