There is a player who controls only a queen, while his opponent controls a knight. Both pieces start from opposite corners of the board. The aim is to kill the knight, without having your queen killed. The board is square, of side $n$.
Case I: The opponent only knows that he should
(a) kill the queen on his current move, if possible
(b) escape to a slot where he can't be killed on the immediate next move
(c) move randomly to any one of the 'safe' slots, as in (b)
Case II: The opponent is a perfect player, and can look into infinite depth and all possible scenarios of the game.
What is the maximum board size for which the queen is 'guaranteed' to win, in Case I and in Case II?
1. In Case I, since moves are random, it is possible that if you can keep coming back to the same position, the knight will eventually make a bad move.
2. 'randomly' means that all 'safe' moves have equal probability, but as the queen's win needs to be guaranteed, this should not affect the answer.
3. There is no limit on moves, time, etc. and no possibility of a draw. 4. The knight always starts.
Since this got answered so quickly, let me make a harder version: The knight is allowed to decide the initial placement of the queen as well as itself. Rest of the question is same.