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

        riddles >> medium >> Dots
        
(Message started by: THUDandBLUNDER on May 29th, 2004, 10:35am)
Title: Dots
Post by THUDandBLUNDER on May 29th, 2004, 10:35am
A dot diagram consists of a series of dots, not all of which are collinear, that are all connected to each other by straight lines.

Is it possible to draw a dot diagram such that every line has at least three dots on it?
Title: Re: Dots
Post by TenaliRaman on May 29th, 2004, 1:06pm
umm proof:
dot diagram implies non-collinear dots
hence no dot diagram can have 3 dots in a line
???
Title: Re: Dots
Post by THUDandBLUNDER on May 29th, 2004, 6:11pm

on 05/29/04 at 13:06:06, TenaliRaman wrote:
umm proof:
dot diagram implies non-collinear dots
hence no dot diagram can have 3 dots in a line
???

Hmm...maybe I ought to have put it in Easy.   ::)

The dots are not ALL collinear. (I have amended the wording.)
Title: Re: Dots
Post by grimbal on May 30th, 2004, 2:29pm
Does the following diagram proove feasibility?

   .
 .   .
.   .   .

Just add the 3 straight lines where obvious.
Title: Re: Dots
Post by rmsgrey on May 30th, 2004, 5:47pm
I think it depends whether "all connected to each other by straight lines" means each pair is directly connected by a straight line (possibly through another point), or that there exists a path between each pair.

I suspect the former is intended.
Title: Re: Dots
Post by THUDandBLUNDER on May 30th, 2004, 9:08pm
If S is a set of non-collinear points in the Euclidean plane such that [smiley=forall.gif] x [smiley=in.gif] S and [smiley=forall.gif] y [smiley=in.gif] S-{x}  
[smiley=exists.gif] z in S-{x,y} collinear with x and y, prove that S must be an infinite set.

(Better?)
Title: Re: Dots
Post by Aryabhatta on May 31st, 2004, 11:38am

on 05/30/04 at 21:08:02, THUDandBLUNDER wrote:
If S is a set of non-collinear points in the Euclidean plane such that [smiley=forall.gif] x [smiley=in.gif] S and [smiley=forall.gif] y [smiley=in.gif] S-{x}  
[smiley=exists.gif] z in S-{x,y} collinear with x and y, prove that S must be an infinite set.

(Better?)


I don't think this should be in the medium section.
When this problem was first posed, it remained open for around 30 years!

Here is a outline of a proof:
[hide]
Suppose the statement is false. Then there are n points (not all collinear) such that for any 2 points, there is a third which is collinear with those two. Consilder the 'dual' of this arrangement. Points map to lines and lines map to points. We get that not all lines are concurrent and no two are parallel. We need to show that there is a point through which only 2 lines pass.

Assume that this is not case. Consider the triangle with smallest area. Say ABC. Then we get that there is another triangle A'B'C' such that ABC lie on the interior of B'C', A'C' and A'B" respectively. We can easily show that one of the
triangles AB'C', BC'A', CA'B' has smaller area than ABC, which leads to a contradiction.
[/hide]
Title: Re: Dots
Post by Barukh on Jun 1st, 2004, 5:52am

on 05/31/04 at 11:38:47, Aryabhatta wrote:
I don't think this should be in the medium section.
When this problem was first posed, it remained open for around 30 years!

So what? It is still Medium for THUD&BLUNDER!  ;)

I like the proof you presented. Do you know sources where this theorem is studied? I saw it mentioned in D. Hilbert’s “Geometry and Imagination”, but no proof provided, and the only reference is to a German source from 1929.
Title: Re: Dots
Post by THUDandBLUNDER on Jun 1st, 2004, 6:50am

Quote:
So what? It is still Medium for THUD&BLUNDER!

Haha. Actually, the reason I put it in Medium is that there exists at least one surprisingly simple proof.  ;)

There are some references here (http://mathworld.wolfram.com/SylvestersLineProblem.html).
Title: Re: Dots
Post by Aryabhatta on Jun 1st, 2004, 1:13pm

on 06/01/04 at 05:52:48, Barukh wrote:
So what? It is still Medium for THUD&BLUNDER!  ;)


;)


Quote:
I like the proof you presented. Do you know sources where this theorem is studied? I saw it mentioned in D. Hilbert’s “Geometry and Imagination”, but no proof provided, and the only reference is to a German source from 1929.


I am glad you liked the proof. I first saw this problem on the http://www.kalva.demon.co.uk/ site which lists problems from various math olympiads. It was given in the vietnam math olympiad in 1987! This was the problem statement
"There are n > 2 lines in the plane, no two parallel. The lines are not all concurrent. Show that there is a point on just two lines. "

