You start off with a deck of playing cards that you actually instead of shuffling it.

Normally you flip 1/2 of it over every time you shuffle said that some of the cards, we're going to find that face up and some of them are gonna wind up face down.

You're a good shuffle, Thank you.

I actually have to do with a bunch of times because I truly want to be randomized it 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 could do it first with a small number.

So give me a number between five and 10.

Let's go for 66 So you lay out six 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 other car the only when its face up, huh?

So right now I've got three choices for which car that could start by drawing out on second rule is that when you draw the card, if it's still touching either of its neighbors, if you flip over any of its remaining neighbors, so anything that's still touching it gets a flipped over.

How do you choose your first car?

What's comes like solitary?

You want to strategize so that you win the game.

If you choose the wrong car, that's possible to mess the whole thing up and winds up losing.

Say, I choose this card right here, so I draw it out.

Flip over both of its neighbors.

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 toe win, you want to strategize a bit.

And then let's say we start off with this queen.

We draw her out and flip over the two neighbors.

This is isolated, but we can draw this one out.

Then let's go ahead and draw this end little over this, too.

Then draw this jacket flip over his neighbors.

Then we can draw out tow each of these remaining two cards.

You want.

Now I'm gonna deal out another six cards on Dhe, 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 the to remove this king, then it would flip over these two cards on like an artist.

You have made a mistake because this island over here is never going to be able to be removed.

So let me undo that.

If I'd fry that said this 10 instead then, uh, I am going to be able to remove this last card in the island.

Now, if I remove this club, remove the king.

But whichever of these two cards I remove, remove the to flip over this Giaka, remove the jacket.

You'll flip over this too, and stuck forever.

Trust may.

You can't want this one.

So if you're playing this game on, you can choose any number of cards to play with.

What's the probability that you wind up with a game that's impossible no matter how well you play?

I've seen three different, beautiful person of us.

Two of them are very formal.

Two of them are the kinds of proof that if you're familiar with the inductive strategy proof or breaking down a large game until smaller parts, you can do fairly like formal proofs that way.

But I'm gonna show you a proof that is a based on jigsaw puzzle pieces.

Instead, One day I was the first proof I ever wrote.

I have some, uh, I guess, nostalgia for it because of that.

So spoiler.

If you play this game a 1,000,000 times, you'll find that approximately half of those times that you'll be able to win it playing perfectly on half the times you'll have laid out a scenario that's impossible to ever win.

Can you tell by looking at it?

I can, uh, I can tell just by scanning across the cards once.

What do you looking for?

What are you looking at to give it away, 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 thumb or an odd number of them total, and if they're an even number of them than that, you're very sad or you say deal again If they're an odd number, you give the green light and you try to play.

Let's try a slightly larger game this time.

Can you pick a number between 10 and 2013?

All right, 13 cards.

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.

Prove it.

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 could win.

Instead, I'm gonna 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 that would flip both of its neighbors.

Then this card on, uh, that would flip this one over, so that could be my third say I go down here for the fifth and here's something I really love is gonna happen to draw this card you end up with what I think of is a fuse.

Going down to the left just kind of burns down that street, and they could also burn off to the right.

So said this is five.

And go ahead and call those 678 then, uh, this card right here.

Next we'll burn down the street.

10 11 12 13.

I can remove this in this order and just show.

And you can, like, move my hands Superfast.

Yes, Well, success.

Now let's look at the proof for why any?

Ah, the number of face up cards could be one.

So if you look at this particular sequence, you can see that follows two rules that match the rules of the game.

Mainly that if I've gotta face up cards, then I can draw that before either of its neighbors, or I can draw that after both of its neighbors.

But if I've drawn out one of its neighbors and not the other, it will be flipped over and stock.

So five is, ah, less than both 10 and sex.

Because of this, if a card is face down, then it's stuck initially.

But if I draw one of its two neighbors, either one in this case this car 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 car to the other side of it.

So it has to be before one of its neighbors and after the other.

So face up cards are either going to have to be less than both of the neighbors or greater than both of the neighbors.

So this one, this one is less than both.

Sport is greater than both of those three is face down.

Three.

It has to be a greater than one neighbor unless than the other.

