Can You Solve The Knight On A Chessboard Riddle? Math Olympiad Problem

Can You Solve The Knight On A Chessboard Riddle? Math Olympiad Problem

hey this is presto Walker here’s an email I received I really like your YouTube videos and I wanted to send you one of my favorite riddles in my opinion it is somewhat hard but the solution is very cool Alice and Bob are playing a game using a chess board this is an 8×8 grid Alice starts by placing a knight on the board then they take turns moving the knight to a new square one that it has not been on before standard chess rules apply the knight can only move in an L shape that’s two squares in one direction and one Square to the side this is one possible place the knight could go and these are all the other places the knight could go from the original square each time the knight moves it has to move in this L shape the first player who cannot move the knight to a new square loses the game who wins if both players play optimally and what is the winning strategy so I’ll admit this problem stumped me and I could not figure it out I want to thank Sebastian for suggesting this problem and for sending me the solution can you figure it out give this problem a try and when you’re ready keep watching the video for a solution so before I get to the solution I want to mention this problem is an example of game theory a mathematical field where you solve games of strategic interaction Alice’s best move depends on what she thinks Bob will do and Bob’s best move will depend on what Alice did and might do each person is trying to outsmart the other like a cat-and-mouse chase remarkably we can analyze these situations and actually find solutions for some games in this game we can prove Bob can always win no matter how Alice plays how can we do that we will use an interesting concept called a graph coloring proof so let’s prove that Bob can always win this game we start out with our chess board and we’re going to divide it into 8 different 4×2 regions so 1 2 3 4 5 6 7 & 8 so what’s so important about these well let’s analyze one of them in particular suppose the knight is in one of these squares where could the knight go while staying in the same 4×2 region this is the key to the whole problem from a square in a given 4×2 region a knight has only one legal move to stay in the same 4×2 region so from this square there’s only one possible spot the knight could go while staying in this 4×2 region so what we’ll do is we’ll color code these two squares the same color so from either of these squares the knight can only move to the other position this will be true for every single square in this 4×2 region for example from the lower right hand square there’s only one possible place the knight could go from there and vice versa so we’ll color these two the same color we can do it for the remaining squares in this 4×2 region well mark two squares the same color if the knight can move between them now what can this coloring do well it’ll apply to every single one of these four by two regions so from a given 4×2 region we know there’s only one legal move to stay in that same 4×2 region so how does this help Bob win the game Alice starts the game by placing the night in some 4×2 region let’s say she places the night here what Bob will do is he’ll then move the night to the only other legal square in the same 4×2 region now the key is that bob has taken the only other legal square in that 4×2 region this forces Alice to move the night to a new 4×2 region on her next move she cannot stay within the same 4×2 region because these two squares have already been visited so let’s say Alice moves here now where should Bob move well he’s then going to move the knight so the only other legal square in that 4×2 region he applies the same coloring pattern to that region in this case the knight is on a yellow square so Bob is gonna move to the other yellow square as long as Bob continues this strategy he will always have a move and he forces Alice into finding a new 4×2 region on every single move Alice has to keep finding new squares in different 4×2 regions and eventually she will not find one the game has to end in 65 moves or fewer as there a total of 64 squares therefore Bob can always win this game and like magic we’ve solved this problem and shown that Bob can always win did you figure it out thanks for watching this video please subscribe to my channel and make videos on math you can catch me on my blog mind your decisions if you like this video you can check out my books which are listed in the video description and you can support me on patreon if you have a map topic suggestion you can email me presh at mind your decisions calm and you can catch me on social media either at mind your decisions or a presto Walker

