Why this puzzle is impossible

[Submit subtitle corrections at criblate. com] It's the holiday season, a time of year to bring people together and to do something a little bit different. So... Mythologer here. I'm Matt Parker from Stand Up Maths. Hey, this is Sam from Wendover Productions and Half as Interesting. Hi everyone, this is James Grime from the Singing Banana channel. What's Brady reporting for service from Numberphile, Objectivity and various subchannels. Hey everyone, my name is Stephen Welch, my channel is Welch Labs. I'm from the channel Looking Glass Universe. Grant told me he was sending me a puzzle and a mug. Hey Grant, I am here. I've got a mug and some paper and some markers and I'm ready to do your puzzle. I really should know how to solve this mug because I'm the guy that makes and sells them with Matt Parker. So I've been instructed not to read the directions before starting. Hi Ben. Hi Grant. So a friend just gave me this mug. You are going to be challenged and I'm just going to kind of make you do this on camera to embarrass you. We've got three different houses here, three different cottages and then three different utilities, the gas, the power and the water. Draw a line from each of the three utilities to houses, so nine lines in total. Okay, without letting any two cross. No two lines cross. So right here, if you wanted to just go straight from power to the house, that's a no go, right? Okay, interesting. That is quite the challenge. So nine lines that don't cross. That doesn't even sound possible. I've got my mug. I've got my utilities mug here. Okay, so here it is. Here's my handmade mug. I've even got real coffee in the mug. I mean that, look at that, that's attention to detail. I'm willing to give this a go. I'm just worried I'm going to muck it up. I tend to make a bit of a parker square of these things when I, ooh, when I try, ah, see? Let's just fill in as many as I can and see what happens. I'm sure this will end terribly. So there's one, there's the other. Here we go. Gas line, it's going to be easy. We're going to go like this. Sound effects are crucial. I'm not going to go around the green one. Don't want to fall for that. I can do another one and now we're up to five. We have four to go. I'm looking at my display over here. I should have put it over there, but oh well. Oh, that should go to the, the second house. 57 00:02:18,620 --> 00:02:18,340 Okay, I'll put it to the second house. Presumably, This is easy enough. So we just need to get from here to there. I have one, two, three, four, five, six, seven lines, two to go. So I have that one connected to that one. I need Oh, now we get into trouble. Okay, now I start to see the problem. And there I have made my fatal error in not paying attention. I have boxed in this house right here. As you can see, there's no way to get to it. Gas needs to get to number one and two. And that's the problem because we're cut off. I kind of want to try it on paper. Okay, it's getting really awkward to draw on a mug. I think what I'm going to do is I'm going to go to a piece of paper. This kind of property that you can make lines go from here to here and also all the way around makes it seem like I should be drawing a sphere. Something like that. Okay, I need bigger lines, bigger space. Uh... Now I've just blocked off. How is this possible? This isn't getting anywhere. Let's try again. Water I need to the first and second. What? Oh, I really messed it up. Okay. To make that at least look easier, I'm going to go around here. Around, around, around to two. Go around the mug with the gas here. So I'm just going to go all the way around. I'm going to go around. Let's go underneath the handle here. Over, over, over, over. So now it's close. We just need to figure out how to get that red in there. House number three is all done and good. Look at that. House number three, good to go. So this house has all three and that house has all three, but this one in the middle doesn't have gas. All right, let me try something new. Let me just try an experiment here. Let's, let's be, let's be empirical. What's really nice about the mug is that it's shiny. So if you use a dry erase marker, you can undo your mistakes. You just rub it off.

