Minimum Number Of Rooks

Probability Level 5

Find the smallest positive integer kk for which the following statement is true.

Suppose kk rooks are placed on a 2014×20142014 \times 2014 chessboard. Then, there must exist three rooks, call them r1,r2,r3,r_1, r_2, r_3, such that r1r_1 attacks r2,r_2, r3r_3 also attacks r2r_2, but r1r_1 doesn't attack r3r_3.

Details and assumptions

  • Two rooks are said to attack each other if they lie on the same row or same column.
  • The kk rooks are placed on distinct cells, i.e. a cell contains at most one rook.
  • The given condition must hold for any configuration of kk rooks.
  • This problem is not original.
Image credit: Wikipedia Siren-Com

Problem Loading...

Note Loading...

Set Loading...