So that's been flipped over exactly once, and we can draw that.

Three is greater than two at the end here, nothing's the writer of that.

So this car, because it's face up, absolutely has to be drawn up before its neighbor.

If this Carver John at first, this would be stuck forever.

Mom, this sign 10 is a less than 11 which is less than 12 which is less than 13 right here in the center.

Six.

It is Leslie seven, which is less than eight.

So I played a bunch of games when I was trying to figure out how the purpose.

Then I looked at at, uh, this sort of greater than less than sequence and start to look a lot like a jigsaw puzzle to May, and I realized that all of the face up cards I've looked like one of two kinds of pieces.

They either looked like these sort of diamond shades pieces, or they looked like the's a kind of con cave pieces, this one here in the center, connecting the nine in the four.

Piece them for all of the face down 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.

Andi, uh, started putting them in, the either moving to the right or I think I left.

Then the two ends or something special.

The two ends are completely forced.

Oh, based on if it's face up or face down.

If it's faced down, that absolutely has to be drawn after its neighbor because it's stuck to begin with, so greater, then makes the piece look like this.

On the other hand, if its face up that absolutely has to be drawn before its neighbor, if I dropped this card first this one, we get stuck.

So I better had drawn that out before the car next to it.

So I created these two pieces for the possibilities of the engines.

Huh?

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 were their will work.

And I show you how to use the pieces to both.

See that it's solvable.

And see what we're hearing will work.

So starting from the left because this card is face up has to be drawn out earlier.

So with an order that's a less than its neighbour, this card being face up, it means that I have a choice either after both of its neighbors or before.

So this is after where there is a number on this card is greater than both of its neighbors, and this one would be before but of its neighbors on dhe, choosing between the is.

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 space down, that means it has to be a earlier than one neighbor and loss and the other, but we already know that's going to be earlier than this one, which means it has to be earlier and then lesson.

It's right, neighbor intentionally keep going down for every face down card.

This is the shape that has to be.

It's either could be left with the right, but always gonna be forced by what came before it.

For face up.

Cards have to put down that, the one that fits next to the blue piece just laid.

So it's a little.

Now is the moment of truth, for we've got one car that the ends and two possible pieces for this face down card, though it has to be drawn that after its neighbor no choice there.

So we'd better hope that it's number that the number of its order brother hope that the order is larger than the car next to it.

In this case, it can be this sign right here, saying that this number can be larger than this number, for this is the piece that fits that's good.

The green pieces of the ones that go with a face down card on the edge.

So it except well luckily, Luckily, it accepted.

It's receiving it.

Exactly.

And if it had happened to be a face up, occurred here on the meaning that there are six total face up Kurds.

This ah wouldn't have worked.

This would have had to be a drawn out before its neighbor would have been stuck there forever, meaning that it would need this piece under it.

But this piece doesn't fit so very happy that we've got face down card on the edge.

Uh, 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, the cars that have the smallest values there's they're gonna be the yellow cards.

You can draw those out, and either or there 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 neighbors.

In fact, any sequence of removing the cards that follow these rules for which parts of the order our earlier or later, is going to be a winning way to play this game.

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.

That is the question of the day.

To help answer the question, let me introduce you to my hedgehog.

Uh, what's his name?

You want me to name him?

Held in the Hedgehog?

Govern the Hedgehog is a bit fussy.

In particular, he likes to go on walks up, but whenever he reaches an arrow, he has to go over in the way that's aligned with his nose.

So if he's reaching an era that points to the left, he actually it's going to turn it around and start going backwards until he reaches an arrow that faces the right again.

He's gonna Suissa and keep going.

Hey, can get to the end bottom first.

He just has to get Yes, he could get to the end, but first of bottom bottom, hey can get to the end bottom first, but he has to reach all the way from the left side.

That's the right side, Um, and he is, Ah, 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 face up cards wouldn't work.

And the answer is if you imagine Calvin starting at the beginning and going over the cards every time there's a face up occurred, including at the very beginning, it causes Kelvin 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 were the only points when he turned.

And if he's turned around ah, a even number of times.

So if he starts off going ahead and then turns one, too, it's back to forward 34 back to forwards if he turns an even number of times, if they're an even number, face up cards and 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.