Annoying Knights

Logic Level 2

Dan and Sam play a game on a $5\times3$ board. Dan places a White Knight on a corner and Sam places a Black Knight on the nearest corner. Each one moves his Knight in his turn to squares that have not been already visited by any of the Knights at any moment of the match.

For example, Dan moves, then Sam, and Dan wants to go to Black Knight's initial square, but he can't, because this square has been occupied earlier.

When someone can't move, he loses. If Dan begins, who will win, assuming both players play optimally?

This is the seventeenth problem of the set Winning Strategies .

Dan Sam Neither of them has a winning strategy

2 solutions

Mateo Matijasevick
May 4, 2016

Relevant wiki: Combinatorial Games - Winning Positions

I will show what Dan has to do in order to win (does not matter what Sam plays):

After the first turn the position is this one

Sam was forced to play his knight to that position because there are not possible remaining squares in which he can place his knight on. I've marked the squares already visited with a red star.

Dan must move his knight to the bottom right corner. Now Sam's options are two squares; I will show each variant:

This one is really simple, because, after this turn, each Sam's move is forced

Each Dan's move must be done in order to enclose Sam's Knight.

After Sam's move, Dan just need to move his knight to the only square where Sam could have placed his knight, and Dan wins

The second variant is a little bit longer, but after some turns, Sam loses

Sam now has 3 squares to place his knight on; two of them are equivalent

And Dan just need to move his knight to the Black knight's remaining square. Thus, Dan wins.

If Sam plays

The result is the same as in previous option.

Finally, Sam can play

And so Dan simply plays

In the next turn, Sam can't move. Sam could have moved to another square, but then the result is the same.

Therefore, Dan wins.

Well a little question : does that imply the first mover is always the winner here ?

Arnav Das - 5 years, 1 month ago

That's what a winning strategy means: steps that you have to follow in order to win (assuming players play optimally).

Mateo Matijasevick - 5 years, 1 month ago

However there is a slight possibility that neither will win

Othman Kurdi - 5 years, 1 month ago

Show me that possibility, because I don't see how on the Earth it is possible to draw in this game... if one of them can't move, he simply loses.

Mateo Matijasevick - 5 years, 1 month ago

Kexin Zheng
May 5, 2016

Not sure if this can be considered another correct way to approach the problem, but here's what I thought:

The game starts with 6 free black squares and 7 free white squares. Each time a knight moves, it has to move to a square with the opposite color of the square it was on (i.e. black to white, white to black). Since both Sam and Dan's knights start on black squares, after both players' first turn, both knights will be on white squares. Then, after the second turn, both will be on black squares. In this fashion, after the sixth turn (when 6 white squares and 6 black squares have been visited), there will be 1 white square left. And since Dan started the game, it will be Dan's turn again, so he will move his knight to the last white square, leaving Sam no room to move his knight. Thus Dan wins the game.

Is this correct?? Feedbacks appreciated!!

Unfortunately, this reasoning is not correct. It can happen that not all the squares are visited during the match. If Dan plays following this strategy (that is, just play to valid squares and wait for Sam to lose), it is possible that Sam wins enclosing Dan's knight, e.g. in a corner, where Dan could have just one valid square to move on.

Mateo Matijasevick - 5 years, 1 month ago

Ah, I see. Thank you!

Kexin Zheng - 5 years, 1 month ago

My computer search finds 68 possible games, in 36 of them the first player (Dan) wins and in 32 the second (Sam). Dan can make dumb decisions (= not optimal) and lose.

Mateo showed a game with Dan taking C2 first (third column left-right, second row bottom-top). Even if Dan takes B3 first, he can react to Sam's every move with a winning strategy. That is what playing optimally means.

Borut Levart - 2 years, 8 months ago

Annoying Knights

This is the seventeenth problem of the set Winning Strategies .

2 solutions

0 pending reports