Author 
Topic: Lines and Points (Read 2019 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


Lines and Points
« on: Mar 10^{th}, 2007, 12:06pm » 
Quote Modify

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.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Lines and Points
« Reply #2 on: Mar 11^{th}, 2007, 10:42am » 
Quote Modify

Thanks, Aryabhatta! I started to forget the problems discussed by myself less than 3 years ago... Do I need to go to a doctor?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Lines and Points
« Reply #3 on: Mar 11^{th}, 2007, 11:26am » 
Quote Modify

on Mar 11^{th}, 2007, 10:42am, 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!


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7408


Re: Lines and Points
« Reply #4 on: Mar 13^{th}, 2007, 7:22am » 
Quote Modify

on Mar 11^{th}, 2007, 10:42am, 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?


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Lines and Points
« Reply #5 on: Mar 14^{th}, 2007, 12:03am » 
Quote Modify

on Mar 13^{th}, 2007, 7:22am, Grimbal wrote: No, no. But you DO remember the money I lend you 3 years ago, don't you? 



IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: Lines and Points
« Reply #6 on: Mar 17^{th}, 2007, 6:30am » 
Quote Modify

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?


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Lines and Points
« Reply #7 on: Mar 17^{th}, 2007, 12:57pm » 
Quote Modify

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


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Lines and Points
« Reply #8 on: Mar 18^{th}, 2007, 12:46pm » 
Quote Modify

Ok. Looks like the below might work. We follow along lines similar to the proof for the noncoloured 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 nonmonchromatic 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 nonmonchromatic sst (s=red or blue, t = opposite colour as s) triangle with a tline through the intersection of the ss 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 nonmonochromatic 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 nonmonochromatic triangle. In the proof of the noncoloured 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.

« Last Edit: Mar 18^{th}, 2007, 12:52pm by Aryabhatta » 
IP Logged 



