抓间谍（离散直线）

Catching the Spy

专题: Strategy / 策略
难度: L6
来源: Brainstellar

题目详情

一名间谍在整数直线上运动。时刻 0 在位置 $A$ ，之后每个整数时刻向右移动 $B$ （ $B$ 可为负，即向左）。 $A,B$ 是固定整数但你不知道。

你每个时刻（从 0 开始）可以选择一个整数位置并询问“间谍是否此刻在该位置？”，得到是/否。

问：是否存在一种询问策略，保证最终一定能抓到间谍？若有，请给出思路。

提示：整数对 $(A,B)$ 可数，可以枚举。

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy

解析

可以保证抓到。

关键：所有整数对 $(A,B)$ 可数，存在一个枚举 $f(n)=(A_n,B_n)$ 覆盖所有可能。

在时刻 $n$ ，你询问位置

A_n+n\cdot B_n.

若真实参数为 $(A,B)$ ，则它会在某个 $n$ 上被枚举到： $f(n)=(A,B)$ 。此时询问的位置恰好等于间谍当时位置，于是回答为“是”，即可抓到。

Original Explanation

Solution

Here is a detailed solution with images

And here is a short solution:

Since integer 2-tuples $(x,y)$ are countable, there exists a function $f:N \rightarrow N*N$ such that $f$ covers all integer 2-tuples.

Let $f(n)=(f_1(n),f_2(n))$ . The algorithm will be to check for location $f1(n) + n\cdot f_2(n)$ at time instant $n$ .

Given $A$ and $B$ , there exists $n_0$ such that $f(n_0)=(f_1(n_0),f_2(n_0))=(A,B)$ , and thus at time instant $n_0$ we will be checking for location $f_1(n_0)+n_0 \cdot f_2(n_0)$ which is $= A+ B \cdot n_0$ - the actual location of the spy.