mersenneforum.org shongo Network
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-05-04, 12:42 #1 n8thegr8   24×3×7×13 Posts shongo Network Ok we had this discussion on another board - nobody could figure it out. It was the draw a figure without lifting your pencil. According to euler it won't work because there are more than 2 points with odd number of vertices. Well then I did research and found out about shongo networks - and the very drawing we talked about was shown. For the life of me, I can't figure it out though. At the bottom of this page http://educ.queensu.ca/~fmc/april2002/Shongo.htm there are 3 drawings - its the middle of the 3. Does anyone know how to do it without there being a trick (ie drawing extra line or folding paper)
2004-05-15, 11:27   #2
Qbert

May 2004

22 Posts

Quote:
 Originally Posted by n8thegr8 I did research and found out about shongo networks - and the very drawing we talked about was shown.
Even though it was shown, it didn't imply that it was solvable. The rule Euler discovered is still being tought at the places I'm aware of for graph theory, and so I'm conviced you can't solve that problem without somehow manipulating the network.

2004-05-15, 14:24   #3
wblipp

"William"
May 2003
New Haven

44448 Posts

Quote:
 Originally Posted by n8thegr8 At the bottom of this page http://educ.queensu.ca/~fmc/april2002/Shongo.htm there are 3 drawings - its the middle of the 3. Does anyone know how to do it without there being a trick (ie drawing extra line or folding paper)
Among mathematicians, proving that something is impossible counts as solving the problem. The Euler rule is simple to understand and proves the network is not traceable with a single line. Pick any point with an odd number of line segments connected to it. Suppose the network is traceable. Either you will start here or you will start someplace else;

First consider the case of starting here. When you trace out, there are now an even number of untraced line segments. Every time you return to the point, there will be an odd number of untraced line segments, to you can leave again. Eventually you will leave with zero untraced segments and never return. So if you start here, you will end someplace else.

Second consider the case of starting someplace else. Every time you return to the point, there will be an even number of untraced links left, and every time you depart the point there will be an odd number of untraced links left. Eventually you will reach the point with zero untraced links conected to the point so you will quit.

Hence every point with an odd number of links must be eiher a starting point or an ending point.

The diagram has FOUR points with an odd number of links. The only way trace it is to use TWO lines to get two starting points and two ending points.

William

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Linux 10 2015-09-25 17:55 Maybeso Information & Answers 5 2009-02-07 20:52 mfgoode Puzzles 19 2007-03-19 15:31 Citrix 15k Search 76 2005-09-04 17:32 crash893 Software 11 2004-05-06 14:15

All times are UTC. The time now is 16:40.

Sun Oct 25 16:40:28 UTC 2020 up 45 days, 13:51, 1 user, load averages: 2.00, 1.93, 1.86

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.