Pause it. Okay, so there's some very pleasing math within this puzzle for you and me to dive into. But first, let me just say a really big thanks to everyone here who was willing to be my guinea pigs in this experiment. Each of them runs a channel that I respect a lot and many of them have been incredibly kind and helpful to this channel. So if there's any there that you're unfamiliar with or that you haven't been keeping track with, they're all listed in the description, so most certainly check them out. We'll get back to all of them in just a minute. Here's the thing about the puzzle. If you try it on a piece of paper, you're going to have a bad time. But if you're a mathematician at heart, when a puzzle seems hard, you don't just throw up your hands and walk away. Instead, you try to solve a meta-puzzle of sorts. See if you can prove that the task in front of you is impossible. In this case, how on earth do you do that? How do you prove something is impossible? For background, anytime that you have some objects with a notion of connection between those objects, it's called a graph, often represented abstractly with dots for your objects, which I'll call vertices, and lines for your connections, which I'll call edges. In most applications, the way you draw a graph doesn't matter. What matters is the connections. But in some peculiar cases, like this one, the thing that we care about is how it's drawn. And if you can draw a graph in the plane without crossing its edges, it's called a planar graph. So the question before us is whether or not our utilities puzzle graph, which in the lingo is fancifully called a complete bipartite graph, K3-3, is planar or not. And at this point, there are two kinds of viewers. Those of you who know about Euler's formula and those who don't. Those who do might see where this is going. But rather than pulling out a formula from thin air and using it to solve the meta puzzle, I want to flip things around here and show how reasoning through this conundrum step by step can lead you to rediscovering a very charming and very general piece of math. To start, as you're drawing lines here between homes and utilities, one really important thing to keep note of is whenever you enclose a new region. That is, some area that the paint bucket tool would fill in. Because you see, once you've enclosed a region like that, no new line that you draw will be able to enter or exit it. So you have to be careful with these. In the last video, remember how I mentioned that a useful problem solving tactic is to shift your focus onto any new constructs that you introduce, trying to reframe your problem around them? Well, in this case, what can we say about these regions? Right now, I have up on the screen an incomplete puzzle, where the water is not yet connected to the first house, and it has four separate regions. But can you say anything about how many regions a hypothetically complete puzzle would have? What about the number of edges that each region touches? What can you say there? There's lots of questions you might ask and lots of things you might notice. And if you're lucky, here's one thing that might pop out. For a new line that you draw to create a region, it has to hit a vertex that already has an edge coming out of it. Here, think of it like this. Start by imagining one of your nodes as lit up while the other five are dim. And then every time you draw an edge from a lit up vertex to a dim vertex, light up the new one. So at first, each new edge lights up one more vertex. But if you connect to an already lit up vertex, notice how this closes off a new region. And this is a very simple way to do it. You can see how this closes off a new region. And this gives us a super useful fact. Each new edge either increases the number of lit up nodes by one, or it increases the number of enclosed regions by one. This fact is something that we can use to figure out the number of regions that a hypothetical solution to this would cut the plane into. Can you see how? When you start off, there's one node lit up and one region, all of 2D space. By the end, we're going to need to draw nine lines, since each of the three utilities gets connected to houses. Five of those lines are going to light up the initially dim vertices. So the other four lines each must introduce a new region. So, a hypothetical solution would cut the plane into five separate regions. And you might say, okay, that's a cute fact, but why should that make things impossible? What's wrong with having five regions? Well again, take a look at this partially complete graph. Notice that each region is bounded by four edges. And in fact, for this graph, you could never have a cycle with fewer than four edges. Say you start at a house, then the next line has to be to some utility, and then a line out of that is going to go to another house, and you can't cycle back to where you started immediately, because you have to go to another utility before you can get back to that first house. So all cycles have at least four edges. And this right here gives us enough to prove the impossibility of our puzzle. Having five regions, each with a boundary of at least four edges, would require more edges than we have available. Here, let me draw a planar graph that's completely different from our utilities puzzle, but useful for illustrating what five regions with four edges each would imply. If you went through each of these regions and add up the number of edges that it has, well, you end up with five times four, or twenty. And of course, this way over counts the total number of edges in the graph, since each edge is touching multiple regions. But in fact, exactly two regions, so this number twenty is precisely double counting the edges. So any graph that cuts the plane into five regions, where each region is touching four edges, would have to have ten total edges. But our utilities puzzle has only nine edges available. So even though we concluded that it would have to cut the plane into five regions, it would be impossible for it to do that. So there you go, bada boom bada bang, it is impossible to solve this puzzle on a piece of paper without intersecting lines. Tell me that's not a slick proof. And before getting back to our friends and the mug, it's worth taking a moment to pull out a general truth sitting inside of this. Think back to the key rule where each new edge was introducing either a new vertex by being drawn to an untouched spot, or it introduced a new enclosed region. That same logic applies to any planar graph, not just our specific utilities puzzle situation. In other words, the number of vertices minus the number of edges plus the number of regions remains unchanged, no matter what graph you draw. Namely, it started at two, so it always stays at two. And this relation, true for any planar graph, is called Euler's characteristic formula. Historically, by the way, the formula came up in the context of convex polyhedra, like a cube for example, where the number of vertices minus the number of edges plus the number of faces always equals two. So when you see it written down, you often see it with an F for faces instead of talking about regions. Now before you go thinking of me as some kind of grinch that sends friends an impossible puzzle and then makes them film themselves trying to solve it, keep in mind, I didn't give this puzzle to people on a piece of paper.

