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)

GA Review

This review is transcluded from Talk:Three utilities problem/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: The Most Comfortable Chair (talk · contribs) 09:01, 17 November 2021 (UTC)

Hello. I will begin the review shortly. — The Most Comfortable Chair 09:01, 17 November 2021 (UTC)

@The Most Comfortable Chair: Ten days later, any progress? —David Eppstein (talk) 18:53, 27 November 2021 (UTC)

Lead

• Something that stands out to me is the size of the lead. The lead accounts for around 20% of readable text in the article. While it does a decent job of covering all the important aspects in the body of the article, it is somewhat overdetailed and could use some pruning.
• The crossing number — which is one — should be mentioned in the lead. And that the problem is very old perhaps.
  • The crossing number was already mentioned: "Although it is nonplanar, it can be drawn with a single crossing". Anyway, I moved some material from the lead into a new "Statement" section and significantly copyedited the rest, including a mention of its oldness. —David Eppstein (talk) 22:21, 30 November 2021 (UTC)

Puzzle solutions

• "Kullman, however, states that" — "Kullman" should be linked when mentioned first, like it is in "History" (up to you if you want to link it again in that section) — "Kullman (1979)".
  • Linked. —David Eppstein (talk) 07:43, 30 November 2021 (UTC)
• "In the utility graph, $E=9$ and $2V-4=8$, violating this inequality, so the utility graph cannot be planar." — "violating this inequality, so the utility graph cannot be planar." could be phrased better.
  • To violate an inequality is standard language, but I reworded to remind readers what the inequality is, in the process also using different wording here. —David Eppstein (talk) 07:43, 30 November 2021 (UTC)

Changing the rules

• "K_3,3" — Shouldn't it be consistent throughout the article, as $K_{3,3}$?
  • Thanks for catching this; fixed. —David Eppstein (talk) 07:43, 30 November 2021 (UTC)
• "K_3,3 is a toroidal graph, which means it can be embedded without crossings on a torus, a surface of genus one, and that versions of the puzzle in which the houses and companies are drawn on a coffee mug or other such surface instead of a flat plane can be solved." — Instead of "is a toroidal graph", wouldn't "as a toroidal graph" be more grammatically accurate, considering the whole sentence? Or the sentence could be broken down in two or three sentences if you would prefer that.
  • No "is" is the main verb here; everything after "which" is a dependent clause. Changing "is" to "as" would leave the sentence unverbed. But your comment made me notice that the sentence was unnecessarily long (impeding readability) so I broke it up into smaller sentences. —David Eppstein (talk) 07:43, 30 November 2021 (UTC)

Properties of the utility graph

• "3"; "4" → "three"; "four"?
  • Ok, done. —David Eppstein (talk) 07:47, 30 November 2021 (UTC)
• "and obviously they are equal." — Using "obviously" should be avoided. You can either edit it out or rephrase that part.
  • Usually I think it should be avoided, as a tell that someone is handwaving because they don't know how to explain why something is true. In this case I think it really is obvious, (both sides have three vertices; 3=3) but I reworded it anyway. —David Eppstein (talk) 07:47, 30 November 2021 (UTC)

References

• Reference 3; 26 — Can the page range be more specific?
• Reference 17 — Use the full-form of "IFToMM". Also, could it be as a separate parameter instead?
  • Huh? The full form is "12th World Congress in Mechanism and Machine Science (IFToMM 2007)", as already given. IFToMM happens to be an abbreviation for the organization that sponsors the conference (the International Federation for the Promotion of Mechanism and Machine Science), but it is also the abbreviated name of the conference. Many academic conferences have both long names ("World Congress in Mechanism and Machine Science") and short names ("IFToMM"). It is also standard to number the long names and to disambiguate the short names by the year of the conference, as here. The short name is still really the conference name and is the version of the name more often used in informal contexts. In formal contexts like bibliographies one would more typically either use only the long name or both names together like this. WorldCat gives the parts of the title in a different order, but again with both. This variation in the ordering of long names and short names and in whether one includes additional words like "Proceedings of" is also common; compare DBLP for SWAT 2018 with the publisher page for SWAT 2018. I have seen bibliographic metadata styles that put the short name in a |series= parameter but I think that's actually less accurate, for one reason because (as in the SWAT example) conference proceedings often belong to a bona fide book series that should be listed in that parameter. I can add the organization name as publisher, I suppose. —David Eppstein (talk) 08:03, 30 November 2021 (UTC)

My point was that it won't be obvious to readers outside the field what "IFToMM" is. Introducing a link to "International Federation for the Promotion of Mechanism and Machine Science" resolves my concern though. — The Most Comfortable Chair 08:25, 30 November 2021 (UTC)

Ok, but in the SWAT example it might not be obvious in the same way; that's because these short names can come from historical reasons (it used to have a long name with those initials, changed the long name, and kept the same short name). So it doesn't make sense to have a general rule that they should always be expanded. —David Eppstein (talk) 17:54, 30 November 2021 (UTC)

I apologize for the delay. I had almost finished reviewing the article when my laptop crashed, and then it took me a while to do it again. It was an interesting read and it should pass. — The Most Comfortable Chair 17:03, 28 November 2021 (UTC)

@The Most Comfortable Chair: Ok, I think I have addressed all your comments above; please take another look. —David Eppstein (talk) 22:21, 30 November 2021 (UTC)

Final assessment

GA review – see WP:WIAGA for criteria

1. Is it well written?

   A. The prose is clear and concise, and the spelling and grammar are correct:

   B. It complies with the manual of style guidelines for lead sections, layout, words to watch, fiction, and list incorporation:

