mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-03-10, 08:29   #1
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

40048 Posts
Cool Network problem


As a sequel to Zeta-Flux's triangle puzzle I present a similar problem which is important for networks. It was given by no less our Mentor, Pierre de Fermat himself, to one of Galileo's pupils (name witheld)

Problem:

What is the shortest road network that will join three cities situated at the vertices of a triangle.

In other words, geometrically, it boils down to getting the minimum sum of distances from a point within, to the vertices of a given triangle and to find and construct the point .

Hint: The geometrical solution to find the point is by far the simplest

Mally
mfgoode is offline   Reply With Quote
Old 2007-03-10, 10:44   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

144638 Posts
Default

120 degrees between the arms gives a local minimum
davieddy is offline   Reply With Quote
Old 2007-03-10, 11:03   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

unless the triangle has an angle >120 degrees,
in which case the network consists of the two shortest sides


Will you believe I didn't Google this please?
davieddy is offline   Reply With Quote
Old 2007-03-10, 14:42   #4
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22·33·19 Posts
Question


Fair enough I give you the benefit of the doubt as its an old classic problem and hence well known.

But that is only half the answer.

How will you construct the point in relation to the 3 vertices ?

Mally
mfgoode is offline   Reply With Quote
Old 2007-03-10, 14:59   #5
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

80416 Posts
Question Half Right.

Quote:
Originally Posted by davieddy View Post
unless the triangle has an angle >120 degrees,
in which case the network consists of the two shortest sides


Will you believe I didn't Google this please?


Not quite!

Davie you are doing well and keep it up. Lets discuss this further.

Which triangle ? You mean the angles contained by the arms at the point.

What happens if one of the three angles is equal to 120* and the other two aren't ?

Mally

Last fiddled with by mfgoode on 2007-03-10 at 15:01 Reason: Add on
mfgoode is offline   Reply With Quote
Old 2007-03-10, 17:15   #6
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by mfgoode View Post


How will you construct the point in relation to the 3 vertices ?

Mally
Construct equilateral triangles on the outside of the
edges of the triangle. The circumcircles of these triangles
intersect at the desired point

Last fiddled with by davieddy on 2007-03-10 at 17:43
davieddy is offline   Reply With Quote
Old 2007-03-10, 17:41   #7
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by mfgoode View Post

Which triangle ? You mean the angles contained by the arms at the point.

What happens if one of the three angles is equal to 120* and the other two aren't ?

Mally
When the original triangle has an angle >=120 degrees,
the network consists of the two shortest sides

Last fiddled with by davieddy on 2007-03-10 at 17:41
davieddy is offline   Reply With Quote
Old 2007-03-11, 18:55   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default New problem

What is the shortest road network that will join four cities situated at the vertices of a rectangle of sides a and b?
davieddy is offline   Reply With Quote
Old 2007-03-11, 20:58   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

a>b
davieddy is offline   Reply With Quote
Old 2007-03-12, 17:58   #10
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by davieddy View Post
What is the shortest road network that will join four cities situated at the vertices of a rectangle of sides a and b?
If I remember well, something looking like >-<
where angles are 120° (?)
I think you can get the result by using a "soap bubble computer"
m_f_h is offline   Reply With Quote
Old 2007-03-12, 20:12   #11
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

645110 Posts
Default

Quote:
Originally Posted by m_f_h View Post
If I remember well, something looking like >-<
where angles are 120° (?)
I think you can get the result by using a "soap bubble computer"
That's what I guess. Total length a + b*SQR(3)

By twisting the "forks" we get the solution to a typical tetrahedron,
which leads me to doubt Cheesehead's soap film proposal.
(See tetrahedral network thread)
David
davieddy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Network logging? Xyzzy Linux 10 2015-09-25 17:55
Tetrahedral network problem cheesehead Puzzles 2 2007-03-10 19:06
Network LLR Citrix 15k Search 76 2005-09-04 17:32
shongo Network n8thegr8 Puzzles 2 2004-05-15 14:24
saving over a network crash893 Software 11 2004-05-06 14:15

All times are UTC. The time now is 03:59.

Wed Oct 28 03:59:58 UTC 2020 up 48 days, 1:10, 2 users, load averages: 1.99, 1.83, 1.77

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.