100 thoughts on “Can You Solve The Knight On A Chessboard Riddle? Math Olympiad Problem

  1. The great Simon Singh tweeted this video! Here's the tweet:

    Simon Singh has written some of the best popular books on mathematics, including "Fermat's Enigma" and more recently "The Simpsons and Their Mathematical Secrets" (which I received as a birthday present, since my friends know I enjoy his books). Do check out his books!

  2. Did Anyone Else Notice He Messed Up A 4×2 He Did 4 Vertically When Its Supposed To Be 4 Horizontally

  3. so the rule is "the knight can not go were it has been on before" but, in the explaination, at the 4th move it moves were it has been at the start. so either the rule is insufficient or the explanaition is wrong.

  4. The optimal strategy would be
    1. Alice places the night in any 4×2 region,
    2. Bob moves the knight to the only legal position in that same 4×2 region,
    3. Alice is forced to move to a new region
    4. Bob moves back to the first 4×2 region,
    5. Alice does step 2.

  5. My question is:
    1. is there a 50% chance that Alice will ever win? because if not this is not a game. You can call it a game when everyone have a same winning chance.
    2. If Bob does not move his knight in the 4×2 region, but seeking a new 4×2 region, did Alice can win?

  6. You could have just said bob ends in an even number my dude you also should have made the vid 10 mins

  7. There are 64 squares. If Alice starts, she will start with 1, then Bob with the 2 move, and so on and so forth. Alice will represent the odd numbers, and since the last number is an even number, Bob will have the last turn, making Alice loose. My math might not be completely applicable, but the answer is a 100%

  8. This was awesome solution. It would be fun to challenge friends to this knowing that I will always win if I can start tho to make it fair we would need to make turns who starts so I need to also come up with alternative strategy of swaying the tide of the game and blocking some squares. The hardest part tho is to remember which squares we used already, there would need to be some kind of marking every time you visit one..

    The solution I was thinking of is that because there is 64 squares, when one places the knight there are 63 possible squares left and if they would both play optimally, they would use ALL the tiles so that the one who puts the knight to the board would always lose. The problem in this is tho that of course the other player would try block this from happening, but I don't know if it's possible or not to be able to do so if they both play optimally. This would need more thinking and/or trial-and-error method to think about more and I'm too lazy to do that but there's a problem for someone else to solve if they want to. 😀

  9. I just figured that there were an equal number of black and white tiles. That's 2*32. The knight can only move from one color to the other. That creates either a black-white or a white-black sequence that can be repeated up to 32 times. Even if, theoretically, the knight could move to every tile, the person to finish the 32nd sequence would be the winner, as there is no 65th tile to move the knight to.
    This would only prove that Bob wins though, didn't exactly provide a strategy for him.

  10. Actually this is completely wrong. If Bob made the first move, alice would of won. It's like tic-tac-toe. The person who made the first move has a strategical advantage.

  11. Orrrr you can just not make the first move and then you’ll be the person to make the last possible move. Just don’t go first!

  12. I thought of a math visual teaching aid while sitting at my desk with a headache. I know it works but NOT WHY, think you could help me understand? Put both hands in front of you, palms facing you an fingers facing each other but not touching. Make little fingers=6, ring finger=7, middle=8, first/pointing finger=9 on both hands. Example: just touch two 9 (first/pointing) together. (2 fingers touching an all fingers below are valued at 10 each). So two 9 fingers plus all below (6 fingers) equals 8 finger times 10 each for value of 80. Now you have two thumbs (one thumb on each hand) above two fingers touching. MULTIPLY what's above to other hand. ( this case we have one thumb on one hand MULTIPLY one thumb above fingers touching on other hand) 1 thumb times (X) one thumb equals ONE plus 80 is 81 (correct, seems difficult here but very easy). Second example: touch two middle (8s) fingers together. You have two fingers touching plus four below finger touching for tens value of 60. Now MULTIPLY two fingers above to two finger touching on other hand for 4 total= 64 (8X8=64). Third example: 6X9 touch little finger (6) to first finger (9). Two fingers touching an everything below (valued 10s) three below for 50. Now MULTIPLY fingers above to other hand 1X4=4 total (6X9=54) this sounds hard but it's just a visual identity that multiplies all the six through nines. (Note: this even works for tens, try it: two thumbs together for two touching and 8 below for 10X10=100 with no fingers above so no one's! Try this is saves elementary school students much effect by just putting hands in front of them for identity! BUT WHY DOES IS WORK FOR SIX THROUGH NINE AN what other operations like this could function? [email protected]

  13. I don’t know how I came up with the solution.
    But I did it the exact same way!

    I suck at math!!

    I have always loved chess and have played since I was 5!!

    I divided the board into 8 4×2 squares just as they did here and realized that the second player will always win as there are an even number of moves to be made in the game before it ends!

    I feel like a flipping genius right now!!!!!!


    EDIT: I think the fact that I solved it and didn’t need to pause the video was why I am so ecstatic right now!!


  14. Duck. I thought Alice always wins, but her putting the knight on the board is her first move. If the chest piece was already there (randomly) and THAN Alice's first move was to move it, than Alice would always win.

  15. My solution was much simpler! If the object of the game is to always find a new square, then Bob will always win because Alice has fewer squares to play with! As she starts the game by placing the knight on a square, she will always have fewer squares to move to!

  16. I found a way for alicia to win.
    She starts the game on the bottom purple square then Bob uses the corresponding color for his move then she moves to a new section but what if Bob then moves to the blue square in the previous section and then alice goes to the other blue square from this point Bob is now forced to always move to a new section

  17. Simple. The solution is to finish the video and re watch it with the solution in mind. Boom. Case closed.

  18. Maybe i'm wrong (or i missed something) but you left out some info, that the original square the knight starts on can be visited again as you do that in the example.
    For me "you can't visite a square again" implies the first position before people do a move is also one (which would implie the oposite result)

  19. So you are saying that whoever takes the first move and their opponent using this strategy wins? Can the first mover win?

  20. I'd like to see the solution where you move 65 times on a 64 square chess board without being on a square twice.

  21. if bob would be the 1st one to put the horse and alice accidentally did 1 legal move (inside 4×2). can bob counter it if he change it to 2×4 box strat? can anyone confirm?

  22. Hey I hate to break it to you but bob can't do that last move you showed. That's were the piece started. If it happened like this then alic would get the upper hand and Bob would loose.

  23. Why is the same logic not applying to Alice. She can use the same tactics by 90 degree rotation the 4×2 box. Shouldn't we see a draw, or is the advantage on the beginner side?

  24. There is just 1 problem to your solution. The knight start at 1 spot and for example in your showcase Bob could not usw that place because that was the starting place for the knight. (at 5.45 you moved it to the place were it should start befor Alice make her first move)

  25. The solution is actually so simple I thought it was too easy to be right… literally choose one of the 8 squares. Bob goes first, so one of the squares will be taken. From there, just count the squares off naming them Alice and Bob, then whoever has the last square wins.

  26. But why would that work? After those 8 regions are gone only 16 tiles were used and thus there are still plenty of opportunities to place it? What is beneficient for bob to stay inside it?

  27. If you follow the example moves the video shows, the moves end when Bob actually moved the chess piece back to where it started. So technically bob lost because the piece went into a space it was in before.

  28. What if Alice starts by moving to the corect colorcoded square, then Bob must enter another zone. What will it happen?

  29. Well, this riddle is miles ahead from the entire Bright side riddles and 7 sec riddle channel

    *Edit: i wrote that comment before watching entirely. In the end, the solution is really good

  30. Math say that Bob can win, But don't forget that math say that if you flip a coin it will be 50% chance for eighter side to be up at landing, But we all know that is not true. So, can YOU really win playing like Bob did?

  31. Wow, the solution is so simple once it’s explained, even though the question itself seems so difficult to prove

  32. If both sides play optimally the game will end in 33 moves as the knight always moves to the opposite colour and there are nly 32 squares of each colour

  33. This is a good model for a pyramid sceme – in any given metropolitan area, the schemer sells her products to a set of people (the first knight square visit) and then that set of people sell the product to a set of their friends in the same metro area (the second knight square visit). After this, the metro area is inundated and the schemer has to move on to another metro area. Unlike a chess board, though, with a big enough board (metro areas) she can eventually come back (say in 10 years) to her original metro area because by then there will be a new set of suckers to be had. This is how many pyramid schemes keep on trucking decade after decade. We prove (mathematically) that provided there are enough metro areas, and a certain "decay rate" of how "used up" a certain metro area is, that you can actually do a pyarmid scheme indefinitely. Goodness, I like math!

  34. Why can't Alice move knight to old 4×2 region finding new colour in old 4×2 region? If this happens then proof is incomplete

  35. This isn't a complete proof.
    Let's name the grids by using coordinates. The left bottom is (0,0) and the right top is (7,7).That means the range of x and y is 0 to 7. Which means the strategy mentioned would only work in this range. The example in the video shows that Alice chose (1,5) and so Bob chose the corresponding place which is (0,7). The strategy is whenever Alice moves as (x1+a,y1+b), Bob moves as (x2+a,y2+b) onto Alice's corresponding place. But how about Alice moves from (1,5) to (3,6)? Alice moves as x+2,y+1, so Bob will move to (0+2,7+1) which is (2,8). But this exceeds the edge of the game board. In fact (2,8) is not existent. Therefore this strategy is unusable in this situation.

    Actually there must be a strategy which can make one side always win. And every game which doesn't affected by fortune must have a strategy that can lead to inevitable winning for one side. I think although the proof is not completed, it is already very close. The last step is to find out another strategy to deal with the previous problem and make the method in video work again.

Leave a Reply

Your email address will not be published. Required fields are marked *