Problem of the Fortnight: X marks the spot
You have an n × n chessboard and a marker. You begin by marking an X through some of the squares of the chessboard. Next, you mark an X through all of the squares which share at least two sides with squares already containing an X. You continue marking an X through such squares until there are no more unmarked squares that share at least two sides with marked squares. (Note that adding an X may open the possibility for another X to be added.) Sometimes when you do this, every square on the board will be marked with an X. Other times, the process will stop with some empty squares left over.
See the picture below for the process on a 5 × 5 chessboard with a certain four squares initially marked. In the end, a total of eight squares are marked.
In terms of n, what is the minimum number of marked squares you can start with and still end up with every square on the board marked with an X? Prove your answer.
Rules and guidelines
The Problem of the Week is open to all undergraduate students, regardless of their major.
Written solutions must be received by the Math Department office in Avery Hall 203 no later than 2:00 p.m. on Friday, November 21, 2008. Include your name and e-mail address with your solution.
The person who submits the best solution, judged on correctness, completeness, and clarity, will win a $10.00 gift certificate to the UNL Dairy Store. The best solution will be posted with the next Problem of the Week on Monday, November 24.
If you have questions, contact Brian Kell at s-bkell1@math.unl.edu.
Winner
The winning solution to this problem was presented Wesley J. Botham.
Other correct solutions were given by Rob Brase and Christopher Haccius.
