Question 62
On an $n\times n$ board, Chris plans to draw three O's. He wants each $\mathbf O$ inside one cell, with the three cells forming an L. The following figure shows examples for $n=4$.
Our aim is to sabotage Chris's plan! We will arrive first and mark some cells with an $\mathbf X$, preventing him from drawing O's there. For example, on a $3\times3$ board we can mark five cells as follows.
We see that Chris cannot carry out his plan.
a) For $n=2$, what is the minimum number of cells to mark with an $\mathbf X$ to sabotage Chris's plan?
b) For $n=3$, find a way to sabotage his plan by marking exactly four cells with an $\mathbf X$.
c) For $n=4$, find a way to sabotage his plan by marking exactly eight cells.
d) For $n=4$, show that it is impossible to sabotage his plan by marking only seven cells with an X. (Hint: use part a).)
Our aim is to sabotage Chris's plan! We will arrive first and mark some cells with an $\mathbf X$, preventing him from drawing O's there. For example, on a $3\times3$ board we can mark five cells as follows.
We see that Chris cannot carry out his plan.
a) For $n=2$, what is the minimum number of cells to mark with an $\mathbf X$ to sabotage Chris's plan?
b) For $n=3$, find a way to sabotage his plan by marking exactly four cells with an $\mathbf X$.
c) For $n=4$, find a way to sabotage his plan by marking exactly eight cells.
d) For $n=4$, show that it is impossible to sabotage his plan by marking only seven cells with an X. (Hint: use part a).)