# More Catching of Cats

After my first puzzle on this theme was solved relatively quickly, here is a (trickier) follow up question in the same vein!

The setup is similar - you are in a room with an infinite line of boxes, numbered in order with the nonnegative integers. In one of these boxes, a (speedy) cat is hiding but you do not know where. Your goal, again, is to catch the cat, taking turns like so:

Every turn, you may check any box of your choosing. If the cat is currently inside it, you win. Otherwise, you close the box and the cat will move, without your knowledge, to a box exactly $$k$$ steps away from its current location (perhaps to a box you already checked). You do not know $$k$$, only that it is a positive integer that is fixed throughout the game. After that, the game continues with the next turn.

Can you find a strategy to always catch the cat?

Have fun!

• The catching of cats is a difficult matter; it isn't just one of your holiday games ... Commented Jun 2 at 19:09

Let's summarize Jaap Scherphuis's answer to the easier version of the problem where the cat can only move 1 step at a time:

The idea is that if we know the cat started off somewhere in the first $$n$$ boxes, there is a finite sequence of moves (whose length depends on $$n$$) that's guaranteed to catch the cat. We start by guessing that the cat started in the first $$9$$ boxes, and try to catch it. If we don't get it, we next guess it started in the first $$99$$ boxes and try again; then the first $$999$$, $$9999$$, and so on. Eventually one of our guesses has to be right so we're guaranteed to catch the cat.

If we use the shorthand $$S(n)$$ to mean "perform a series of moves that will catch the cat if it started in the first $$n$$ boxes", then the strategy is: perform $$S(9), S(99), S(999), ...$$ etc. until we catch the cat. (Of course the sequence $$9, 99, 999, ...$$ is arbitrary and can be any sequence that grows to infinity.)

Now, since in this version the cat has a step size of $$k$$, we have to modify our strategy:

by just guessing what $$k$$ is! Just like in the 1-step case, if we know both the step size $$k$$ and a bound $$n$$ on the starting position of the cat, there's a finite sequence of moves we can make that's guaranteed to catch it. As an extension of the previous notation, let's denote that by $$S_k(n)$$, so the $$S(n)$$ from before is now $$S_1(n)$$. Then we proceed similarly to how we did before: first, guess that the step size is $$1$$, and try to catch the cat. If we're right, great! If not, guess the step size is $$2$$ and try again, then $$3$$, $$4$$, and so on till we get it.

...Right?

Not quite. This doesn't work because:

If we write out the sequences of moves that we're making, the first step (checking $$k=1$$) already involves an infinite sequence $$S_1(9), S_1(99), S_1(999),...$$ meaning that if $$k\ne 1$$, we'll make an infinite number of moves without finding the cat. Essentially, we're trying to make the moves in the following order:$$S_1(9),S_1(99),S_1(999),...\\S_2(9),S_2(99),S_2(999),...\\S_3(9),S_3(99),S_3(999),...\\\vdots$$ which doesn't work since there are an infinite number of $$S_1$$'s to try before the first $$S_2$$.

We can fix it by:

Interleaving the values of $$n$$ and $$k$$ that we try, instead of trying to exhaust the entirety of $$k=1$$ before proceeding to $$k=2$$. (Essentially, we need to solve the problem of enumerating ordered pairs of natural numbers.) For example, we can do our moves in the following order:\begin{align*}&S_1(9),\\&S_2(9),S_1(99),\\&S_3(9),S_2(99),S_1(999),\\&...\end{align*}This way no matter the actual value of $$k$$ and $$n$$, we're guaranteed to reach it after a finite number of moves.

Finally, here's an appendix of sorts to expand on some details:

What if the cat keeps moving farther away faster than we expand our search?

This isn't a problem because the $$n$$ in $$S_k(n)$$ is the starting position of the cat, not the current position. This means that $$S_k(n)$$ really depends not only on $$k$$ and $$n$$, but also on how many turns have already passed before we invoke it: if we're performing it after we already made $$x$$ moves, then it really means "assume the cat has a step size $$k$$ and started at below $$n$$, so it currently is at position at most $$n+kx$$." Although the number of steps this takes depends on $$x$$, not just $$n$$ and $$k$$, the important thing is that it's always finite.

What actually is the strategy $$S_k(n)$$?

For $$k=1$$, see the previous question's answer. For $$k>1$$, we can reduce it to the 1-step case by making another guess, this time guessing what the cat's position is mod $$k$$. For example, take $$k=10$$. If the cat started at a position ending in $$7$$, it can only move between positions $$7, 17, 27, 37, ...$$ which is just like the 1-step case with the boxes relabeled. We just have to check each possible value mod $$k$$, doing $$k$$ different shifted versions of the 1-step strategy.

• Very nice work! Commented Jun 2 at 17:24
• This is somewhat reminiscent of the submarine puzzle. Commented Jun 2 at 18:03