Author |
Topic: Dots (Read 1457 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
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?
|
| « Last Edit: May 29th, 2004, 6:13pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
 |
Re: Dots
« Reply #1 on: May 29th, 2004, 1:06pm » |
 Quote  Modify
|
umm proof:
dot diagram implies non-collinear dots
hence no dot diagram can have 3 dots in a line
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Dots
« Reply #2 on: May 29th, 2004, 6:11pm » |
Quote Modify
|
on May 29th, 2004, 1:06pm, 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.)
|
| « Last Edit: May 31st, 2004, 7:54am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Dots
« Reply #3 on: May 30th, 2004, 2:29pm » |
Quote Modify
|
Does the following diagram proove feasibility?
.
. .
. . .
Just add the 3 straight lines where obvious.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Dots
« Reply #4 on: May 30th, 2004, 5:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Dots
« Reply #5 on: May 30th, 2004, 9:08pm » |
Quote Modify
|
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?)
|
| « Last Edit: May 31st, 2004, 7:53am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Dots
« Reply #6 on: May 31st, 2004, 11:38am » |
Quote Modify
|
on May 30th, 2004, 9:08pm, 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:
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.
|
| « Last Edit: May 31st, 2004, 11:44am by Aryabhatta » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Dots
« Reply #7 on: Jun 1st, 2004, 5:52am » |
Quote Modify
|
on May 31st, 2004, 11:38am, 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.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Dots
« Reply #8 on: Jun 1st, 2004, 6:50am » |
Quote Modify
|
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.
|
| « Last Edit: Jun 3rd, 2004, 4:03am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Dots
« Reply #9 on: Jun 1st, 2004, 1:13pm » |
Quote Modify
|
on Jun 1st, 2004, 5:52am, 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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Dots
« Reply #10 on: Jun 2nd, 2004, 7:04am » |
Quote Modify
|
on Jun 1st, 2004, 1:13pm, Aryabhatta wrote:
I can post that solution if someone is interested.
|
|
eh? You don't need to ask!!!! 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Dots
« Reply #11 on: Jun 2nd, 2004, 10:52am » |
Quote Modify
|
on Jun 2nd, 2004, 7:04am, Sameer wrote:
eh? You don't need to ask!!!! |
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Dots
« Reply #12 on: Mar 12th, 2007, 4:44pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Dots
« Reply #13 on: Mar 12th, 2007, 9:15pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Dots
« Reply #14 on: Mar 12th, 2007, 10:53pm » |
Quote Modify
|
on Mar 12th, 2007, 9:15pm, 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.
|
| « Last Edit: Mar 12th, 2007, 11:27pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Dots
« Reply #15 on: Mar 12th, 2007, 10:58pm » |
Quote Modify
|
on Mar 12th, 2007, 4:44pm, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print