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