가상 게임에서 토큰은 A, B 두 칸 중 한 곳에 숨습니다. 매 차례 한 칸을 확인해 그곳에 있으면 즉시 찾습니다. 못 찾으면 토큰은 다음 확인 전에 반드시 다른 칸으로 이동해요. 머물거나 이동을 건너뛰지는 않아요. 두 칸을 번갈아 확인하면 언젠가는 찾을까요?
첫 토큰이 B에 있고 확인 순서가 A, B, A, B라고 해 볼까요? 첫 확인은 A라서 놓치고 토큰은 A로 가요. 둘째에는 B를 확인해 또 놓치며 토큰은 B로 돌아가요. 이런 엇갈림은 아무리 오래 반복해도 사라지지 않아요.
이를 숫자로 표현해 A=0, B=1로 두고, t번째 확인 직전 토큰의 위치를 pₜ라고 쓰겠습니다. 찾지 못한 경우의 이동 규칙은 다음과 같아요.
대신 A를 두 번 연속 확인해 봐요. 처음 A에 있으면 첫 확인에 잡힙니다. 처음 B에 있으면 첫 확인은 실패하지만 A로 옮겨 오므로 둘째 확인에 잡힙니다. 가능한 두 출발 위치를 모두 따져 보았으므로 늦어도 두 차례 안에 찾는다는 보장이 생겨요.
한 차례만으로는 확인하지 않은 칸에 토큰이 시작할 수 있어 보장할 수 없어요. 따라서 이 규칙의 최소 최악 횟수는 2입니다. 모든 장소에 들렀다는 사실만으로 움직이는 대상을 찾는 것은 아니에요. 이동을 언제, 어떻게 하는지와 확인 순서를 함께 맞춰야 해요.
참고한 수학 개념: AMS · Capturing the Invisible Hopping Rabbit.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.