We're gonna play a game called brussels
Sprouts. So let me show you how to play.
We're gonna start with a couple crosses
and here's what we do: so on player 1's
turn they can connect any two of these
free ends. So player 1 might go like
that; and then you need to put a slash
through the curve you've just drawn to
create two new ends like this. So that
would be one players turn, and then
player 2 would go. Player 2 might
connect this end and this end and
draw a slash through and then it'll be
player 1's turn again. Player 1 might
do this - you can't draw through an edge
that's already there; so another turn
might look like this and the game goes
on like that alternating player 1 and
player 2. So the player that wins is
going to be the last person that makes a
legal move. So at some point if there's
no more moves that you can make then the
other player will win. You wanna play?
(Brady: I'll give it a go.) - Maybe we'll use some colors?
I'll play blue you play red. - (Okay, Brady is red.)
So why don't you start? - Okay I will play that.
Okay, I going to do this. So this isn't really a
fair fight because I'm really good at
brussels sprouts. - (Oh you're good at it are you?)
Yeah. - (You've got a good strategy have you?)
Copying me I see.
I am going to do this. - (I will play)
(through the middle here.) - I'll do this one.
Umm, I'll do this.
Yeah, you lost
I'm sorry. You shouldn't feel too bad
about losing, cos as I said I'm really
good at brussels sprouts and actually
it's not really a game, it's more of a
mathematical trick. So no matter how you
would have played I claim that this
game of brussels sprouts was always
going to have eight moves. So because I
had you go first you were always going
to lose, cos the number of moves was even
so player 2 would make the last legal
move. So I want to show you how we know
there's always eight moves because it's
really cool. Okay so let's look at this
picture that we have, our finished game
of brussels sprouts. So I'm gonna do
something, I'm just gonna make these
crosses a little bigger so they're
easier to see, so I'm just gonna fatten
them up a little bit. And I'm gonna call
these dots vertices - let's see did I get
them all? I did. So this kind of picture
that we have here, where we have dots
that are vertices and edges connecting
them, where the edges aren't crossing
over each other, that's what's called a
planar graph. And planar graphs we have
this cool mathematical fact: so for any
connected planar graph like this one the
number of vertices minus the number of
edges plus the number of faces is always
equal to 2. So this is like a really- - (Not 2 factorial?)
Yeah sorry - 2 excitement! Sorry that's not a
factorial, although 2 factorial is 2 so
we'd be okay either way. So I'm enthusiastic about
this bag because it's really cool and
it's useful in lots of different things;
it's called the Euler characteristic. - (That guy Euler.)
Yeah so he did a lot of things including
this. So we have this fact for all planar
graphs and I claim that we can use this
to study the game of brussels sprouts, so
shall we do it? So let's say that we have
a game of brussels sprouts
and it ends after m moves. Okay so this
is just gonna be the number of moves
until the end of the game and I'm gonna
try to show that that number has to be 8.
So if we're going to use the Euler
characteristic we need to count some
things. So we need to count the number of
vertices, edges, and faces. So at the end
of the game I want to count the number
of vertices, the number of edges, and the
number of faces.
Okay so let's figure it out. When we
started the game we had just these two
crosses like this, so we had two vertices
at the beginning. Now what happens when
we make a move? So the first move we
connected two of these ends and we put a
slash through, that creates a new vertex.
So we started with two of them but every
time we do a move we get another one. So
if we have m moves we have 2 plus m of
the vertices - does that make sense? Okay, so, now
I need to count edges. So let's look at our moves
again; so when I make a move I'm drawing
an edge, but then remember I cut it in
half. So actually I drew two edges. We
started with no edges in the beginning,
when we started the game there were
nothing connecting our vertices. So we
had zero edges at the beginning and on
each turn we created two. So at the end
we have two times the number of turns.
Now faces is the trickiest one, so let's
look back at our picture here of our
completed game of brussels sprouts. So
when we count faces, I should have
mentioned earlier, that when you count
faces what is a face? It's these regions
that are bounded by the edges, except
that we also count all of the outside as
one of the faces. So over here I need to
count these faces. So if we look at the
picture at the end of the game, every
face has one free end in it. You know if
it had two free ends in it the game
wouldn't be over because somebody could
just connect those two ends? So we can
only have one free end at the end of the
game. So each face has one of those ends
in it and those things are actually
easier to count; so instead of counting
the number of faces I'll just notice
that's the same as the number of free
ends. - (Teena how do we know there can't)
(be an end state in which there's a face)
(with no free ends in it?) - Yeah you have to
think a little bit about how the faces
are created, so maybe we should look at
like this partially done one. How are the
faces created? Well we get faces when we
add an edge and a slash; and so every
time we're closing off one of those
faces we're automatically getting a
little free end inside it. So there never
exists a face that doesn't have one of
those ends in it, so we just need to know
there can't be more than one. Okay so we
count the number of free ends, and why is
that easier to count? Well at the
beginning of the game how many did we
have? So we had four on each of our
little crosses, so we started with eight
of them. On each turn you use up two of
them right? We use up these two, they're
not free anymore, but we create two more.
So after one turn there are still eight.
And the same thing is true after every
other turn; we use up two of them but we
make two more. So we use up two of them
but we make two more, so there are always-
if you count we still
eight and in fact we always are going to
have eight. So the number of free ends is
eight which means our faces have to be
eight. So maybe we should have done this
one as an example. So in this example for
instance, if we count vertices there are
1,2,3,4,5,6,7,8,9,10 vertices; and I'm
supposed to subtract the number of edges,
there are 1,2,3,4,5,6,7,8,9,10..15 - 16
edges. And I'm supposed to add the number
of faces; so these faces are the
regions so it's 1,2,3,4,5,6,7 but then I
also count everything outside the graph
as a region so 8. And then we get 2, like
we were supposed to. Okay so let's let's
do the Euler characteristic: so I'm
supposed to do the number of vertices
minus the number of edges plus the
number of faces. 2 plus m is the number
of vertices, minus the number of edges,
plus we had eight faces and it has to be
equal to 2 - Euler told us that. So what
do I have? I have 10 minus m is equal to
2, the number of moves is 8. We just
showed that player 2 always wins but
what if you had insisted that you wanted
to go second? Well I still could have won.
Because- I could. - (What would you have done?)
I would have started with 3 crosses instead of 2. So if you
start with 3 then the game ends after 13
moves. And the cool thing about brussels
sprouts is that if we start with n
crosses the game ends after 5 n minus
2 moves. And it's the exact same argument
we just did, just we add another variable
for the number of crosses. So whenever
we start with an even number of crosses
player 2 wins and with an odd number of
crosses player 1 wins.
So what I recommend is you ask somebody
'do you want to play brussels sprouts?' and
you put two down and they'll say sure.
And then you say, do you want to go first
or second? And if they say, you know, I
want to go second then I just say oh
since we already did two crosses let's
add a third one and we'll play with
three. People don't notice because the
game seems like it should have strategy
to it so people mostly are focusing on
the strategy and not assuming that I'm
starting them with a losing situation.