This week’s Riddler Classic comes courtesy of George Mu, who is passing along a puzzle based on one discussed in a mock coding interview.
You are trying to whack a mole. Every second, it pops its head out from one of 100 holes arranged in a line. You don’t know where the mole starts, but you do know that it always moves from one hole to an adjacent hole each second. For example, if it pops out of the 47th hole, then one second later it pops out of either the 46th hole or the 48th hole. If it pops out of the first hole, then it’s guaranteed to pop out of the second hole next; similarly, if it pops out of the 100th hole, then it’s guaranteed to pop out of the 99th hole next.
Of course, there’s a catch — the mole is camouflaged, and you have no idea where it is at any time until you actually whack it. Each second, you can whack one hole of your choosing. Many sequences of whacks do not guarantee that you’ll eventually get the mole (e.g., always whacking the first hole), but some do.
What is the shortest such sequence that guarantees you will whack the mole, no matter where it starts or how it moves around? (In the aforementioned video, Ben and Dan discuss a sequence that is guaranteed to whack the mole, but it is not necessarily the shortest such sequence.)
Let's look at two cases.
Whack hole 2 twice. This guarantees that the mole is whacked if it started at 1.
Then, continue to whack the $k$th hole on the $k$th turn, for $3 \le k \le 99$. You are guaranteed to whack the mole.
Very similar to above, whack hole 99 twice. This guarantees that the mole is whacked if it started at 100.
Then, continue to whack the $101 - j$th hole on the $j$th turn, for $3 \le j \le 99$. You are guaranteed to whack the mole.
Combining the two together yields the following two seqeuences:
'Mirroring' yields two more winning sequences: