Aug 23, 2022

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

Hi, I'm Presh Talwalkar. Here is an email I received. I really like your YouTube videos and wanted to send you one of my favorite

### riddle

s. In my opinion, it is a bit difficult, but the solution is very good. this is an 8x8 grid alice starts by placing a horse on the board then they take turns moving the horse to a new square it hasn't been on before standard chest rules apply the horse can only move in the form of a l which has two squares one direction and one square to one 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 every time the

### knight

moves it has to move in this l shape the first player who can't 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 will admit this

### problem

stumped me and i couldn't work it out.
I want to thank Sebastian for suggesting this

### problem

and sending me the solution, can you

it, try this

### problem

and when you are ready, keep watching the video to find a solution, so before I get to the solution, I want to mention that this

### problem

is an example of game theory, a

#### math

ematical field. where you

#### solve

strategic interaction games alice's best move depends on what she thinks she will do bob and bob's best move will depend on what he did and could do alice each person is trying to outsmart the other like a cat in the mouse chasing remarkably we can analyze these situations and find solutions for some games in this game, we can prove that Bob can always win no matter how Alice plays, how can we do that?
We'll use an interesting concept called the graph coloring test, so let's prove that Bob can always win this game. Let's start with our

## chessboard

and divide it into eight different four-by-two regions, so one two three four five six seven and eight so what's so important about these? Well, let's analyze one of them in part. Suppose the

### knight

is on one of these squares. Where could the horse go while staying in the same 4x2 region? This is the key to the whole

### problem

. From a square in a given four by two region, the

### knight

has only one legal move to stay. the same four by two region, so from this square there is only one possible place the

### knight

could go while staying in this 4 by two region, so what we'll do is color code these two squares of the same color, so so that from any one of these squares the

### knight

can only move to the other position, this will be true for every square in this four by two region, for example from the bottom right square there is 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 four by two region we'll mark two squares the same color if the horse can move between them now what it can do well this coloring will apply to each one of these four by two regions so from a g In a four by two region, we know there is only one legal move to stay in that same four by two region r two, so how does this help Bob win the game?
Alice starts the game by placing the horse in a four by two region, let's say she places the horse. here what bob will do is move the

### knight

to the only other legal square in the same 4x2 region now the key is that bob has taken the only other legal square in that 4x2 region this forces alice to move the

### knight

to a new 4x2 region in her next move, she can't stay within the same 4x2 region because these two squares have already been visited, so let's say Alice moves here now, where Bob should move, so she'll move the

### knight

to the only other legal square in that region of four by two, apply the same coloring pattern to that region, in this case, the

### knight

is on a yellow square, so Bob will move to the other yellow square, as long as Bob continues with this strategy, he will always have a move and forces Alice to find a new 4x2 region every move Alice has to keep finding new squares in different 4x2 regions and eventually won't find one The game has to end in 65 moves or less, because that there are a total of 64 squares, therefore Bob can always win this game and like magic we have

d this

### problem

and proved that bob can always win you figured it out thanks for watching this video please subscribe to my channel and do

#### math

videos you can see me on my blog mindyourdecisions if you like this video you can check out my books listed in the video description and you can support me on patreon if you have a suggestion for a

#### math

topic you can email me presh mindyourdecisions.com and you can find me at social media at mindyourdecisions or at preshtalwalkar
Trending