Talk:Three utilities problem

I DID IT.

File:Http://i.imgur.com/dEsRuFK.png

— Preceding unsigned comment added by 50.80.170.239 (talk) 17:57, 25 February 2015 (UTC)

You have two connections from E to 3, and no connections from E to 1. —David Eppstein (talk) 18:26, 25 February 2015 (UTC)

Three cottage problem solvable?

As the problem is formulated ("Is there a way to do so without any of the lines crossing each other?") the problem should be solvable with the solution "no".

In order to say that the problem has no solution you should formulate the problem as something like "Find a way to do so without any of the lines crossing each other".

I think the best thing is to just say that the answer is no, there is no such way and keep the original problem formulation.

Just my two cents. --130.238.5.7 08:49, 22 April 2006 (UTC)

The Problem is formulated with unreferenced rules

In the article referenced by Uncle G the 1979 Mathematics Magazine article that explains the long history of the utilities setting[1] the utilities puzzle only has 1 rule, that the lines cannot cross. Why has there been a rule added that states the lines cannot pass through another company or house? By adding that rule it makes the puzzle unsolvable in 2D but I don't know why that rule would be added. The puzzle can be found on the internet without that rule so it should at least be mentioned that some variations don't have that rule.

In the magazine article there are 2 older versions. 1 of the older versions is about 3 families who hate each other but wish to go to the market, the church and a third place. This version does not imply that the path to the church could not pass through the path to the market thus making the puzzle solvable.

The version with paths to wells implies that you can't cross over the stations because they are wells but 2 of the 3 do not.--220.136.176.147 (talk) 16:12, 16 June 2011 (UTC)

According to the external link at Archimedes lab.org the rules do not say that you cannot run a line through a house. Thus the rules are wrong here on Wikipedia. 'Alternative solution 1 Nevertheless, this puzzle is possible to solve by using subterfuge... The only way this can be done without the lines crossing is by allowing one of the lines (it doesn't matter which one) to enter a house or a utility company and then emerge from the building on the other side. In fact, the wording of the puzzle is a bit imprecise and doesn't forbid lines to go through the houses or to use the third dimension!'

According to the rules at cut the knot the rules do not say you can't run a line through a house. 'The puzzle is to lay on water, gas, and electricity, from W, G and E, to each of the three houses, A, B and C, without any pipe crossing another.'

The 3D graph solution is being pushed above all other solutions and thus the rules are being altered. This ruins the usefulness of the puzzle which for me is a simple practice experiment in divergent thinking. With the rules stated properly the easiest solution is a line passing through a house.

Agree

