Today's video is about a game. You start off with a deck of playing cards that you actually, instead of shuffling it
normally, you flip a half of it over every time you shuffle
so that some of the cards are going to wind up face up and some of them are gonna wind up face down.
(Brady: You're a good shuffler!)
Thank you. I actually have to do it a bunch of times because I truly want it to be
randomised if it's face up or face down. So I don't want exactly 50/50. I want them to be up or down as they may.
Then you pick a number, and we're gonna do it first with a small number.
So give me a number between, say, 5 and 10.
(Brady: Let's go for...6) - 6. So you lay out 6 cards in a row with the edges touching each other.
The objective of the game is to wipe the table of all the cards. The way the game is played is you can draw out
a card only when it's face up.
So right now I've got 3 choices for which card I could start by drawing out. And the second rule
is that when you draw out the card, if it's still touching either of its neighbours you flip over any of its remaining neighbours.
So anything that's still touching it gets flipped over. - (Brady: How do you choose your first card?)
Well, it's kind of like solitaire, you wanna strategise so that you win the game. If you
choose the wrong card it's possible to mess the whole thing up and wind up losing. Say I choose this card right here,
so I draw it out flip over both of its neighbours,
but now this little island right here is actually stuck. No chance of either of these cards getting flipped over,
I can't pull them out,
I'm gonna lose the game.
If you're going to play the game to win
you want to strategise a bit and then, let's say we start off with this Queen. We draw her out,
flip over the two neighbours. This is isolated
but we can draw this one out. And then
let's go ahead and draw this end, flip over this two. Then draw this jack, flip over his neighbours.
And we can draw out each of these remaining two cards.
(Brady: You did it, you won!)
Now I'm going to deal out another six cards and see if we can win the second game.
All right, now I can tell you right now this game is not winnable. Even if I played with optimum strategy
nothing will work. If I try to remove this King
then it would flip over these two cards and I can already see I've made a mistake because
this Island over here is never going to be able to be removed.
So let me undo that. If I try, let's say this ten instead
then I am going to be able to remove this last card in the island. Now if I remove this club,
I can remove the king but whichever of these two cards I remove,
remove the two, flip over this jack;
if I remove the jack, you'll flip over this two and stuck forever. Trust me. You can't win this one.
So if you're playing this game and
you can choose any number of cards to play with, what's the probability that you wind up with a game that's impossible
bo matter how well you play?
I've seen three different
beautiful proofs of this. Two of them are very formal, two of them are the kinds of proof that, if you're familiar with
inductive strategy proof
or breaking down a large game into smaller parts,
you can do fairly, like, formal proofs that way. But I'm going to show you a proof that is
based on jigsaw puzzle pieces instead. One that - it was the first proof I ever wrote and
I have some, I guess nostalgia for it because of that.
So, spoiler, if you play this game a million times
you'll find that approximately half of those times you'll be able to win it, playing perfectly. And
half the times you'll have laid out a scenario that's impossible to ever win. - (Brady: Can you tell by looking at it?)
I can. I can tell just by scanning across the cards once. - (Brady: What are you looking for?)
(What are you looking at to give it away? Or are you not telling me?)
You're looking specifically at the number of face up cards. And you're looking to see if there's an even number of them or an odd number of them
total. And if they're an even number of them
then you're very sad, or you say "ah deal again!"
If they're an odd number you give the green light and you try to play it.
Let's try a slightly larger game this time. Can you pick a number between ten and twenty?
(Brady: Let's go thirteen.)
Thirteen, all right, thirteen cards. - (Brady: So there's five-) - Because they're an odd number of face up cards
if you play this perfectly you'll be able to win. - (Brady: Prove it!)
Excellent, so I'm actually gonna do more than just prove
that this game is winnable, I could do that just by playing it and showing you that I could win.
Instead I'm going to show you a way to prove that for any odd number of face up cards you can win that game.
I could start with
this card right here.
And that would flip both of its neighbours. Then this card, then that would flip this one over so that could be my third.
Okay. Say I go down here for the fifth
and here, something that I really love is going to happen. You draw this card,
you wind up with what I think of as a fuse going down to the left. It just kind of burns down that streak.
And it could also burn off to the right.
So say this is five and go ahead and call this six, seven, eight. Then this card right here,
next, and I'll burn down this streak. Ten, eleven, twelve, thirteen.
I can remove this in this order and just show and you can like move my hands super fast.
We've won! - (Brady: You've done it)
Yes, success. - (All right, cool. Let's reload it.)
Now let's look at the proof for why any odd number of face up cards can be won.
So if you look at this particular sequence, you can see that it follows two rules that match the rules of the game.
Mainly, that if I've got a face up card, then I can draw that before either of its neighbours
or I can draw it out
after both of its neighbours.
But if I've drawn out one of its neighbours and not the other it'll be flipped over and it's stuck. So 5 is
less than both 10 and 6 because of this. If a card is face down then it's stuck initially,
but if I draw one of its two neighbours, either one, in this case
this card gets drawn out first, it'll flip over and I'll be able to draw it out as long as I don't
also draw out the card to the other side of it.
So it has to be before one of its neighbours and after the other.
So face up cards are either going to have to be less than both of the neighbours, or
greater than both of the neighbours. So this one, this one, is less than both.
This 4 is greater than both. Now this 3, this face down 3, it has to be
greater than one neighbour and less than the other so that it's been flipped over exactly once and we can draw it out.
This 3 is greater than 2. At the end here nothing to the right of that
so this card, because it's face up,
absolutely has to be drawn up before its neighbour.
If this card were drawn out first, this would be stuck forever. And on this side, 10 is
less than 11, which is less than 12, which is less than 13. Right here in the centre, 6 is
less than 7, which is less than 8.
So I played a bunch of games when I was trying to figure out how to prove this. Then I looked at
this sort of greater-than, less-than
sequence. And it started to look a lot like a jigsaw puzzle to me. And I realised that all the face up cards looked like
one of two kinds of pieces.
They either looked like these sort of diamond shaped pieces,
or they looked like these kind of concave pieces.
This one here in the centre,
connecting the nine and the four piece, and then for all of the
facedown cards, every single piece looks exactly the same. Double to the left, or double to the right.
So I just made one kind for that and
started putting them in, either moving to the right
or to the left.
And then the two ends are something special. The two ends are
completely forced, based on if it's face up or face down. If it's face down then it absolutely has to be drawn
after its neighbour, because it's stuck to begin with. So greater than makes the piece look like this. On
the other hand if it's face up
then it absolutely has to be drawn before its neighbour. If I drew out this card first this one would get stuck.
So I'd better had drawn that out
before the card next to it. So I created these two pieces for the possibilities of the ends.
All right, so again, we've drawn that one that has five face up cards
so this is going to be solvable. But have no clue
what order will work and I'm gonna show you how to use the pieces
to both see that it's solvable and see what ordering will work.
So starting from the left because this card is face up it has to be drawn out earlier,
so with an order that's less than its neighbour. And this card being face up means that I have a choice. Either
after both of its neighbours or before. So this is after where is a
number on this card that's greater than both of its neighbours. And this one would be before both of its neighbours. And,
well, I'm choosing between these but only one of them agrees with the card to the left of it.
So the choice is actually completely forced. I have to put down this one.
So then moving on, this one's face down, that means it has to be
earlier than one neighbour and less than the other but we already know that it's going to be earlier than this one
which means it has to be
earlier and then less than its right neighbour.
I'm just going to keep going down and for every facedown card
this is the shape that has to be, it's either going to be to the left or to the right,
but it's always going to be forced by what came before it. For face up cards
I have to put down the one that fits next to it's a blue piece just laid. - (Brady: So let's fill it up)
Now it's the moment of truth. We've got one card at the end and two possible pieces. For this face down card
though it has to be drawn out after its neighbour, no choice there. So we'd better
hope that it's number, that the number of its order,
we'd better hope that the order is
larger than the card next to it. In this case it can be, this sign right here
saying that this number can be larger than this number. Therefore
this is the piece that fits. That's good, the green pieces are the ones that go with a face down card on the edge.
(Brady: So it accept- where luckily, luckily it accepts it, it's receiving it?) - Exactly. And if it had happened
to be a face up card here on the edge, meaning that there are six total face up cards, this
wouldn't have worked. This would have had to be
drawn out before its neighbour, it would have been stuck there forever,
meaning that it would need this piece under it, but this piece doesn't fit.
So, I'm very happy that we've got face down card on the edge.
We actually, can actually use this to see how to win the game. In
particular, we can see that the cards that need to be drawn out early are the cards that have the smallest values.
Those are going to be the yellow cards. You can draw those out in either order,
you can do this whole side of the game before this side of the game,
but this card has to be drawn out before both of its neighbours. In fact, any
sequence of removing the cards that follows these rules, for which parts of the order are
earlier or later, is going to be a winning way to play this game.
(Brady: How do you know that you can't deal out an even number of face ups and still make a jigsaw that works?)
I'm very glad you asked that question. There's the question of the day. To help answer the question
let me introduce you to my hedgehog.
(Brady: Aww, what's his name?)
You want me to name him?
Calvin the Hedgehog.
Calvin the Hedgehog is a bit fussy. In particular he likes to go on walks,
but whenever he reaches an arrow, he has to go over it in the way that's aligned with his nose.
So if he's reaching an arrow that points to the left he actually is going to turn around
and start going backwards until he reaches an arrow that faces to the right again and he's gonna switch it and keep going.
(Brady: He can get to the end bottom first, he just has to get to the end?) - Yes he can get to the end butt first. Bottom. Bottom?
He can get to the end bottom first, but he has to reach all the way from the left side to the right side.
And he is
incredibly fussy. So if he ever has to break the rules he's not willing to proceed.
So you asked me why an even number of face up cards wouldn't work, and the answer is if you imagine
Calvin starting at the begin and going over the cards,
every time there's a face up card, including at the very beginning, it causes Calvin to turn.
Now at the end here we can actually figure out which direction he's facing just by looking at how many
face up cards there were. Because those are the only points when he turned. And if he's turned around a even number of times,
so if he starts off going ahead and then turns one, two -
he's back to forward
Three, four - back to forward. So if he turns an even number of times, if they're an even number face up cards, then he's going to be
going the same direction as he started. If he starts on the picture card, then he has to start off pointing to the left,
so walking butt first, and
then every time he reaches a face up card he'll turn around.
This means that if there are an even number of face up cards after this first one, which means an odd number total,
he'll wind up facing backwards at the very end. And if he's facing backwards at the very end, then the last card
absolutely has to be one that fits in with this arrow, an arrow pointing left,
meaning that it absolutely has to be a face down card.
So in total, you'll have an odd number of face up cards. If at the beginning
your first card is face down, well that changes the entire puzzle sequence, all the way across and
you'll have a Hedgehog that gets to start going forward
and then if it passes over an odd number of face up cards,
it will have turned around backwards.
If it passes over an even number of face up cards, it will have turned around so that it's,
you know, backwards, forwards, backwards, turns around until it's facing ultimately forwards again. So replacing this card here with
reverse every single piece in the row,
every red block would become yellow and every blue block would have to change directions.
And by the time you get to the end, you'd need the opposite kind of card in order to complete it.
So ultimately if this one winds up face up, end has to be down. This one down, ends up. And
that's based on the number in the middle.
If the number in the middle is odd
then the ends have to match. If the number in the middle is even then the ends have to be different.
(Brady: Do you ever play this game anymore? Or is playing this game boring because you, because you always know the result now?)
I like to play this game with people who have never played before, because if you give them a long sequence of cards,
even though it might be possible to win it
and you might know how if they're an odd number of face up cards in the middle. If they pick the wrong ones in the wrong order
then they can still lose the game.
And so there's still, you know, some strategy involved and that moment where you realise oh,
they just flipped over that card and I know they're doomed. They don't see it yet
but I know they're doomed. And I guess I like that moment!
[Outtakes]All right. I'm going to ask you to pick a number between 10 and
20, and you're going to say 13.
(Brady: Alright, go on then)
All right, now let's try playing a longer game, pick a number between 10 and 20 this time. - (Brady:14.)