Problem - 05 - National Math Camp 2021 Combinatorics Test - "Checkers on a board"

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Problem - 05 - National Math Camp 2021 Combinatorics Test - "Checkers on a board"

Unread post by Anindya Biswas » 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.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 05 - National Math Camp 2021 Combinatorics Test - "Checkers on a board"

Unread post by Mehrab4226 » Mon May 03, 2021 9:18 pm

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.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Problem - 05 - National Math Camp 2021 Combinatorics Test - "Checkers on a board"

Unread post by Mehrab4226 » Tue May 04, 2021 10:11 pm

No one?? :'(
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Problem - 05 - National Math Camp 2021 Combinatorics Test - "Checkers on a board"

Unread post by Anindya Biswas » Tue May 04, 2021 11:22 pm

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
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply