8
$\begingroup$

This is not original. I just want to share this problem. If you have heard of it, please give opportunities for those who haven't to answer.

Horst and Queenie are playing a game on a $200\times200$ chessboard. At first, the chessboard was empty. Every move, Horst puts a white knight on an unoccupied cell such that no two knights are attacking each other, then Queenie puts a black Queen on an unoccupied cell. The game ends if someone cannot move. How many knights can be placed a most, no matter the strategy of Queenie?

Improve this question
$\endgroup$
1
  • $\begingroup$ So, the upper bound for the lower bound of how many knights Horst can place? $\endgroup$
    – Chronocidal
    Apr 2, 2020 at 16:17

2 Answers 2

Reset to default
8
$\begingroup$

Horst can place

at least 10000 knights

That's because

Horst can simply keep placing knights on white squares, because knights always attack the squares of opposite color. Since there are 20000 white squares on a $200\times200$ board, at least half of them will be available to Horst, even if all other ones will be occupied by the Queenie's queens (since Horst and Queenie alternate their moves).

Note

the upper bound is probably also 10000, because the maximum number of non-attacking knights on a $N\times N$ board is $\mathrm{ceil}(N^2/2)$, and if Horst chooses any other arrangement, Queenie could always tune her strategy by placing her queens on squares unattacked by Horst's knights, thus depriving him of "good" squares.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Correct! Have you heard of this question? $\endgroup$
    – Culver Kwan
    Mar 31, 2020 at 8:25
  • $\begingroup$ @CulverKwan No, I've not. $\endgroup$
    – trolley813
    Mar 31, 2020 at 8:29
  • 2
    $\begingroup$ Still it's not sufficient proof in my opinion.. In detail, why is it true for any X (your answer, to avoid spoiler) white knight positions, there's only a single way for black to cancel the (X+1)th position? Why is it impossible to "deceive" the second player? If we want to see your strategy of the lowerbound, why is this not correct: suppose you put X knights on white squares, and the second player will put another X on white squares, why can't you put any additional piece on black square as maybe, just maybe, it can't attack other knight but only attack queens? $\endgroup$
    – athin
    Mar 31, 2020 at 10:20
  • 2
    $\begingroup$ @athin On a 4×4 board, Queenie can always place a queen in the position that is a 180 degree rotation from Horst's last move. After four such moves, all unoccupied positions will be attacked by a knight. The 200×200 is simply 2500 separate 4×4 boards. $\endgroup$
    – Daniel Mathias
    Mar 31, 2020 at 11:20
  • 1
    $\begingroup$ @oerkelens: yes, if Queenie is cooperative the upper bound is twice as high. This answer assumes Queenie is trying to minimize the number of knights that can be placed. $\endgroup$
    – Ross Millikan
    Mar 31, 2020 at 15:28
-3
$\begingroup$

The question doesn't say that the queen has to go onto an unattacked square.
This means that the upper bound is

20,000

because

there are 40,000 (200x200) squares on the board. If Horst places his knights on white squares, and Queenie uses the black squares, then the board will be completely filled, with 20,000 knights and 20,000 queens.
With optimal play by Queenie, the limit is 10,000, as given in the answer above. With non-optimal play the answer is 20,000. so, the range of pieces that can be placed by Horst will be in the 10,000 to 20,000 range

Improve this answer
$\endgroup$
4
  • $\begingroup$ The question asks for the maximum "no matter the strategy of Queenie", i.e. even if queenie does not cooperate. $\endgroup$
    – Jaap Scherphuis
    Mar 31, 2020 at 17:36
  • $\begingroup$ and the maximum is as my answer. the chances of Queenie doing that are slim to none, but that doesn't alter the maximum $\endgroup$
    – SeanC
    Mar 31, 2020 at 17:40
  • 1
    $\begingroup$ Your answer is the best you can get if Queenie cooperates, but the question is about the best that you are guaranteed to achieve regardless of Queenies moves, i.e. the worst case.scenario. $\endgroup$
    – Jaap Scherphuis
    Mar 31, 2020 at 18:11
  • $\begingroup$ The answer above gives the minimum, not the maximum, assuming optimal play by Horst. $\endgroup$
    – SeanC
    Apr 2, 2020 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.