I agree with the above. The historical "water, gas and electricity" puzzle has the intended solution of going through a house. The article would be better with the simpler formulation, and a diagram of the intended solution, as well as a proof that there is no solution with the houses and utilities as points (or a reference to such a proof, since I guess it's already somewhere on the topological part of wikipedia). JoDu987 (talk) 16:24, 15 April 2012 (UTC)

Solution:

I've worked for a pipeline company before. You HAVE to use common sense in this case.

For one: These are NOT 'dots'. These are houses, actual 'area' in squared feet. And two: NO company in their right mind would provide direct lines of service to houses, they try to avoid that since it costs money. Instead they have one 'main-line' that branches off to houses.

And since the houses/cottages occupy 'area' and are NOT 'non-existant/non-area points', the houses can accept branched pipes.

http://en.wikipedia.org/wiki/Image:3-cottage_solved.JPG —The preceding unsigned comment was added by Mix Bouda-Lycaon (talk • contribs) 10:18, 25 January 2007 (UTC).

lol real life objects is not what this puzzle is about. going through "houses" is illegal, they represent points. plus I don't think your solution would apply to electric circuits. 88.240.13.46 16:12, 31 January 2007 (UTC)

Not 'going through' houses, gas and water lines run in the streets while power-lines tower over houses, all having run-off lines to suplly the house with utilities. Nowhere on here specifies to 'represent points'. I'm talking about the literal problem here, not the metaphor of it. This problem is labeled The 3 Cottages, not The 3 Points. My solution works perfectly. —The preceding unsigned comment was added by Mix Bouda-Lycaon (talk • contribs) 06:39, 6 February 2007 (UTC).

well in real world there is no problem supplying millions of houses with utilities, because we live in a 3 dimensional world. but if there were only 2 dimensions, three of your brain cells would not be able to connect with three other cells, or your digestive system would have to have one only orifice or you would be torn apart. this problem is about constraints in two dimensions imo. regards. 88.241.181.163 12:02, 11 February 2007 (UTC)

The problem is meant to be attempted in two dimensions only. Giving it cottages and utilities just makes it a word problem and easier (and more fun) to visualize. In mathematical terms: "Given two distinct sets of three points in a plane, connect each point to all the points in the other set. As long as they are in the same plane, placement of points is arbitrary, even among sets. Is it possible to do this without having the connecting segments intersect?" That is the real literal question, not the metaphor. Adding the other details just makes it colloquial. The point is, in two dimensions, the solution is impossible, a point clearly made in this page.--WPaulB 14:21, 14 February 2007 (UTC)

The reply "I've worked for a pipeline company before. You HAVE to use common sense in this case" is silly and irrelevant, because the true common-sense answer is that this problem just doesn't come up; there's always a practical solution of some kind, usually a simple one. This is a concept in mathematics/geometry/whatever, made easier to visualize by imaginary houses and imaginary utility lines, and the added rules only prevent people from missing the point. It's not an engineering problem and engineering solutions don't count, because the problem is so ridiculously easy even for a novice engineer (using real houses and real utilities) that it's not even worth mentioning. TooManyFingers (talk) 15:42, 30 June 2021 (UTC)

A Popular Game

There's a game based on this idea, played in many a school exercise book. And there's a solution (sort of), if drawn on paper where a line would cross punch a hole draw the line past it on the other side and punch a hole back through to join it to the last house! (no don't take it seriously!--Kingrandomfan (talk) 18:06, 8 June 2010 (UTC))

So the solution is the embedding on a torus! Asmeurer (talk ♬ contribs) 22:36, 11 July 2010 (UTC)

Requested move 25 October 2018

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review. No further edits should be made to this section.

The result of the move request was: Not moved. (non-admin closure) –Ammarpad (talk) 17:17, 1 November 2018 (UTC)

---

Three utilities problem → Utility graph – The current title is a misnomer — this is not a “problem” in any of the senses used in mathematics, at best it could be called a "puzzle" or a "riddle". Most of the article is of interest to graph theorists, therefore i recomment making the graph the primary subject of the article. Nowak Kowalski (talk) 16:15, 25 October 2018 (UTC)

Oppose. Most of the article and most of its sources are about the puzzle, not about the graph. And the puzzle is notable independently of the graph, so at most we could split off the purely graph theoretic parts to another separate article and still have an article about the puzzle. We are not here to correct well-established misnomers; see WP:RIGHTGREATWRONGS. —David Eppstein (talk) 19:16, 25 October 2018 (UTC)

Oppose. This is one of several names that the puzzle goes by. The utility graph is used to analyze the puzzle, but it is not the puzzle itself. I agree with David Eppstein. --Bill Cherowitzo (talk) 02:46, 27 October 2018 (UTC)

oppose. The puzzle (which has no solution) is to prove that $K_{3,3}$ is non-planar. The puzzle and the graph are distinct concepts, each deserving of its own page Robinh (talk) 03:27, 27 October 2018 (UTC)

• Oppose the existing title isn't great, but the suggested new name is worse. Non-planarity of K3,3 might be a descriptive name but is very awkward. power~enwiki (π, ν) 20:32, 27 October 2018 (UTC)

---

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.

"Proof without words"

The "proof without words" section really did help me to understand the situation faster and more clearly. I truly think it's very well done. But I find it a bit comical that the part of it that helped me the most was the paragraph-length caption full of ... words. :) TooManyFingers (talk) 15:24, 30 June 2021 (UTC)

The missing solution

This puzzle is not impossible to solve. One simply routes one of the utilities through the middle house so that "all houses are supplied with all utilities without the lines crossing". There is nothing in the instructions to say that you can't go through a property to reach another, is there? Mjroots (talk) 17:30, 20 December 2021 (UTC)

See the article, section "Changing the rules". This solution is described there, and the requirement that lines not pass through buildings is stated explicitly in the "Statement" section of the problem. The lead is deliberately oversimplified, as leads often are. —David Eppstein (talk) 18:34, 20 December 2021 (UTC)

@David Eppstein: where does it prohibit lines passing through buildings in the statement "Suppose three houses each need to be connected to the water, gas, and electricity companies, with a separate line from each house to each company. Is there a way to make all nine connections without any of the lines crossing each other?" Mjroots (talk) 20:13, 20 December 2021 (UTC)

A couple lines down from there: "An important part of the puzzle, but one that is often not stated explicitly in informal wordings of the puzzle, is that the houses, companies, and lines must all be placed on a two-dimensional surface with the topology of a plane, and that the lines are not allowed to pass through other buildings". —David Eppstein (talk) 20:17, 20 December 2021 (UTC)

So the puzzle is only unsolvable if the instructions are explicit. Mjroots (talk) 20:32, 20 December 2021 (UTC)

The article has an entire section about how it is solvable if you vary what is required. It also states that the through-the-buildings solution was already noted by the first person documented to have published the problem, Dudeney. Did you read any of this? —David Eppstein (talk) 20:54, 20 December 2021 (UTC)

In a plane?

The link on WP's main menu today states, "...it is impossible to draw non-crossing lines from three houses to three utilities (pictured) in a plane?" My initial reaction is to wonder if that is also true if you are in a car or just walking? :-) Just my 2-cents! Thomas R. Fasulo (talk) 20:52, 20 December 2021 (UTC)

Probably "in the plane" would be more accurate wording. But I guess it wouldn't avoid that ambiguity. —David Eppstein (talk) 20:54, 20 December 2021 (UTC)

the Mobius strip solution doesnt work

the mobius strip doesnt work because the blue and yellow line still have to cross ... the only solution is to add another dimension .. allowing one to go through the middle or leave the plane the items are on ... 2607:FEA8:BD1F:5910:804B:D7C7:6F9C:12FE (talk) 21:54, 17 February 2023 (UTC)

There is no crossing on the Möbius strip shown in the illustration. There appears to be a crossing in the drawing, but that is only because you are viewing it projected onto a planar surface (your computer screen). On the strip itself, the curves do not cross. —David Eppstein (talk) 22:06, 17 February 2023 (UTC)