And I'm betting the handle has something to do with this. Okay. Otherwise, why would you have brought a mug over here and not a piece of paper? This is a valid observation. Ooh, I have one cool idea, maybe. Use the mug handle to be... Oh yeah, I think I see it. I feel like it has to do something with the handle and Okay. because that's our ability to hop one line over the other. I'm gonna start by, I think, taking advantage of the handle because I think that is the key to this. You know what? I think actually a sphere is the wrong thing to be thinking about. I mean like famously, a mug is topologically the same as a donut. So to solve this thing, you're gonna have to use the torusiness of the mug. handle somehow. That's the thing that makes this a torus. So let's take the green and go over the handle here. Okay. And then the red can kind of come under. Nice. And there we go. There you go. I think I did it. All right. Wow. My approach is to get as far as you can with, as if you were on a plane and then see where you get stuck. So look, I'm gonna draw this to here like that. And now I've come across a problem because electricity can't be joined to this house. This is where you have to use the handle. So whatever you did, do it again, but go around the handle. So I'm gonna go down here. I'm gonna loop underneath, come back around and back to where I started. And now I'm free to get my electricity through. I'm gonna go over the handle like that. There we go. Bit messy, but there you go. And then I'm gonna go on the inside of the handle. Go all the way around And finally connect to the gas company. To solve this puzzle, just join the M and there's three more connections to go. Let's just make them one, two, and now we have to connect those two guys, right? Just watch it. In through the front door, out through the back door. Done. No intersections. Maybe you think that's cheating. Well, so it's a topological puzzle, so it means the relative positions of things don't matter. What that means is we can take this handle and move it here, creating another connection. Ho, ho. Oh my god, am I done? Is this over? I think I might have gotten it. 24 minutes. Grant, you said this would take 15 minutes. There you go. I think I've solved it. You're in the success category. Hard but not impossible. This is maybe perhaps not the most elegant solution to this problem. If I drew this line here, you'll think, oh no, he's blocked that house. There's no way to get the gas in, but this is why it's on a mug, right? Because if you take the gas line all the way up here to the top, you then take it over and into the mug. If you draw the line under the coffee, it wets the pen. So when the line comes back out again, the pen's not working anymore. You can go straight across there in and join it up, and because it wasn't drawing, you haven't had to cross the lines. Easy. By the way, funny story. So I was originally given this mug as a gift, and I didn't really know where it came from. And it was only after I had invited people to be a part of this that I realized the origin of the mug, MathsGear, is a website run by three of the YouTubers I had just invited, Matt, James, and Steve. Small world. Given just how helpful these three guys were in the logistics of a lot of this, really the least I could do to thank them is give a small plug for how gift cards from MathsGear could make a pretty good last minute Christmas present. Back to the puzzle though, this is one of those things where once you see it

it kind of feels obvious. The handle of the mug can basically be used as a bridge to prevent two lines from crossing. But this raises a really interesting mathematical question. We just proved that this task is impossible for graphs on a plane. So where exactly does that proof break down on the surface of a mug? And I'm actually not going to tell you the answer here. I want you to think about this on your own. And I don't just mean saying, oh it's because Euler's formula is different on surfaces with a hole. Really, think about this. Where specifically does the line of reasoning that I laid out break down when you're working on a mug? I promise you, thinking this through will give you a deeper understanding of math. Like anyone tackling a tricky problem, you will likely run into walls and moments of frustration. But the smartest people I know actively seek out new challenges, even if they're just toy puzzles. They ask new questions, they aren't afraid to start over many times, and they embrace every moment of failure. So give this and other puzzles an earnest try, and never stop asking questions. But Grant, I hear you complaining, how am I supposed to practice my problem solving

if I don't have someone shipping me puzzles on topologically interesting shapes? Well, let's close things off by going through a couple puzzles created by this week's mathematically oriented sponsor, brilliant. org. So here I'm in their intro to problem solving course and going through a particular sequence called flipping pairs. And the rules here seem to be that we can flip adjacent pairs of coins, but we can't flip them one at a time. And we are asked, is it possible to get it so that all three coins are gold side up? Well, clearly I just did it, so yes. And the next question, we start with a different configuration, have the same rules, and we're asked the same question, can we get it so that all three of the coins are gold side up? And, you know, there's not really that many degrees of freedom we have here, just two different spots to click, so you might quickly come to the conclusion that no, you can't. Even if you don't necessarily know the theoretical reason yet, that's totally fine. So no, and we kind of move along. So next, it's kind of showing us every possible starting configuration that there is, and asking for how many of them can we get it to a point where all three gold coins are up? Obviously, I'm kind of giving away the answer, it's sitting here four on the right, because I've gone through this before. But if you want to go through it yourself, this particular quiz has a really nice resolution, and a lot of others in this course do build up genuinely good problem solving instincts. So you can go to brilliant. org slash 3b1b to let them know that you came from here, or even slash 3b1b flipping to jump straight into this quiz. And you can make an account for free, a lot of what they offer is free, but they also have a annual subscription service, if you want to get the full suite of experiences that they offer. And I just think they're really good. I know a couple of the people there, and they're incredibly thoughtful about how they put together math explanations. Water goes to one, and then wraps around to the other. And naively at this point... Oh, wait, I've already messed up. Then from there, water can make its way to cottage number three. Ah, I'm trapped! I've done this wrong again.