From: 3blue1brown
The Utilities Puzzle: K3-3
The “Utilities Puzzle” challenges individuals to connect three distinct houses to three different utilities (gas, power, water) with lines, such that none of the nine total lines cross [00:58:00], [01:05:00], [01:10:00]. Initial attempts often lead to lines crossing or houses becoming “boxed in,” making further connections impossible [02:37:00], [03:22:00].
Mathematical Problem-Solving Strategies
When a puzzle seems particularly difficult, a key problem-solving strategy is to shift focus to a “meta-puzzle”: proving whether the task is impossible [05:02:00], [05:07:00].
Graph Theory Concepts
For understanding difficult math problems like the Utilities Puzzle, concepts from graph theory are essential [05:20:00].
- Graph: A collection of objects (vertices) with connections (edges) between them [05:20:00], [05:29:00].
- Planar Graph: A graph that can be drawn on a plane without any edges crossing [05:43:00], [05:46:00].
- Complete Bipartite Graph (K3-3): The specific graph representation of the Utilities Puzzle, consisting of two sets of three vertices where every vertex in one set is connected to every vertex in the other set [05:52:00], [05:56:00].
Proof of Impossibility on a Plane
To prove the impossibility of solving the Utilities Puzzle on a flat plane, one can analyze the regions created by drawing lines [06:25:00].
A useful problem-solving strategy is to focus on new constructs, such as the enclosed regions [06:50:00], [06:54:00]. A key insight is that each new edge drawn either increases the number of “lit-up” nodes by one or increases the number of enclosed regions by one [08:06:00], [08:11:00].
For the Utilities Puzzle (K3-3), there are six vertices and nine edges [08:38:00].
- Starting with one lit-up node and one region (the entire 2D space) [08:31:00], [08:36:00].
- Five lines are needed to light up the remaining five initially dim vertices [08:43:00], [08:59:00].
- The remaining four lines must each introduce a new region [09:13:00].
- Therefore, a hypothetical solution would cut the plane into five separate regions (the initial region plus four new ones) [09:13:00], [09:18:00].
Furthermore, for a bipartite graph like K3-3, every cycle (enclosed region) must contain at least four edges [09:32:00], [09:37:00].
- If there are five regions, and each requires at least four edges to form its boundary, then the total count of edges (summing edges per region) would be 5 x 4 = 20 [10:14:00], [10:21:00], [10:27:00].
- Since each edge borders exactly two regions, this sum double-counts the edges [10:33:00], [10:36:00].
- Thus, any such graph would need 20 / 2 = 10 total edges [10:41:00], [10:44:00].
- However, the Utilities Puzzle (K3-3) has only nine edges [10:50:00], [10:55:00].
This contradiction proves that the Utilities Puzzle is impossible to solve on a flat piece of paper without lines intersecting [11:01:00], [11:04:00].
Euler’s Characteristic Formula
This proof illustrates a general truth known as Euler’s characteristic formula for planar graphs: the number of vertices (V) minus the number of edges (E) plus the number of regions (R) always equals 2 (V - E + R = 2) [11:35:00], [11:39:00], [11:48:00]. Historically, this formula also applies to convex polyhedra, where faces (F) replace regions (V - E + F = 2) [11:54:00], [11:58:00], [12:01:00].
Solving the Puzzle on a Mug
The puzzle’s setup on a mug provides a crucial hint: the handle [12:21:00], [12:36:00]. A mug is topologically equivalent to a donut (a torus) [12:59:00], [13:05:00]. This means the surface has a hole, which changes the topological properties of the space in which the graph is drawn. The handle acts as a “bridge,” allowing lines to pass over or under other connections without technically crossing on the main surface of the mug [13:55:00], [14:24:00], [14:46:00].
This ability to “hop” lines over or under using the handle circumvents the planar graph restriction, making the puzzle solvable [14:09:00], [15:19:00], [16:30:00], [16:32:00]. The question of where the mathematical proof of impossibility breaks down on the surface of a mug provides a deeper understanding of the role of topology in solving mathematical problems [16:42:00], [16:47:00], [16:52:00].
General Problem-Solving Instincts
Engaging with puzzles, even “toy puzzles,” builds strong problem-solving strategies in mathematics [17:17:00], [17:20:00]. Smart problem solvers actively seek out new challenges, ask new questions, are not afraid to start over, and embrace moments of failure [17:14:00], [17:20:00], [17:23:00].