Problem 17. Shoot the Dragon

-

We have 100 boxes that are arranged horizontally in a line. A dragon is in one of these boxes, however, the box is unknown to us. Moreover, we have a gun and we can use the gun to shoot the boxes and if the dragon is in the box we shoot at, he will die. If the dragon survives a shot, he jumps to either the right box or the left box (if they exist). Is there an algorithm to shoot the boxes one by one that will surely kill the dragon? If not, why? If yes, what is the algorithm?
clarification: The shooting can go on as long as we wish to continue. Each time, we shoot first and if the dragon survives, he makes a move to either the left box or the right box. Keep in mind that dragons are super smart and if there is a way for them to escape the shooting, they will do so.
Link to the problem on Twitter: https://twitter.com/Riazi_Cafe/status/1682276511402037248

-

. First, try to solve the following easier problem: Assume that we know that the starting position of a the dragon is a box whose index is odd. In this case, is there a way to kill the dragon? Is there a way to generalize this idea?

-

. The answer to this question is positive. There is a shooting algorithm that always kills the dragon.
,

Let the boxes be numbered from 1 to 100 from left to right. We start from box 1 and in the first 100 steps, we shoot box number \(i\) in step \(i\). Notice that our shooting position increases by one each time and the dragon’s position either increases by one or decreases by one. Therefore, the distance between the box we shoot at and the dragon’s box either remains the same or decreases by 2. This implies that if in the beginning, the dragon’s box number is odd, we shoot at him at some point in this process. Therefore, if the dragon survives the first 100 shots, it means that his original box number was even. This means that after 100 steps, the number of the box that contains the dragon is even too.

With that knowledge, we can repeat the above algorithm but start from box 2. With the same analysis, since the distance between the box of the dragon and the box we shoot at changes by either 2 or 0 each time, we will eventually shoot the dragon in this algorithm.
Link to the solution on Twitter: https://twitter.com/Riazi_Cafe/status/1682656010081828865