So the first thing we're going to do is we're gonna draw some graph. So, I don't care what it looks like,
let's try it, put a few vertices here and some edges,
connect it up nicely,
okay, so there's a graph. And now I'm gonna give each vertex of my graph a number; and again
you can just choose this randomly and it can even be a negative number. Okay, so let's say I've got negative two here,
I don't know, what do you want here?
(Brady: Three)
Three and...
(Brady: One)
One. And how about minus one, and
I don't know, another two. So here's the rules of the game:
the goal is to make sure that none of the vertices have negative numbers anymore.
Okay?
So you can think of this, this - one name for this game is "The Dollar Game"
which is that, you can imagine this is five people and they have this amount of money.
Some of them are in debt, some of them are not. And the moves that you can make in the game
are that either a person can donate money,
meaning for each vertex that they're connected to, they can give a dollar.
Or a person can take money,
meaning for each vertex that they're connected to they can take a dollar. And the goal of the game is to make sure that everyone's out of debt.
(Brady: And no picking or choosing, if you give or take you have to give or take from everyone you're connected to?)
That's right. That's right. So let's take a look at this example that we've drawn here, and see if we can win this game.
So what do you think we should do?
(Brady: Well, I think our three person has to give?)
Good! Okay, so let's do that. Let me do a different colour so we don't get confused.
Okay, so if 3 gives that means 3 goes down to 0,
(Brady: Yep)
2 goes up to 3 ,1 goes up to 2, but here's something good;
which is that this is now negative 1 instead of negative 2, which is better for getting everyone out of debt.
Brady: Alright, we gotta give...
Now, what should we do?
(Brady: That three needs - should give across, shouldn't it?)
Yeah, we've got all this extra money over here
and so why don't we move some of it?
Do you want to move all of it?
We could just do three consecutive moves, moving money over, yeah?
(Brady: So it's okay to be on 0, you don't have to be in surplus?)
Yeah, that's right it's okay to be on zero, you just don't want any debt. So let's do three moves,
each time we'll donate $1 from this vertex to it's only connected guy. Ok, great!
So now we have two problem vertices left, these two minus ones. So what should we try?
(Brady: Why don't we consolidate all the debt?)
Let's try it. So you want to donate-
...oh, sorry, you meant the other way?
(Brady: No that's okay, but move it-)
Well, if this donates... - (Brady: Doesn't he also have to give to there and there?) - ...Oh you're donating the other way...sorry I see what you're saying.
No, let's do what you said. So this thing donates to everyone, so it goes from being minus one to being minus four,
right?
(Brady: Yeah, now this person)
(can give to there?) - Good, good. Yeah, let's get rid of his three.
Okay, so five can give, goes down to two.
One, two, minus two. And then I guess every time we have something here we should move it back, right?
(Brady: Yeah, go on) - Zero and three. - (And now)
(our two up here can do another give.) - Yeah, good. Zero.
Minus 1, 4 - oh, it looks pretty good!
(Brady: We're good, we're done now. All we- all that person with that 4 now has to do one more give.)
That's right, okay, so 1, 1 and zero, okay. - (Brady: And a 1 up here) - Oh and a 1 up here!
Okay, so we won, right? After much, much difficulty. We've got zero and 1, zero,
1 and 1. As we have demonstrated very well here, it's not obvious if we took the optimal strategy to win this game.
It's possible that we could have done fewer moves.
And so one question you could ask is, if you hand me a game like this, if you draw the graph and you assign the
numbers, how few moves can you win the game in?
But before you even ask that question, you might wonder when is it possible to win this game?
Right?
Like if we had started with all negative numbers, then obviously it's impossible because no matter what we try it's not gonna
finish the problem.
Or even, you can think about if we had started with numbers that have the property that they don't add up to something
non-negative, right? Like if the sum of all of the numbers was negative
(Brady: There has to be enough money on the board)
There has to be enough money on the board to get everyone out of debt, exactly.
So there are obviously some constraints for when you can win this game. So let's do a slightly simpler version.
So let's say we just have two
vertices. And we'll connect them by an edge.
Now my question is what kind of money can I put into this game to make it possible to win?
So for example if I have minus 2 here,
let's say, what numbers will work over here to make it a winnable game? And the answer is, well,
as long as I have 2 over here, then I can win. So in this game - so the only thing we need to win is
to have enough money. In other words we've got to have a
non-negative sum in the bank, as you said it,
on the board. Okay.
So let's do something similar here, now with 3 vertices. And now it's not so obvious
exactly if this is still true, right?
I mean, so let's say I have something negative over here, and maybe I don't know negative over here. Again
I want to have enough money on the board so I've got to have at least 3 here.
Let's say I have 4 or something like that.
Then what I can do is I can donate all of the money from the positive vertex to the other 2 vertices,
but because of the way that they're connected I can always balance it between the two of them so that it works.
And so the thing that was true for the two vertex example is also true for this 3 vertex example.
But let's try a different arrangement of
three vertices. It turns out that it's possible in this arrangement to have enough money on the board
but never win the game. And I'm going to show you a way that that can happen.
So if I assign the number 0 here, 1 here, and
minus 1 here.
Then let's think about what's going to happen. So I have enough money on the board, right?
The sum is 0. But if I donate from one of the positive vertices
it will immediately turn negative. And that's true
no matter how many times I try and do it. And so I can never get rid of the fact that we have some negative
vertex in this graph, even though there's enough money on the board. - (Brady: Because you always have to move two at a time.)
Yeah, that's right. Because there's too much connection, right? What's the difference between these two graphs?
It's that I can't move sort of freely between two chosen vertices,
I have to donate all or nothing in the second case. And so it's not enough,
so this is a bad configuration - bad game, not winnable.
It's not enough just to have enough money on the board for all possible graphs.
And so then, okay, the question is can I tell? And it turns out to be really complicated actually to answer this question.
So I definitely advise that you sort of mess around with this a little bit. You can draw any kind of graph you want,
probably you want it to be connected because that makes the game a little bit more interesting. And assign some numbers,
respecting this idea that okay, you've got to have enough money on the board, right? And see what kind of things you end up with.
(Brady: You could have some monster games!)
Yeah, you really could - I mean it depends on your patience level.
But next time you're bored in an airport, which is something I am very often,
that's something that you can do is play this game. Do you want to know the answer, Brady? - (Brady: Yeah.) - Yeah? Okay.
So the full answer is actually really complicated
but let me tell you a partial answer. I can at least tell you that a game is definitely winnable in certain cases.
So there's a special number you can assign to a graph, call this genus.
So the genus of a graph: the number of edges of the graph
minus the number of vertices of the graph
plus one. Okay, very simple to count. So let's check what the genus is in each of these cases.
So in this case the genus is, let's see,
we've got one edge and we've got two vertices, and we add 1 so the genus is zero. In this case
we've got two edges, three vertices, and we add one - and again we get zero. In this case
we've got three edges, three vertices,
plus 1 so the genus is 1. And so this is giving me a way to detect
this notion that I mentioned earlier of being: it's a little too connected, right?
it's too complicated to try and move money around the graph and
this number, which is the genus, gives you an idea of how much complication there is. And so it turns out that you can show
that a graph must be winnable,
there is some way to win this game,
if the amount of money you have is at least as large as the genus of the graph.
(Brady: As in that's your surplus?) - That's your surplus. So here
we knew that the game was winnable exactly when we have zero or more dollars on the board.
We know the game is winnable by what I just said if
the number of dollars on the board is larger than the genus, which is zero. And same here, right?
Because the graph has genus 0, as long as there's at least zero dollars on the board we can win the game.
(Brady: And we had 1. We had positive money on that board)
Yeah, that's right,
but I could have had a three here and it would have worked out, right? And then here in this bad game example
it didn't work to just have zero dollars on the board,
but here's the reason why.
Which is that the genus is 1. And so in order to win the game
you've got to have at least one dollar on the board.
Now the thing that's kind of funny is that it's actually not an absolute characterisation of when you can win the game.
Sometimes you might have less money than you think you need, but you can still win the game. And
actually trying to figure out exactly some nice
characterisation of when you can win the game is pretty complicated.
But even to show,
even to prove that this is true; that if you have as much money as the genus of the graph you can win,
requires some really advanced graph theory. And so I would be really interested to see - I don't think I've given you homework before - I
would be really interested to see a much more straightforward
argument that this is true - that, that having this much money guarantees you a winning set of moves to win the game.
(Brady: What was the genus of our first game and how much money was on the board?) - Oh, that's a good question, let's figure it out.
So, let's see, we've got one two, three four five edges.
We've got five vertices and
we add 1 so the genus in this was 1 also. And what did we start with? We started with
six minus three, we started with three dollars on the board. So we really sort of rigged the game for ourselves,
we should have been able to do better probably.
(Brady: So you could have taken two dollars off the board and we still would have been able to win that?) - And we still woulda-
Which is weird; if you go back and look at this it looks a little difficult, doesn't it?
Yeah. But so that's the guarantee, is as long as you draw your self solitaire graph, which has this property,
there's always a way to win - even if it takes you a long time to find it.
(Brady: I think that is the most interesting thing, is it winnable?)
(But I also think it's incredibly interesting on what the minimal number of moves is.) - Yeah,
so even - I mentioned that is it winnable is complicated to prove.
I don't think that we have a proof or a complete characterisation of what the optimal strategy is for this game.
If you like puzzles and games, like the one you've just seen, why don't you check out today's show sponsor Brilliant.
This is a website full of quizzes and courses; loads of elegantly designed content. This is stuff
that's not only fun to do but it's specially designed to sort of change the way you think,
get you thinking outside the box. Now, there's loads of mathematical content, but I think you might also like this one,
I'm quite excited by it.
Artificial neural networks. Really get your brain around how all this artificial intelligence stuff's working.
There's loads of free content on Brilliant,
but you can get 20% off their premium subscription, which opens the door to everything, by going to
brillaint.org/numberphile. There's the URL on the screen. Our thanks to Brilliant for supporting this episode.