wu :: forums - Print Page


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

        riddles >> hard >> Lines and Points
        
(Message started by: Barukh on Mar 10^th, 2007, 12:06pm)

Title: Lines and Points
Post by Barukh on Mar 10^th, 2007, 12:06pm

Given a set of n > 2 points in the plane, not all collinear, consider all lines joining the pairs of points from the set.

Prove there is a line with exactly 2 points.

I don't know the solution, and I don't even know if it belongs to hard. My friend presented this problem to me earlier today. He told me that the truly elementary solution was devised about 20 years ago, although the problem was known for at least 60 years.

Title: Re: Lines and Points
Post by Aryabhatta on Mar 11^th, 2007, 8:46am

Has been posted before:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1085852106;start=9#9

Title: Re: Lines and Points
Post by Barukh on Mar 11^th, 2007, 10:42am

Thanks, Aryabhatta!

I started to forget the problems discussed by myself less than 3 years ago...

Do I need to go to a doctor? ???

Title: Re: Lines and Points
Post by Aryabhatta on Mar 11^th, 2007, 11:26am

on 03/11/07 at 10:42:56, Barukh wrote:

Thanks, Aryabhatta!

I started to forget the problems discussed by myself less than 3 years ago...

Do I need to go to a doctor? ???

No doctor!

This way you can enjoy the beautiful puzzles, jokes, stories etc again and again! :D

Title: Re: Lines and Points
Post by Grimbal on Mar 13^th, 2007, 7:22am

on 03/11/07 at 10:42:56, Barukh wrote:

Thanks, Aryabhatta!

I started to forget the problems discussed by myself less than 3 years ago...

Do I need to go to a doctor? ???

No, no. But you DO remember the money I lend you 3 years ago, don't you? ;)

Title: Re: Lines and Points
Post by Barukh on Mar 14^th, 2007, 12:03am

on 03/13/07 at 07:22:24, Grimbal wrote:

No, no. But you DO remember the money I lend you 3 years ago, don't you? ;)

;D ;D

Title: Re: Lines and Points
Post by Barukh on Mar 17^th, 2007, 6:30am

Here is a variation.

Consider 2 finite sets of points (not all collinear) and the lines formed by every pair of these points. The points in one set are colored red, in another - blue.

Is it true that there is always a "monochromatic" line?

Title: Re: Lines and Points
Post by Aryabhatta on Mar 17^th, 2007, 12:57pm

Hmm.. interesting. My guess is "yes" (though my guesses are wrong most of the times) there is always a monochromatic line. Now proving it is the hard part :P

Title: Re: Lines and Points
Post by Aryabhatta on Mar 18^th, 2007, 12:46pm

Ok. Looks like the below might work.

We follow along lines similar to the proof for the non-coloured version given in the Dots thread (see second post in this thread for a link to that thread)

Consider the dual.

We now have n lines, either red or blue, not all concurrent, no two parallel. We need to show that there is at least one point through which only like coloured lines pass.

Assume the contrary, i.e there is no such point.

Consider a non-monchromatic triangle XAB. Say Composed of 2 Red edges (intersect at X) and one Blue edge. Now assume that there is a Blue line through X (the two Red lines intersection point) which splits the triangle XAB into two smaller trianges XAC and XBC.

Consider the point C. It is the intersection point of 2 Blue lines. So assume there is a red line through it. That line intersects one of XA or XC , say XA in D.

Thus we have the BBR triangle XAC, with blue lines intersecting at C such that there is a red line through C splitting this triangle into smaller triangles.

i.e Given any non-monchromatic sst (s=red or blue, t = opposite colour as s) triangle with a t-line through the intersection of the s-s edges, we can find a smaller area triangle with the same property.

Since there are a only finite number of lines, we are done, i.e there must be a point through which only like coloured lines pass.

Now all we need to prove is such a triangle exists.

To prove the existence of such a triangle, just take the largest area non-monochromatic triangle. We can easily show that either there is a required colour line through the required vertex of the triangle splitting it into smaller triangles or there is a bigger non-monochromatic triangle.

In the proof of the non-coloured version in the other thread, just using the minimal area triangle worked, but that approach did not seem to work here (trying that approach did give a clue that we can probably find a never ending sequence of triangles though).

Maybe someone can make that approach work.