mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2004-05-04, 12:42   #1
n8thegr8
 

11·13·17 Posts
Default 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)
  Reply With Quote
Old 2004-05-15, 11:27   #2
Qbert
 
May 2004

22 Posts
Default

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.
Qbert is offline   Reply With Quote
Old 2004-05-15, 14:24   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

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
wblipp 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
Constant network activity? Maybeso Information & Answers 5 2009-02-07 20:52
Network problem mfgoode Puzzles 19 2007-03-19 15:31
Network LLR Citrix 15k Search 76 2005-09-04 17:32
saving over a network crash893 Software 11 2004-05-06 14:15

All times are UTC. The time now is 00:00.

Mon Nov 30 00:00:00 UTC 2020 up 80 days, 21:10, 3 users, load averages: 1.10, 1.21, 1.28

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.