Author |
Topic: Lines and Points (Read 2257 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Lines and Points
« on: Mar 10th, 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 11th, 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 11th, 2007, 11:26am » |
Quote 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? |
|
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: 7526
|
|
Re: Lines and Points
« Reply #4 on: Mar 13th, 2007, 7:22am » |
Quote 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? |
|
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 14th, 2007, 12:03am » |
Quote 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? |
|
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Lines and Points
« Reply #6 on: Mar 17th, 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 17th, 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 18th, 2007, 12:46pm » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print