You can find the problem statement here.
Let denote the maximum number of jumps on any path to . We wish to show that if , . As a consequence, every block of values will only take on two distinct values, which greatly reduces the complexity of our problem.
Proof: We will do a proof by contradiction. Assume . Let be a trajectory to that takes jumps, and be a trajectory to that takes jumps. Also, let and denote the number of single-steps taken by and respectively. Then, note that our above inequality is equivalent to . We now wish to show that given this condition, there must exist an intersection between and such that prior to that intersection, uses one more jump than .
An example of one such intersection is shown by the red line.
If such an intersection exists, we can swap the section of before the intersection with the section of , thereby increasing by 1 and contradicting our assumption.
Consider the following algorithm to find such an intersection:
step_balance = 0
balance = 0
start trajectories X and Y at 0
while step_balance < D:
if Y_pos <= X_pos:
advance Y
^ if single step, --step_balance, --balance
^ else, balance -= D
else:
advance X
^ if single step, ++step_balance, ++balance
^ else, balance += D
I claim that this algorithm will always terminate with and at the same position---that is, balance will equal .
First, note that the program will definitely terminate and always with step_balance = D.
Furthermore, note that step_balance and balance are always congruent modulo .
Finally, note the following two properties of the above algorithm:
- If was the last trajectory advanced,
balance > -D. - If the last step took was a single step,
balance <= 0.
Therefore, if step_balance = D, the only viable value of balance is 0.