It's the holiday season, a time of year to bring people together and to do something a little bit different so
Mathologer, here I'm Matt Parker from stand up maths. Hey, this
Is sam from Wendover Productions and half is interesting hi everyone this James Grime from the singingbanana channel
Which Brady reporting for service from numberphile objectivity and various other channels. Hey everyone, my name is Steven Walsh
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 I've been. Hey Grant so a friend just gave me this mug you are gonna be challenged
And I'm just gonna 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 each of the three houses so nine lines in total okay without letting
Any two cross, no two lines crops, is right here if you, wanted to just go straight from power to the house
right
Okay, interesting that is quite a 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
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 gonna muck it up I tend to make bit of a poker square of these things when I when I truck
Say, well 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
There we go. Gas line it's, gonna be easy we're gonna go like this,
wow sound effects are crucial,
I'm not gonna go around the green one don't want to fall for that
I can do another one and now up to five four, go I'm looking at my display over here I should
have put it over there but, oh well. Oh that's good of it
That's your go to the second is okay?
There's no ibly this is easy enough
And 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
Mean that one connected to that one. 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 1 and 2. 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 gonna, do is i'm gonna go to a
Piece of paper this 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
spear
Something like that
Okay, let me i need, bigger, lines bigger bigger space
But 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 i really messed it up okay, to make that at least look, easier i'm gonna go around
here
Around around around around around to to go around the mug with, the gas here, so i'm just gonna go all the way
Around i'm gonna go around
Let's go underneath the handle here
So now it's closed
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
Alright 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 rub it off
Posit, 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 the 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 gonna 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
Now 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 k33 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 and in complete 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 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 beaten all of duty' space
By the end we're going to need, to draw. Nine lines since each of the three utilities gets connected to each of the three 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 each edge is touching 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 her to do that
So there you go bada-boom bada-bing 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 2 in 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. Ok, otherwise, why, would you have brought a, bug over here
This is a valid observation
Maybe use the mug handle, oh?
Yeah, i think i see okay i feel like it has to do something with the handle
And 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 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
Doughnut so to solve this thing you're
Gonna have to use the "torus-ness" of the mug you can have to use the handle somehow
That's the thing that makes this a torus mm-hmm let's take the green
and go
Over the handle here okay?
And then the red can kind of come under nice
My approach is to get as far as you can
with
As far as you can as if you are on a plane
and then
See, where you get stuck so look i'm gonna draw
this
too, 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
messy there you, go and then i'm gonna go on the inside of
the handle go all the way around the inside of the handle and
finally connect
To, the gas company to solve this puzzle just drawing the m. And there's three more connections to go so let's just make them
one
Two and i will 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 it's cheating, well sort of topological puzzles 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, oh?
Oh, my, god am i done
is this over i
think i might've gotten
24 minutes granny says to take 15 minutes
There you go i think i've solved it you haven't success but but, not impossible hard but not impossible this
Isn't it maybe perhaps not the most elegant solution to this problem and 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 not 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 pens not working anymore you can
Go, straight across there in and join it up and because it wasn't drawing you haven't. Had across the lines
Baby, 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 maths kheer 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 and 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 matt's gear 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 the whole 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 and 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 dork
So here i'm in there 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 different configuration, have the same rules and rask 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/3b1b
to them know that you came
From here or even slash 3 b 1 b 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 cut it number three. Ah i'm trapped i've done this wrong, again