wu :: forums
« wu :: forums - Lines and Points »

Welcome, Guest. Please Login or Register.
Sep 23rd, 2018, 7:46am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, towr, Grimbal, ThudnBlunder, Icarus, william wu, SMQ)
   Lines and Points
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Lines and Points  (Read 2019 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Lines and Points  
« on: Mar 10th, 2007, 12:06pm »
Quote Quote Modify 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
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Lines and Points  
« Reply #1 on: Mar 11th, 2007, 8:46am »
Quote Quote Modify Modify

Has been posted before:  
 
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_med ium;action=display;num=1085852106;start=9#9
« Last Edit: Mar 11th, 2007, 8:46am by Aryabhatta » IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Lines and Points  
« Reply #2 on: Mar 11th, 2007, 10:42am »
Quote Quote Modify 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?  Huh
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Lines and Points  
« Reply #3 on: Mar 11th, 2007, 11:26am »
Quote Quote Modify Modify

on Mar 11th, 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?  Huh

 
No doctor!  
 
This way you can enjoy the beautiful puzzles, jokes, stories etc again and again!   Cheesy
 
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: Lines and Points  
« Reply #4 on: Mar 13th, 2007, 7:22am »
Quote Quote Modify Modify

on Mar 11th, 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?  Huh

No, no.  But you DO remember the money I lend you 3 years ago, don't you?   Wink
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Lines and Points  
« Reply #5 on: Mar 14th, 2007, 12:03am »
Quote Quote Modify Modify

on Mar 13th, 2007, 7:22am, Grimbal wrote:

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

 Grin Grin
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Lines and Points  
« Reply #6 on: Mar 17th, 2007, 6:30am »
Quote Quote Modify 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: male
Posts: 1321
Re: Lines and Points  
« Reply #7 on: Mar 17th, 2007, 12:57pm »
Quote Quote Modify 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  Tongue
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Lines and Points  
« Reply #8 on: Mar 18th, 2007, 12:46pm »
Quote Quote Modify Modify

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.
« Last Edit: Mar 18th, 2007, 12:52pm by Aryabhatta » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board