Rock2000's blog

By Rock2000, 4 years ago, In English

I was solving this problem. I solved it with my intuition and the solution I thought was also given in the editorial. But I couldn't find proof of this solution anywhere. Can anyone please give me proof for the solution of this problem. Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Consider any sequence of less then $$$n + \left[\frac{n}{2}\right]$$$ moves. Then there will be more then $$$\left\lceil\frac{n}{2}\right\rceil$$$ cells that are used no more than 1 time (Dirichlet principle). This means that there will be a pair of consecutive cells that are used no more than 1 time. Now consider a tank in the cell which is being bombed later. If this tank moves to the other cell, it wont be hit for the second time.