I guess they intended the student to convert it to the original version using the dual and use Sylvester's result. I think this was also posed (original non-dual version) on the IBM ponder this website, don't remember when. There are also planar-graph theoretic proofs of this result!

I also saw a proof of a similar result in Donald Newman's "A Problem Seminar" which uses linear algebra! I think the statement which was proved was
"If we have n points, not all collinear, then we have at least n lines".

I can post that solution if someone is interested.
Title: Re: Dots
Post by Sameer on Jun 2nd, 2004, 7:04am

on 06/01/04 at 13:13:21, Aryabhatta wrote:
I can post that solution if someone is interested.


eh? You don't need to ask!!!!  :D
Title: Re: Dots
Post by Aryabhatta on Jun 2nd, 2004, 10:52am

on 06/02/04 at 07:04:40, Sameer wrote:
eh? You don't need to ask!!!!  :D


Here goes.

Consider a point as the set of the lines that pass through it.
So a restatement of the problem becomes:

Given n distinct sets S1,S2,...Sn such that for any i  [lessgtr] j, |Si  [bigcap] Sj| = 1. Show the |[bigcup]i =1[supn] Si|  [ge] n.
(|A| is the size of the set A)

Assume that there are more points than lines. We can attach numbers, not all 0, to the points in such a way, that for each line the total of these numbers for the points on that line is 0.
(Basically we have a system of k linear equations in n variables)

Call the points 1,2,...,n the lines L1,L2,...,Lk and the numbers x1,x2,...,xn.

Thus for each line v, [sum]i[in]L_v xi = 0.
Now look at

T = [sum]v=1k ([sum]i[in]L_vxi)[sup2]

Observe that every xi[sup2] appears at least twice and every cross term 2xixj (i[lessgtr] j) appears exactly once. (2xixj appears exactly once because 2 points determine a unique line. xi[sup2] appears at least twice because each point is on at least 2 lines)

So we have

0 = T  [ge] [sum]i=1[supn] xi[sup2] + ([sum]i = 1[supn] xi)[sup2] > 0

A contradiction!

An awesome proof! The book is filled with such gems. I highly recommend it.
Title: Re: Dots
Post by Eigenray on Mar 12th, 2007, 4:44pm
Actually there is an elementary solution to the original problem without dualizing: by assumption there exist (finitely many) non-degenerate triangles.  Pick one with a minimal altitude; the base of that altitude is the required line.
Title: Re: Dots
Post by ecoist on Mar 12th, 2007, 9:15pm
Am I missing something?  Here's a proof for:

Given n points, not all collinear, the pairs of these points determine at least n straight lines.

Induction on n.  The statement is true for n=3 points.  Assume that the statement is true for n>=3 points and consider a set A of n+1 points.  Let p be any point in A.  Assume, by way of contradiction, that pairs of points in A determine fewer than n+1 lines.  Then, by induction, A\{p} determines exactly n lines and so p must lie on all of them.  By the same argument, a second point q in A lies on all n lines determined by A\{q}, which lines must be the same n lines as those determined by A\{p}.  This contradicts the fact that n>1 distinct lines can intersect in at most one point.  Hence the pairs of points in A determine at least n+1 lines.
Title: Re: Dots
Post by Aryabhatta on Mar 12th, 2007, 10:53pm

on 03/12/07 at 21:15:24, ecoist wrote:
Am I missing something?  Here's a proof for:

Given n points, not all collinear, the pairs of these points determine at least n straight lines.

<snip>


The intent was more on the proofs which make you go "wow" rather than those which work. (nice proof, btw)

Here is another proof for the n points n lines prob which uses the result (Sylvester-Gallai) discussed in this thread.

Induction. Assume true for n. Given set of n+1 points. By the result discussed, there are 2 points such that no other points lie on that line. Remove one of those points and apply the induction assumption.
Title: Re: Dots
Post by Aryabhatta on Mar 12th, 2007, 10:58pm

on 03/12/07 at 16:44:38, Eigenray wrote:
Actually there is an elementary solution to the original problem without dualizing: by assumption there exist (finitely many) non-degenerate triangles.  Pick one with a minimal altitude; the base of that altitude is the required line.


Yes, I believe this is the most famous/well known proof for this.

A very elegant proof of this uses graph theory:

Dualize and map the lines onto the surface of a sphere. The resulting graph of points (vertices) and lines (edges) is planar and hence has a vertex of degree <= 5.
Title: Re: Dots
Post by Aryabhatta on Mar 17th, 2007, 12:55pm
Linking to the other thread on this topic:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1173557173


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