Dhaka regional 16 P2

For students of class 9-10 (age 14-16)
mdhasib
Posts: 10
Joined: Fri Jul 22, 2016 11:43 am

Dhaka regional 16 P2

Unread post by mdhasib » Sun Jan 01, 2017 8:40 am

Untitled.png
Untitled.png (66 KiB) Viewed 1107 times

User avatar
Thanic Nur Samin
Posts: 176
Joined: Sun Dec 01, 2013 11:02 am

Re: Dhaka regional 16 P2

Unread post by Thanic Nur Samin » Fri Jan 13, 2017 1:59 am

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$
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply