wu :: forums « wu :: forums - Lines and Points » Welcome, Guest. Please Login or Register. Sep 23rd, 2018, 7:46am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Eigenray, towr, Grimbal, ThudnBlunder, Icarus, william wu, SMQ)    Lines and Points « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Lines and Points  (Read 2019 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
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: Lines and Points   « Reply #1 on: Mar 11th, 2007, 8:46am » Quote 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:
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: 7408
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »