Puzzle: What is the algorithm for finding the kangaroo

629 Views Asked by At

There is a kangaroo that placed somewhere on $L$ upon the axis of the natural numbers.

At some point of the time, The bell is ringing and the game starts: Each round the kangaroo jumps $K$ steps right on the axis (Means, that she moves from her old place $x$ to her new place $x+K$), And right after her jump, We check one of the natural numbers on the axis, by our choice. If the kangaroo is there, we caught him and won; else, we continue to the next round.

We don't know the number $L$ - where the kangaroo been on the start of the game, and we don't know what is the $K$ - Which is the size of the jump (But we know that she always jumps $K$ steps right).

Find the algorithm which assures us that we always catch the rat after limited number of $n$ steps.

(Apologies in advance, English is not my native language).

1

There are 1 best solutions below

0
On

You don't know $(L,K)$. At each step, you can check one possible $(L,K)$. For example, at step 2, you check $L_2+2K_2$; at step 3, you check $L_3+3K_3$.
Try to put all $(L,K)$ on one list, so you can go systematically through all possible $(L,K)$ pairs.