Chapter 2: The Intriguing Utility Problem

Among Dudeney's numerous puzzles, the Utility Problem stands out as particularly captivating. In his book Amusements in Mathematics, Dudeney describes this ancient challenge. To modernize it, he presents a scenario where three houses must be connected to water, heat, and electricity, with the stipulation that none of the utility lines may intersect. The initial concept is straightforward, but layers of complexity lie beneath the surface.

At the beginning of this discussion, I included an example solution that fails because two lines intersect, rendering it invalid. I encourage you to ponder this puzzle and attempt to devise a valid solution yourself. Each house must connect to each utility without any lines crossing.

As illustrated in the image above, we see Dudeney's depiction of the problem. The three utilities—water, gas, and electricity—are positioned above, while the houses are shown below. Dudeney always provides solutions to his puzzles, so let's delve into what he proposed for this one.

This solution is a clever trick! The line connecting House C to the water utility actually runs beneath House A. While this technically resolves the problem, it leaves much to be desired as a satisfactory answer. Dudeney received considerable backlash for this solution, prompting him to later offer a formal proof indicating that no true solution to the Utility Problem exists, making his answer merely a ruse.

Chapter 3: Understanding the Graph Theory Connection

For those familiar with mathematics, this problem resonates within the realm of graph theory, which examines abstract points and their interconnections. The Utility Problem can be represented graphically, where the red dots signify utilities, the blue dots represent houses, and the lines denote the connections. The earlier graph fails to solve the problem, as many lines intersect.

Graph theory has a specific classification system, and this scenario is designated as K₃₃. The inquiry into this question has been extensively explored across various graphs. A graph is termed planar if it can be represented on a two-dimensional plane (like a sheet of paper) without any lines overlapping. Therefore, the Utility Problem essentially queries whether the graph K₃₃ is planar. By asserting that no solution exists, we conclude that K₃₃ is non-planar.

The visual above illustrates a proof: imagine House A is absent. We can establish connections between the three utilities and the remaining two houses without intersections. This indicates that the graph K₃₂ is planar. The image divides the space into three distinct regions, represented by different colors—yellow, pink, and blue. You might want to test this assertion by crafting your own variations.

It’s notable that each utility interacts with two different regions. For instance, water connects to yellow and pink, gas to yellow and blue, and electricity to pink and blue. This principle holds true universally; if House A occupies the yellow region, it can link to water and gas without crossing any lines, but electricity cannot connect without an intersection.

Chapter 4: Exploring Alternative Solutions

While we have established that the Utility Problem is unsolvable on a flat surface, what about in three-dimensional space? Thankfully, this problem can be elegantly resolved in 3D environments. Dudeney's clever solution utilizes this dimension by allowing one of the lines to run beneath a house.

In fact, there are other unconventional surfaces, such as a Möbius strip, where the Utility Problem can also be solved.

The solution here closely resembles our previous attempts on a flat surface. The connections between House A and electricity, as well as House C and water, navigate around the Möbius strip. This visualization assumes the strip is transparent, allowing lines to appear on both sides, which can be confusing without a tangible model.

Additionally, we can solve the Utility Problem on a toroidal shape, akin to a bagel. Remarkably, a bagel is topologically similar to a coffee mug! This understanding simplifies our task: the line between House A and electricity encircles the bagel's far side, while the line between House C and water loops around the bottom, ensuring no intersections occur.

Chapter 5: Conclusion and Further Learning

I hope this exploration has provided you with valuable insights! Engaging with mathematical puzzles like the Utility Problem can lead to exciting avenues of discovery. Should you wish to delve deeper into this subject, I’ve included some helpful links below.

As mentioned earlier, Dudeney's works are freely available online. Project Gutenberg offers a copy of Amusements in Mathematics, featuring 430 problems with solutions! If you’re looking for a fun mental challenge, I highly recommend giving them a try. Just be prepared for some unconventional solutions, such as the one for the Utility Problem, which appears as Problem #251.

Since Dudeney's time, numerous sources of mathematical puzzles have emerged, including a daily puzzle book and the Moscow Puzzle book. Graph Theory is replete with similar challenges, and if you’re eager to learn more, check out my article or explore a free online textbook.

For additional visual resources, I’ve linked several engaging YouTube videos that explore this problem in various contexts.

If you enjoyed this piece, please consider giving it a clap! You may also want to follow me for more content like this or subscribe to my email list, where I share weekly insights into mathematics and science.