ok this is alittle hard to explain so hopefully someone else is familiar with it.
Draw three squares on a piece of paper in a horizontal row. Now draw three below just the same way. The top three represent houses, the bottom three represent power, water, and gas companies. The goal is to connect each service to each house with out crossing any lines.
Is this even possible?
No. Search on “planar graphs” for a detailed explanation as to why.
G’day
This puzzle can be solved only if you run one of the services under some of the houses or companies.
eg. Take the service from the company on the left, run it in to the house on the left and though the squares representing the houses in a horizontal line. Then take the middle company, and run its services into the lower sides of the houses. Then take the company on the right, run its services around in a loop to the right and into the top sides of the houses.
Regards,
Agback
It’s supposed to drive you mad. That’s the point; it’s impossible.
Provided that the restriction against crossing any lines means only that none of the utility lines can cross, then the puzzle can be solved without making any assumptions about lines passing over one another, or being underground, or the like.
Here is one way of doing it:
For ease of reference, mark the houses going from top to bottom as A, B and C. Number the squares representing utilities from left to right as 1, 2, and 3.
Utility 1 can be connected to each of the houses my drawing lines to the left side of A, B and C.
Utility 2 can be connected to House A by drawing a curving line which begins at the bottom of Square 2 and then arcs around on the outside of the three lines extending from Square 1. Utility 2 can be connected to House C by a simple straight line. Utility 2 and House B can be connected by drawing a line which loops around from the right end of the top of Square B to the right side of House B.
Utility 3 can be connected to Houses A and B by drawing lines from Square 3 to the left sides of Houses A and B.
This leaves only the problem of connecting Utility 3 and House C
If the rule against crossing lines refers only to crossing utility lines, one can draw a line from the bottom of Square 3 and loop it up and through Square 2 and then directly into House C. Alternatively, one can draw a line from the bottom of Square 3 and overlay it on dividing line between Square 2 and Square 3. Arguably this line and the dividing line do not “cross”.
Here’s an earlier thread asking this question.
http://boards.straightdope.com/sdmb/showthread.php?threadid=189117
This person never did say what was supposed to be the “solution.”
Another dubious solution is to make 3 folds in the paper between the houses and the utilities, and then connect one utility to all 3 houses per fold. Unfold the paper and no lines cross, but fold it correctly and the utilities feed the houses as required.
Oh, you silly rabbits!
Everyone who thinks like me knows that power comes into the house is fat string-like things from the poles out back. Gas and water come from underground in tube-like what-cha-ma-callits.
I worked it all out in a 3D CAD program and it was no problem.
Nobel prize to follow…
Place house C inside house B. Problem solved.
Thinking outside the box…
Is this one of these idiotic “outside the box thinking” puzzles? If so make the power transmission beamed microwaves and your problem is solved.
By the end of the 1960s, all domestic power will be supplied by a small atomic reactor underneath the staircase.
You can complete the puzzle if you do it on a donut-shaped 3-d object.
You can’t draw a bipartite K2,3 graph on a planar surface without one line crossing (bipartite K3,3 is the scenario described above). Nor can you draw a complete K5 graph on a planar surface without one line crossing (ie a graph with 5 nodes with edges/lines joining all of the nodes).
You can do it on a donut …mmmmm … donuts.
Provided the ‘houses’ and ‘utilities’ on paper are meant to be representations of an actual 3D situation on this planet, it’s easily done. You just need a really long connection for whichever utility you’re going to route completely around the globe. Right?
Unfortunately, a sphere’s surface counts as a plane for the purpose of drawing a planar graph. Therefore, routing a cable around the globe won’t help you.
Connect all three utilities to house A…run all three to house B FROM house A…run all three FROM house B to house C
All three houses have all three utilities and no lines are crossed
Hey nothing in the question says you cannot do it this way
Please everyone sit back down you’re embarrassing me
In summary:
If you assume the paper is a plane section, a plane or a sphere, the lines are continuous on the paper, and the lines can’t cross the houses, the stations, or be inside each other, then there is no solution (proof on request.)
If you relax any assumption, there is a “clever” solution; either folding the paper, using a paper donut (or, basically, the surface of any 3d shape that isn’t a sphere), being in 3d or higher (now this one’s really trivial), running a line through a house, or utility, or putting line inside another.
The actual routings are relatively easy to think of once you’ve got the trick.
Which answer applies depends on how the question is worded; eg. in this case he doesn’t specify the shape of the paper, so it could be the surface of a donut.
Have I missed anything?
No, no other 3D object will work, other than a donut. Cubes and cones still have in effect 1 surface, like a sphere. A cylander works, but it’s just a thick donut.
Sorry, I should have been clearer - “any shape which isn’t topologically equivalent to a sphere.” I’ve been getting lazy recently.
Any shape that’s basically a blob of plasticine, canonically represented by a sphere, has the same problem as a plane.
Any shape with any hole in (eg. donut, teacup, swiss cheese, probably klein bottle, but that’s not exactly ‘a 3d shape’, etc) should be ok.
Is that better?
Any shape that’s topologically equivalent to a sphere (genus 0) won’t work (cylinders included), but a shape of genus 1 or higher will work.