Problem #PRU-65400

Problems Fun Problems Word Problems Tables and tournaments Chessboards and chess pieces Methods Examples and counterexamples. Constructive proofs Pigeonhole principle Pigeonhole principle (other)

Problem

What is the smallest number of cells that can be chosen on a \(15\times15\) board so that a mouse positioned on any cell on the board touches at least two marked cells? (The mouse also touches the cell on which it stands.)