3
$\begingroup$

In a flat plane, I have an infinite number of holes in a straight line. A mole lies in one of the holes and will travel $d$ number of holes every morning, and he will move that number of holes in the same direction. We do not know which hole the mole is in. A gardener wants to catch this mole because it is destroying his crops. A gardener will only check once every night at a particular hole. If the mole is there, it is caught. If it is not there, the gardener goes back home. What should the gardener do so that he will catch the mole eventually? (Assuming there exist an infinite number of days)

What I have tried:

I label the holes $...,-n, -n+1, -n+2,..., -2, -1, 0, 1, 2, 3, ..., n-2, n-1, n...$. I assume that if the mole starts in hole $0$ and travels $2$ steps back, then he is in hole $-2$. If the mole starts in hole $0$ and travels $2$ steps forward, then he is in hole $2$.

Suppose both the mole and the gardener starts on the same hole, and for simplicity, both the mole and gardener starts on hole $0$. What the farmer can do: Check hole $1$ on the first day, check hole $-2$ on the second day, $6$ on the third day, $-8$ on the fourth day, $15$ on the fifth day, $-18$ on the sixth day.. In general, he should check:

Hole # = $n.\frac {-n}{2}$ if $n$ is even, and Hole # = $n.\lfloor \frac {n+1}{2} \rfloor$ if $n$ is odd, where $n$ is the $n^{th}$ day.

In my earlier statement, I have proved that I can form a one-to-one correspondence. For example, $f(1)=1, f(2)=-1, f(3)=2, f(4)=-2,...$. Hence, the gardener is able to find a way to hunt down the moles. Hence, even though he does not know how many steps does the mole move a day or in which direction, the gardener am still able to track it down.

Now here's the real problem. The gardener does not know which hole the mole is in, nor how many steps or in which direction the mole is heading. What can the gardener do to catch the mole eventually?

Any answers are appreciated but I hope that you can explain why the answer works that way too! Thank you! It would be good to show me how a one-to-one correspondence works for this question too!

$\endgroup$
  • $\begingroup$ The statement says that the mole "will move that number of holes in the same direction". I take this to mean that the mole never changes direction from one day to the next; once the first two locations are fixed, all future position are determined (even though the gardener does not know them). Is this correct? $\endgroup$ – Marc van Leeuwen Mar 16 '17 at 14:51
  • $\begingroup$ Yes you are right! $\endgroup$ – Icycarus Mar 16 '17 at 14:54
3
$\begingroup$

If indeed the dynamics of the mole are entirely determined by initial position $p$ and per-day displacement $d$ (so then at any day $n$ it is at $p+nd$), then this is a countable number of possibilities (the cardinal of $\Bbb Z\times\Bbb Z$ where $(p,d)$ is taken from). The gardener can choose an enumeration of $\Bbb Z\times\Bbb Z$, in other words a surjective map $f:\Bbb N\to\Bbb Z\times\Bbb Z$, and then for each $n\in\Bbb N$, letting $f(n)=(p,d)$ choose the hole $p+nd$. Once the enumeration reaches the actual parameters valid for the mole, the mole will be caught, and this cannot fail to happen.

$\endgroup$
  • $\begingroup$ Ahh! I get it! In a way we can also create a one-to-one correspondence $f:\Bbb N \to \Bbb Z \times \Bbb Z$ (something similar, but not equals to, Cantor's diagonalization process) right? One question: I do know that on Day 7 for example, I should visit Hole $p+7d$. Is there any specific way to find $p$ and $d$? $\endgroup$ – Icycarus Mar 16 '17 at 15:34
  • $\begingroup$ Not Cantor's diagonal argument by any stretch. Though Cantor was certainly aware that things like $\Bbb Z\times\Bbb Z$ are countable. An obvious choice for enumerating $\Bbb Z\times\Bbb Z$ would be to start in the origin and spiral outward in some systematic way; easy to conceive though not so easy to give a formula for. $\endgroup$ – Marc van Leeuwen Mar 16 '17 at 15:56
  • $\begingroup$ Sure thing! Thanks for the tip! I will let you know after my lecturer has shared some hints regarding this question! $\endgroup$ – Icycarus Mar 16 '17 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.