0
$\begingroup$

Suppose we have a board $100 \times 100$ and place $100$ queens such that none attack another. Prove that each of the four $50 \times 50$ sub-boards (gotten by dividing the board in $4$) contains at least one queen. Additionally, prove that if one of the boards contains exactly one queen, replacing queens by knights would lead to knights attacking each other.

My approach has been to use that each of the row and column must contain only one queen, then utilize pigeonhole principle somehow. Still, I'm not sure how is it possible to place only one queen on $50 \times 50$ board.

$\endgroup$
1
  • $\begingroup$ The question is asking you to show "each subboard has at least one queen," not "at least one subboard only has one queen." $\endgroup$
    – angryavian
    Jun 12, 2021 at 16:55

1 Answer 1

2
$\begingroup$

Each row must contain exactly one queen; each column must contain exactly one queen.

Suppose for sake of contradiction the upper-left subboard contains no queens.

  • This implies that the 50 queens in the upper half of the board must be in the upper-right subboard.
  • This also implies that the 50 queens in the left half of the board must be in the bottom-left subboard.

Since these two sets of queens are disjoint, this accounts for all $100$ queens: all are either in the upper-right or bottom-left subboards.

However, these two subboards contain only $2 \cdot 50 - 1 = 99$ diagonals, so there must be two queens on the same diagonal somewhere. This is a contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .