- Untitled.png (66KiB)Viewed 2714 times
Dhaka regional 16 P2
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: Dhaka regional 16 P2
Lets assume that we can have a maximum of $T$ chocolates. Take the set of all configs that attain $T$. Now, note that,
1. There is such a config for which every row contains at least one choclate. Because if a row doesn't contain any choclate, then if we place a chocolate on it, there would be at most two neighbours of it. But $T$ is maximal, so one other chocolate now has $3$ neighbours. $2$ chocolates can't have $3$ neighbours, because without the new chocolate, then each of them would have $3$ neighbours from the beginning. So, we remove that chocolate. By repeating this, we get a config that contains $T$ chocolates and has a chocolate in each row.
2. Take the config from 1. Now, assume that there is a column that has no chocolates in it. That would mean if we put a chocolate in that column, either it would have $3$ or neighbours or one of the other chocolates would have $3$ or more neighbours. The former can't happen, so the latter must be the case. Due to similar logic of the above, the amount of such chocolates is exactly one. And also, the new chocolate stays in the same row with that chocolate. So, replacing them, we get another config that has maximum amount of chocolates, and contains at least one chocolate in each row and column.
Now, Every row and column contains at least one chocolate. Put another chocolate to a cell. Then we get $T=198$
1. There is such a config for which every row contains at least one choclate. Because if a row doesn't contain any choclate, then if we place a chocolate on it, there would be at most two neighbours of it. But $T$ is maximal, so one other chocolate now has $3$ neighbours. $2$ chocolates can't have $3$ neighbours, because without the new chocolate, then each of them would have $3$ neighbours from the beginning. So, we remove that chocolate. By repeating this, we get a config that contains $T$ chocolates and has a chocolate in each row.
2. Take the config from 1. Now, assume that there is a column that has no chocolates in it. That would mean if we put a chocolate in that column, either it would have $3$ or neighbours or one of the other chocolates would have $3$ or more neighbours. The former can't happen, so the latter must be the case. Due to similar logic of the above, the amount of such chocolates is exactly one. And also, the new chocolate stays in the same row with that chocolate. So, replacing them, we get another config that has maximum amount of chocolates, and contains at least one chocolate in each row and column.
Now, Every row and column contains at least one chocolate. Put another chocolate to a cell. Then we get $T=198$
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.