BdMO Online Forum

We place some checkers on an $n\times n$ checkerboard so that they follow the conditions :

• Every square that does not contain a checker shares a side with one that does;
• Given any pair of squares that contain checkers, we can find a sequence of squares occupied by checkers that start and end with the given squares, such that every two consecutive squares of the sequence share a side.

Prove that at least $\frac{n^2-2}{3}$ checkers have been placed on the board.

Anindya Biswas wrote: ↑

Fri Apr 30, 2021 5:40 pm

We place some checkers on an $n\times n$ checkerboard so that they follow the conditions :

• Every square that does not contain a checker shares a side with one that does;
• Given any pair of squares that contain checkers, we can find a sequence of squares occupied by checkers that start and end with the given squares, such that every two consecutive squares of the sequence share a side.

Prove that at least $\frac{n^2-2}{3}$ checkers have been placed on the board.

I don't think I am getting the question correctly. If we place one checker in the corner of the board and keep $2$ of its adjacent squares(The ones which share a side) empty and fill out all others with checkers. Then we placed $n^2-2 > \frac{n^2-2}{3}$ but still the condition $2$ doesn't satisfy.

No one?? :'(

Mehrab4226 wrote: ↑

Tue May 04, 2021 10:11 pm

No one?? :'(

We have to show if condition 1,2 satisfies, then the conclusion is, but not necessarily the 2nd condition must be true if the inequality is true