8
$\begingroup$

A token starts at location (0,0) on an infinite grid. On turn $n$ it must jump $n$ units horizontally or vertically, in one of four directions. What is the least number of turns needed for it to reach the location (10,10)? Bonus: what about location (100,100)? Good luck!

$\endgroup$
16
$\begingroup$

The token travels a distance of at least 20 to get to (10,10). Also, the total distance travelled

must be even, because any distance travelled past 10 must be undone and hence travelled twice.
The first n for which the total distance 1+2+..+n is more than 20 and even is n=7, for a total of 28.
This has a surplus of 8=2*4, so we can just reverse the direction of the length 4 step to compensate. The steps can be made to reach (10,10) by for example (10,10) = (3+7, 1+2-4+5+6)

For (100,100) we can do the same thing.

The first n for which 1+2+..+n is at least 200 and even is n=20.
Then 1+2+...+20 = 210, so flip the direction of the size 5 step to get rid of that surplus of 10. You can make 100 by 100=20+19+18+17+16+10 for example (there are many possibilities for this - I used the greedy method to find this one), and then the rest of the steps make up the other 100. This gives the solution:
(100,100) = (10+16+17+18+19+20, 1+2+3+4-5+6+7+8+9+11+12+13+14+15)

$\endgroup$
1
  • 2
    $\begingroup$ That is a brilliant answer! Very well explained. $\endgroup$ – Dmitry Kamenetsky May 10 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.