draw a line from each utility to each house kindof problem: Philosophy Forums

Page: 1 2

draw a line from each utility to each house kindof problem

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 12:02 AM: Subject: draw a line from each utility to each house kindof problem	#1
There is this trick question of how to draw a line from each of 3 houses to each of 3 utilities (water, power and something else, can't remember what) without overlapping. I was wondering if there is some kind of generic algorithm for solving these type of problems, where you have n nodes and e edges, to find out if it is possible without overlapping and perhaps give an instance of such a solution. I'd appreciate it if anyone who aware of any such could tell me.
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

ragus
Tenured Poster

Usergroup: Members
Joined: Apr 23, 2006

Total Topics: 16
Total Posts: 2187

Posted 09/12/09 - 01:09 AM:	#2
Check out Euler's Konigsberg's Bridges Problem
"A word in your ear is like an untethered goat in a field" Wittigenstein

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 01:23 AM:	#3
Thanks for responding although I don't think that's the type of problem I have. If I remember correctly you can't walk around without using the same bridge twice since there's too many "islands" with odd number of bridges connected to it, but this problem I have is the problem of not having two "bridges" cross one another, rather than not crossing the same bridge twice.
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

unenlightened
everything is...

Usergroup: Administrators
Joined: Aug 10, 2007
Location: Wales

Total Topics: 36
Total Posts: 3286

Posted 09/12/09 - 02:47 AM:	#4
I think, although it may not seem so, that your problem is more closely related to the four colour theorem - deep waters indeed.
...most of our actions are the result of the past, or according to a future ideal. That's not action, that is just conformity. J Krishnamurti "Philosophy, to the Philistine, is an evolutionary process, watched over by some sort of brisk dynamic Providence, and culminating in the supreme insight of modern thought." John Cowper Powys

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 03:09 AM:	#5
That's another interesting one, maybe a bit more related but doesn't seem like I can use it. I found out btw these graphs are called utility graphs and have a property called crossing number, which is the number of minimal amount of crossings. Just to add something, even if its not possible to get that number down to 0, I'd like to be able to get a minimal solution. http://mathworld.wolfram.com/UtilityGraph.html
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 03:59 AM:	#6
After staring at it baffled for a while, I noticed that two green lines actually go to the same house, and one house has no green utility. I remember doing this myself, took a while to realize it was impossible.
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

Sherlock Holmes
Initiate

Usergroup: Members
Joined: Jul 26, 2009

Total Topics: 1
Total Posts: 16

Posted 09/12/09 - 04:02 AM:	#7
Heck! you're right - a rushed job! Looks like it's impossible for more than h=2, if h=u. One should be able to prove it if a proof doesn't already exist. Edited by Sherlock Holmes on 09/12/09 - 04:42 AM

unenlightened
everything is...

Usergroup: Administrators
Joined: Aug 10, 2007
Location: Wales

Total Topics: 36
Total Posts: 3286

Posted 09/12/09 - 04:07 AM:	#8
Here is a discussion of the problem, containing a link to a page on crossing numbers. It seems you can do it on a bagel or a mobius strip, but not on flat paper or a roundish planet.
...most of our actions are the result of the past, or according to a future ideal. That's not action, that is just conformity. J Krishnamurti "Philosophy, to the Philistine, is an evolutionary process, watched over by some sort of brisk dynamic Providence, and culminating in the supreme insight of modern thought." John Cowper Powys

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 04:12 AM:	#9
The way I concluded it was impossible was through starting with 3 houses and 2 utilities, and so far there is only one way of connecting them ..w ./\|\ /.\|.\ A.B.C \.\|./ .\\|/ ..p Then the question is where to place the remaining utility, however if you place it outside the wApC cage, you can't get to B, and if you place it inside wBpC you wont get to A, and if you place it inside wApB, you can't get to C.
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

keda
Ijon Tichy

Usergroup: Members
Joined: Jul 25, 2005
Location: Finland

Total Topics: 38
Total Posts: 3642

Posted 09/12/09 - 04:22 AM:	#10
unenlightened wrote: Here is a discussion of the problem, containing a link to a page on crossing numbers. It seems you can do it on a bagel or a mobius strip, but not on flat paper or a roundish planet. Yep, only a trick answer can solve this trick question.
All about making money Free Europe Now How to fix your country In thought, men distance themselves from nature in order thus imaginatively to present it to themselves--but only in order to determine how it is to be dominated - Adorno and Horkheimer

Page: 1 2

Sorry, you don't have permission to post. Log in, or register if you haven't yet.

Euler's Konigsberg's Bridges Problem