Conway Checkers (proof) - Numberphile

this is a proof that you can't reach row five in a game of conway checkers it follows on from a main video on the number file channel so you probably should have watched that first if you've landed here and haven't seen that video i'll include links on the screen and down in the video description actually we can start on the board and as a matter of fact i don't even need the line it's distracting for now so at first what i'm going to do is try to create a feature that doesn't changes a so-called invariant if you have seen before pebbling the chessboard the previous video on number file you would know what i'm talking about so if you want you can stop look at it and then come back however if you are up for the challenge let's just do it right away here are two checkers i want some feature not to move so what happens is this checker is going to jump over and then this one will disappear in other words i have two old checkers and one new so whatever is happening for the old checkers should be happening for the new one if that feature is supposed to be an invariant not to change now a very common uh way of creating invariants just like in pebbling the chessboard is to put certain numbers in each cell of the board and those numbers are not random they are powers of something in pebbling the chessboard it was powers of one half but here we are in a much more complex situation powers of what mysterious number do we have to put so we need to do a little bit of a calculation here so let's do it so here we go we have three squares next to each other and we are trying to put powers of some mysterious number x all right so i will put x to the power n the next power x to the power n plus 1 and x to the power n plus 2. so there will be adjacent powers of x the old guys uh those two x to the n and x to the n plus one and the new one is x to the n plus two so what we will do is add up the old numbers and try to get the new one is this possible x to the n plus x to the n plus 1 equals to x to the n plus 2. well there are too many x's so if i want to solve for x i should divide by the smallest power of x so for instance if this were x cubed plus x to the fourth equals to x to the fifth we should simply divide everything by x cubed to get rid of the extra fluffy stuff here so x cubed divided by x cubed is one we have one extra x if i divide x to the fourth by x cubed and two extra x's on the right hand side well this equation starts looking extremely familiar because if i put the lower terms on the other side push them over i will end up with one of the most famous equations in the history of mathematics a simple quadratic equation which is nevertheless famous why is it famous do you know brady because it was in the movie uh well it definitely has been in davinci school that's right what's that number that was in that movie golden ratio golden ratio all over again it keeps popping up everywhere in this world let's see is it indeed a solution to this equation now if you have had very good algebra course in high school you would know the quadratic formula a x squared plus b x plus c equals to zero the two roots of this quadratic equation are minus b plus minus square root b squared minus 4ac over 2a let's try so in our situation x 1 and 2 will be i'm putting the fraction bar b here is negative 1 so negative negative one is just one plus minus square root negative one squared minus four a is here and that's one and c is minus one and all has to be divided by two all right this not so hard we end up with one plus or minus one plus four is five so square root of five and bingo we end up with two possibilities one of them is one plus square root of five over two which is known as the golden ratio and it is denoted by the greek letter 5 and if you wonder about how large this number is it's approximately 1.6 and this golden ratio truly appears in very unexpected places but we have another candidate here the other one x2 is 1 minus square root of 5 over 2 and this is obviously negative it's approximately negative 0.6 it's kind of a twin to the golden ratio but it's the evil one i'll just call it the evil twin yes yes yes let's just do that okay it's the evil twin of the golden ratio and if you actually want a notation for it you can say that it is bar of the golden ratio now could one of those two numbers that came up so naturally from this game be the mysterious x that we will use to place in every single cell the answer is no unfortunately we're not yet there why not well didn't you assume you assumed three four and five at one point ah that's a good question actually the same equation quadratic will come up no matter what you have upstairs because all you have to divide is by the smallest power so if we take this approach we will always come up with those two solutions the reason that none of them works is a very prozac pedestrian reason it just is not gonna do what we want for instance now we are on an infinite chess board not just on three adjacent cells so if i use the golden ratio i will have something that looks like this one in one cell 1.6 or approximately 1.6 1.6 squared 1.6 cubed and this will keep going and going and going on this side i'm going to have probably the negative powers so 1.6 to the minus 1 1.6 to the minus 2 and so on okay now what happens if i add up all of those what number would i get well one plus something that's bigger than one plus something that's bigger than one plus something that's even bigger than that keep on adding and adding and you will end up with infinity so we have a problem i don't want infinity to enter my my computations i'm trying to show that something finite like reaching the fifth row is impossible i don't want that infinity why did we get infinity because the golden ratio was too big for our purposes the golden ratio is bigger than one and that is not enough okay well maybe but like you can't just decide what you want though isn't mathematics like don't you have to just accept what mathematics serves up to you i will define what i like if it does what i want and it's a free country i can put whatever i like in those cells i see that the golden ratio is not going to do what i want so it's not the number for us it looked very promising but it's too big now if we try the evil twin the evil twin is relatively small it is negative 0.6 and if i feed it into a similar argument i can actually come up with a finite number but the problem with this evil twin is that it's negative and remember we wanted a feature that moves only in one direction but what do powers of negative numbers do they flip flop so for instance negative 0.6 is negative and if we raise it to the power of 2 negative 0.6 squared that negative is going to disappear and so you will end up with something positive and this will keep flip-flopping between positive and negative numbers and so eventually we're not going to get our nice monovariant this feature that either only increases or only decreases so we are out of luck here using those two numbers but there is something that is close to them something intermediate that satisfies an almost similar equation that's going to work what could it be it's not the golden ratio it's not the evil twin it is that reciprocal of the golden ratio because the golden ratio was too big if i take its reciprocal that will be less than one and it will still be positive the thing is that people actually know about the golden ratio and they don't know about this other number it's like sitting in the background ready to jump out at any moment and there you go and you will see that it's somehow connected to our helper the number that we're looking for okay but if you were just like making a and if you're just like inverting it now and saying i'm gonna use one over because it suits me better why don't you just use a half or you know naught point three like why don't you just use any old number like if you can just if you're just playing fast and loose now and just saying i'm not happy with that number i'm going to make it smaller how can i make it smaller you could just use any old number it's a very reasonable suggestion extremely reasonable but guess what first of all i have to oblige the rules of the game so somehow i have to stay close to that equation that we obtained don't stray too far from it secondly we actually did see the powers of that mysterious number already here they are 1.6 to the negative 1 that we wrote earlier that's a negative power of the golden ratio but it's a positive power of its reciprocal and 1.6 to the negative 2 is also a positive power of the reciprocal so actually half of what we wrote before is exactly what we need and i am going to replace the other half the larger half that had the golden ratio by a symmetrical uh array of numbers so that everything actually is smaller than one okay but i want to make a point so strictly speaking you don't need to do this calculation but it will link probably what you have done in high school to what we are doing now so i will try to derive a formula for the reciprocal of the golden ratio all right so 1 over 5 is one over what was the golden ratio one plus square root of five yes five or two oh i wrote two look at me so it is square root of five okay so these two goes on top this is what i was thinking about 1 plus square root of 5. and so when you see such nasty things in the denominator you want to rationalize them so you multiply top and bottom by something called the conjugate of them it's almost the same but with a negative sign okay so what is this doing i will have in the numerator what i have 2 times 1 minus square root of 5 but the denominator will become nice there is a formula here at play a minus b times a plus b and that turns out to be a squared minus b squared let me write this down for you a plus b a minus b is a squared minus b squared so by this formula you will have 1 squared minus square root of 5 squared so at the end of the day we are getting to a simplification 1 minus 5 which is minus 4 in the denominator a little bit of cancellation minus 2 and then we flip the sign on top square root of 5 minus 1 over 2. so this is our reciprocal of the golden ratio and if you compute it it will be close to 0.6 does this number remind you of something have we seen it before it's it's it's it's the evil twin except we have taken out the minus in fact that's not a coincidence at all this mysterious number is indeed the negative of the evil twin so it is both the reciprocal of one of the solutions and the negative of the other and for homework you can actually try to prove that i don't need to do it but now we have a pretty good idea of what this number is so i think we are ready to populate our table with powers of this very very useful reciprocal i'm going to call it x once again because this is what we concentrate on so remember we had this infinite board all right and i'm just ignoring the line wherever it is this argument is going to work you need to put to start with one so put your checker anywhere you'd like and we will in that cell right one next to this one i will put powers of x powers of my mysterious number so we start populating the table with powers of x but not only it will be horizontally symmetric but also vertically because we also have vertical moves whatever we do horizontally we should duplicate it vertically and so there you go the pattern is emerging hmm brady what should i put here is that going to be what like x to the 2 or yep that's right that would be x squared this will be x squared x squared x squared but how about here i'm going to put x squared there as well you're absolutely right because the adjacent powers of x are sitting in adjacent cells but that forces us to put right here x squared x squared x squared and now look at this we have a larger square kind of diamond shape turned with x squares and we keep on going so if we go back to the board this is what it's going to look like here my x squared and let's just do one more x cubed and i think the viewer will know what is going on so we will have x cubed x cubed i'm moving along the diagonal because i know i will need those adjacent cells filled with x cubed so what is this thing good for did we achieve our goal to find a monovariant feature we need a little bit of work to see what is going on so imagine you have checkers placed right here in positions x and x squared and you are moving towards one you're jumping like this and then you are freeing this cell okay so our original sum x plus x squared didn't change so we had x squared plus x occupied but after the move only is occupied did this sum change what do you think we are replacing two small numbers all of those powers of x's are actually small numbers because they're powers of 0.6 the sum of two smaller numbers by one this has the hope of actually being equal to one what when x equals 0.6 yes but where is this coming from it is coming from our original equation for the golden ratio so that original equation said that 1 plus x is equal to x squared but then we reciprocated x right so what equation is the reciprocal satisfying all right so here is what we will do a little bit of magic put a question mark here we don't know if this is true but i know that x is the reciprocal of the golden ratio so i'm going to substitute the golden ratio squared plus again the golden ratio its reciprocal is this equal to 1. let's simplify 1 over 5 squared plus 1 over 5 is that equal to 1. let's clear the denominators multiply everything by 5 squared so what do we get here i will get one here i will be having only one phi and on the other side phi squared ah that's exactly our equation for from before one plus the golden ratio is the golden ratio squared so actually this is correct and then everything before that is correct all right so let's start summarizing indeed if i have checkers placed like this and i'm moving towards one the sum is preserved by what we showed how about if i had the checkers here and i'm moving towards one will the sum be preserved yes because this equation is simply multiplied by another x so let me just write this i will have x cubed plus x squared is that x certainly because i just multiplied this equation by x okay but brady what happens if i go vertically would that also work fine um that's right because we made it symmetric so if you move towards one your sum is preserved it's an invariant there is one move though that is very special what if you jump over one i think the sum will decrease because originally you had x plus 1 but then you replaced it just by x so the sum decreased oops so it's not going to be an invariant but it might be a decreasing monovariant so now we put our all of our hopes into showing that what we've constructed is actually a decreasing monovariant so let me backtrack a bit so yes what's a decrease in a variant is just something where then the number can never go up exactly what's wrong with the number well then it's not going to be a mono variant but neither is the decreasing one that's not model variant either the process is a lot more controllable if you start from five and end up going to one you know that we you have traversed this interval only going down without exiting it and doing five seven three jumping up and down and doing something randomly so if you have a function just a general function or a feature you don't want it to go up and down that's very hard to imagine very hard to control very hard to predict but if you know that that feature can never go up then you have a pretty good idea of what's going on in fact you may need only finitely many steps to reach a level where you need to go so backtracking what's happening in the real game is you have some random checkers you know who knows where on this board so you will sum up the numbers of the occupied cells and it is this number that we hope to be decreasing monovariant there is one other type of moves though what happens if you go away from one like this did the sum increase or decrease if i had originally put my checkers on x and x squared and then i replaced this by x cubed let us plug for x 0.6 that's a good approximation so i will have 0.6 plus 0.6 squared is being replaced by 0.6 cubed well which one is larger definitely the left hand side because it contains larger numbers than this very small one so it's decreasing yes is decreasing let's draw one's row here and one's column if you move towards one's column like this no matter where on this grid you are your feature your sum will be preserved it won't change however if you move away it will decrease it will go down the only non-trivial move is if you go over the row or column of one you will decrease by one but that's still decreasing so with after all of this work we actually got our decreasing feature the sum of all of the occupied cells all right so let's go back now to the original problem how do we show that something is impossible we may have seen similar arguments before on other number file videos but basically instead of trying to provide some arguments for why it cannot happen you slow down and say okay well suppose it is possible let's see what will go wrong in other words we are arguing by contradiction so let's say brady tells me yes i can reach row five and then i will ask brady all right so here is my dividing line you will place your checkers underneath and play i don't care about this right now but you show me where is the cell the first cell on row five that you will reach just point to me okay well one two three four that one there okay so i'm going to place a checker there so that's the checker that brady reaches the first one in row five well that's not possible why does brady have enough soldiers enough checkers underneath the line to actually reach there even if brady put checkers all under the line everywhere millions and billions infinitely many okay infinitely many checkers does he have enough fuel to reach the top so imagine this is all filled with checkers infinite all right so if i manage to add up what is on this half of the board i will get some number right let's say i end up with five okay is five good because what do i have here so i didn't tell you where to put the original one i'm going to put the original one exactly where brady claims he has reached row five so that's one right here that's one this is where brady has reached row five and then populate the rest of the table with those powers of x right so let's say i added up then everything underneath the line these are lots of numbers and i ended up with five i don't see a problem because this sum can either stay the same or decrease but all i am trying to reach is one so it's okay well that sum somehow decreased and got to one but is the sum five actually it turns out that if you add up all of those numbers underneath the line you're going to get only one let's see why this is so we need another sheet okay so here is the line and we have how many cells up we have 5 and here is our one this is the cell that brady said he can reach okay underneath we have x x squared x cubed x to the fourth and what we're really interested in is what's happening underneath the line so i'm going to write just a couple of powers here in this central column x to the fifth x to the sixth and here we have x to the sixth here we have x to the sixth and you can keep extending okay so now what we need to do at first is calculate what's happening only on one row and so for that i'm just going to go to the easiest row that has one and use its result later so we have x x squared in this direction and x x squared in this direction right okay so let's start adding just for this row we will have 1 plus x plus x squared plus x cubed and so on and so forth well does this remind us of something this is so so-called geometric series and probably it's a topic that you will study in second semester calculus and such a geometric series actually has a very nice formula when you add it up the formula is 1 over 1 minus x x is the ratio here so in other words every time you move to the next term you are multiplying by this x every time okay now this works only if x is small how small between minus one and one luckily for us our x is approximately 0.6 so we can add up now however this 1 over 1 minus x i don't like it this ratio because it's just very complicated is there a way to simplify it yes because we have a very helpful equation before x squared plus x is equal to 1. and so from here if i pull the x to the other side i have x squared plus x equals to 1. here we are pulling x to the other side we will get more or less what we need here is your 1 minus x i'm going to go up here and substitute instead of it x squared but the story gets even better remember that this x was the reciprocal of the golden ratio so golden ratio is going to come back into our story so what happens if i divide 1 by x squared it will turn out to be the golden ratio squared because you've reciprocated so to summarize half of this row is the golden ratio squared how about the other half we just can't forget that so let's add so the other half is x plus x squared plus x cubed and so on right now i don't really need to repeat this whole calculation here so we haven't got the one anymore no we don't so what do we have to do just subtract one from our previous answer because we are missing it here so this whole thing is our previous answer -1 okay this is all very nice but now we should add them up to get the whole all right so row with 1 adds up to 5 squared plus 5 squared minus 1. now this is pretty complicated where did we get the golden ratio there was another equation for the golden ratio from before and uh it is this equation it looks like the previous one but it's different and here when i put phi squared i end up with 5 squared minus 5 minus 1 equals to 0. so 5 squared minus 1 is put the 5 to the other side is just 5. okay so we are getting somewhere it's not yet exactly what i want but it looks like this expression being replaced by phi this is what i have can i also do something with this yes i can it's exactly the same equation okay so look at this so 5 squared plus five this is some algebraic gymnastics that i'm going to produce is factor out five five plus one what is five plus one five plus one is five squared so there are lots of relationships about the golden ratio that you can extrapolate just from this single quadratic equation so when you substitute this here i have 5 i have five squared so what did they get brady pi cubed done that was the hardest calculation okay so if you are really determined to find how much we have just in row one this is phi cubed this is the golden ratio cubed okay well let's just start writing here in a different pen so row one adds up to 5 cubed what does row 2 add up to now i'm not going to redo the whole calculation it's not necessary but watch this every number on the first row is being multiplied by x to get it to the second row underneath so the sum that we got before must also be multiplied by x but what was x x our mysterious number was the reciprocal of the golden ratio so what happens if i multiply phi cubed by one over 5. let's see phi cubed times 1 over 5 is 5 squared oh thanks look promising how about the next row if i add up what do you really think well it must you must knock another one off the power so it must drop to five exactly because we keep multiplying by the reciprocal of the golden ratio but how about here that's an interesting row that's right five times the reciprocal of it is one keep on going now we drop to the negative powers of five and finally we come to the region where we were interested in the first place this is underneath the line so the first row underneath the line must add up to 5 to the negative 2. we need another picture so we just concluded that if i add up everything on the first low below the line i will get 5 to the negative 2 and then we keep on going 5 to the negative 3 5 to the negative 4 and so on and so forth now we need to add up all of those in order to see what's going on with our army of checkers that we can put here for the whole region underneath the line our answer starts like this you keep adding powers negative powers of the golden ratio now this is just way too complicated let me factor the first one and what will be left 1 plus 5 to the minus 1 plus 5 to the minus 2 plus etc etc but guess what we just computed this a while ago this is 1 plus x remember x was the reciprocal of the golden ratio plus x squared and so on and so forth let's see where was that that was 5 squared so this sum here overall is 5 squared so what is everything under that line it is 5 to the negative 2 times 5 squared well that just one all this computation to get one for adding up this infinitely many numbers underneath our line going back to our chess board here is the line and all of the cells have been somehow populated for the sake of the experiment and we've added all of the numbers underneath the line and we got one can we actually i'm going to move the line because i need one more row on top there you go is it possible for brady to reach row five oh it feels like it is possible now yes just possible just possible yeah because if i as long as i stay as long as i don't vary i can i can stay on one you can so you need to stay on one so i can just get there just get there barely really so tell me after you play all of this so you start with an army that adds up to one you stay constant you land on yourself how many checkers do you end up with one just one can you have more like like for example here no it must be the last move to ask you the final thing i do well that's not the reason though because if you hit more than one of those checkers you have a one here remember the one was on this spot plus something more your thumb will have increased starting from one you ended up with something more than one no because because my fi that's my second to last move and that so as long as that adds up to one yes and then that adds up to one i'm alright so actually you're proving my point all i wanted to say is that at the end of this game there can be only one checker left any extra checker means that the sum is more than one but we can't increase so brady plays with his army of checkers and at the end of the game in order to reach this place he has only this checker left well brady how many moves did you make to decrease your infinite army of checkers to one how many moves was that an infinite number infinite number because every move reduces the number of checkers by one so if you play finitely many moves you will reduce this infinity by finitely many checkers you'll still have infinitely many so there is no way to fit this bigger carpet in a small room no matter what you do is going to pop up in one corner if you you need all of those infinitely many checkers now do you see why because if i have even one removed i will start with the sum that is less than one well i can't get it to one so i need all of the checkers so if i start with an infinite number of checkers i can't get to five i'm just always on the way there you're always on the way there but if you tell me i reached row five then it means the game stopped and you've done it and you've done maybe a billion moves but that's finitely many so it is impossible actually to reach row five well i used to say and i'm still inclined to say occasionally that i hate it i hate the game of life i don't really at least i don't anymore how about we test our skills on finding just the sum of the first row

Channel: Numberphile2

Views: 305,866

Keywords: conway checkers

Id: Or0uWM9bT5w

Length: 41min 54sec (2514 seconds)

Published: Fri Feb 23 2018