2. Is it verifiable with no original research?

   A. It contains a list of all references (sources of information), presented in accordance with the layout style guideline:

   B. All in-line citations are from reliable sources, including those for direct quotations, statistics, published opinion, counter-intuitive or controversial statements that are challenged or likely to be challenged, and contentious material relating to living persons—science-based articles should follow the scientific citation guidelines:

   C. It contains no original research:

   D. It contains no copyright violations nor plagiarism:

3. Is it broad in its coverage?

   A. It addresses the main aspects of the topic:

   B. It stays focused on the topic without going into unnecessary detail (see summary style):

4. Is it neutral?

   It represents viewpoints fairly and without editorial bias, giving due weight to each:

5. Is it stable?

   It does not change significantly from day to day because of an ongoing edit war or content dispute:

6. Is it illustrated, if possible, by images?

   A. Images are tagged with their copyright status, and valid fair use rationales are provided for non-free content:

   B. Images are relevant to the topic, and have suitable captions:

7. Overall:

   Pass or Fail:

   The article covers complex information in an accessible manner, and the topic is covered comprehensively. Prose is well-written and it meets the criteria. Thank you for your hard work, and another fine mathematics-related good article. — The Most Comfortable Chair 04:46, 1 December 2021 (UTC)

Did you know nomination

The following is an archived discussion of the DYK nomination of the article below. Please do not modify this page. Subsequent comments should be made on the appropriate discussion page (such as this nomination's talk page, the article's talk page or Wikipedia talk:Did you know), unless there is consensus to re-open the discussion at this page. No further edits should be made to this page.

The result was: promoted by Theleekycauldron (talk) 20:20, 15 December 2021 (UTC)

(

• Comment or view
• Article history

)

• ... that although drawing non-crossing connections from three houses to three utilities in the plane is an impossible puzzle, it has solutions on the torus and Möbius strip?Source: Impossible: Kullman 1979 "it can actually be proved that no solution exists"; torus: Parker 2015, pp. 191–192; Möbius strip: Larsen 1994, p. 292

• ALT0a: ... that although it's impossible to draw non-crossing lines from three houses to three utilities (pictured) in the plane, it is possible on the torus or Möbius strip?
• Reviewed: Template:Did you know nominations/Mary Earle

Improved to Good Article status by David Eppstein (talk). Self-nominated at 23:14, 1 December 2021 (UTC).

• Comment: you'd think I'd have learned my lesson from that time I got absolutely and deservedly smacked for proposing a bad ALT on a math nom, but I think this one could improved; I've proposed an ALT0a that has minor changes and suggested that the image in infobox be used if this hook is ran as a lead (the white background would stand out on the blue highlight of the Main Page). We don't get enough diagrams and puzzles on Did you know, and I think this one would be fun and interesting for readers to try to work out—some will try to work it out, even though they know it's impossible. In fact, I think it'd get more attention if we didn't say that it was impossible upfront, but that's a different ALT. Cheers! theleekycauldron (talk • contribs) (they/them) 03:18, 3 December 2021 (UTC)
  • I formatted the second image and added a border to both. If you prefer them without, feel free to remove the "border" parameters.  MANdARAX • XAЯAbИAM  19:50, 8 December 2021 (UTC)
  • ALT0a looks ok to me, a little less awkwardly worded. We don't generally allow contractions like "it's" in article space, but I guess it's ok in DYK. I took the liberty of adding "(pictured)" to the hook. —David Eppstein (talk) 06:03, 3 December 2021 (UTC)

Diagram of the three utilities problem showing lines in a plane

• Comment: I prefer ALT0a but with "it's" and "it is" made consistent. If, however, it's decided to remove mention of the torus and Möbius strip, I think this version with lines, one pair crossing, is better. Disclaimer: I drew both diagrams (and their brethren). Cheers, cmɢʟee⎆τaʟκ 02:01, 6 December 2021 (UTC)

General: Article is new enough and long enough
New enough: Long enough:

Policy: Article is sourced, neutral, and free of copyright problems
Adequate sourcing: Neutral: Free of copyright violations, plagiarism, and close paraphrasing:

Hook: Hook has been verified by provided inline citation
Cited: Interesting:

Image: Image is freely licensed, used in the article, and clear at 100px.
Freely licensed: Used in article: Clear at 100px:

QPQ: Done.

Overall: I recall seeing this problem in a recent YouTube video; glad it has a GA! I like the hook, but I feel it's trying to squeeze in a little more than it needs to, so my suggestion would be to just go with the simple:

ALT1: ... that it is impossible to draw non-crossing lines from three houses to three utilities (pictured) in a plane?

I think that'll draw readers in, and they can then read about the torus/Mobius/etc. in the article.

For the other review components, everything looks good here, with some elements already covered at GAN. Slightly debatable where there's an inline citation for the hook fact right after it appears in the article, but I think it's fine. Picture is freely licensed own work from Cmglee (heads up that you're Main Page-bound!); we could also go with one of the alternate versions but I like how this one is clean and simple. Hook fact is interesting for either ALT0a or ALT1, and I think it's able to state the problem both completely and concisely (not always an easy task). Just let me know your thoughts on ALT1 vs. ALT0a and this will be good to go. {{u|Sdkb}} ^talk 08:59, 5 December 2021 (UTC)

ALT1 is good to go. I have struck ALT0 ALT0a, which I agree are too complex for the average reader (including me). I have also removed the other image to avoid confusion. Another very good article David Eppstein, thank you. Onceinawhile (talk) 19:29, 14 December 2021 (UTC)

ALT1 to T:DYK/P1

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)