[This is a solution to the catch the magical monkey puzzle posted earlier]
Brief description of the puzzle:
A monkey is moving at constant integer velocity among the integer points.
You can pick a point at any given time and check if the monkey is there. If he is there, you can catch him.
Can you eventually catch the monkey?
The solution relies on the following fact: $\mathbb{Z}^2$ is countable, and so there is a bijection mapping every ordered pair of integers $(a,b)$ to a natural number $f(a,b)$.
The strategy is to guess that the monkey's position at time $f(a,b)$ is $a + bf(a,b)$, corresponding to a guess of initial position $a$ and velocity $b$.
If the monkey's actual speed is $v$ and initial position was $u$, then we will catch him at time $f(u,v)$
Brief description of the puzzle:
A monkey is moving at constant integer velocity among the integer points.
You can pick a point at any given time and check if the monkey is there. If he is there, you can catch him.
Can you eventually catch the monkey?
Solution
The solution relies on the following fact: $\mathbb{Z}^2$ is countable, and so there is a bijection mapping every ordered pair of integers $(a,b)$ to a natural number $f(a,b)$.
The strategy is to guess that the monkey's position at time $f(a,b)$ is $a + bf(a,b)$, corresponding to a guess of initial position $a$ and velocity $b$.
If the monkey's actual speed is $v$ and initial position was $u$, then we will catch him at time $f(u,v)$
No comments:
Post a Comment