7

A groundhog has made an infinite number of holes one metre apart in a straight line in both directions on an infinite plane. Every day it travels a fixed number of holes in one direction. A farmer would like to catch the groundhog by shining a torch into one of the holes at midnight when it is asleep.

What strategy can the farmer use to ensure that he catches the groundhog eventually?

Glorfindel
  • 28,033
  • 9
  • 96
  • 142
Jeff Beh
  • 79
  • 1

3 Answers3

6

The farmer can

enumerate all the possible groundhog-trajectories -- there are only countably many of them -- and then on day N shine the torch into the hole the groundhog will be in on day N if it is on trajectory N.

More concretely

associate with the number $2^a3^b5^c7^d$ where $a,b,c,d$ are non-negative integers the possibility that the groundhog is at position $(-1)^a\cdot b$ on day 0, and moves by $(-1)^c\cdot d$ on each day. List all positive integers in order, one per night, and when on night $n$ you find one of the form $2^a3^b5^c7^d$ shine the torch into hole $(-1)^a\cdot b + n\cdot(-1)^c\cdot d$. (There are much more efficient strategies than this one, but clearly the farmer has all the time in the world and more in any case.)

Gareth McCaughan
  • 119,120
  • 7
  • 313
  • 454
  • 1
    Can I ask how one learns things like this without a formal education in math? I find these things fascinating and would really like to get better at these sorts of questions. – visualnotsobasic Apr 29 '19 at 15:40
  • 2
    @visualnotsobasic - I'm sure there's a farmer nearby who wouldn't mind teaching you this stuff... – komodosp Apr 29 '19 at 15:52
1

Extending Gareth McCaughan's answer, the farmer can:

Enumerate all the possible options. Draw a diagram with "starting position" on the X axis, and "groundhog speed" on the Y axis. Hit all the points on the integer grid for that diagram.

For example, follow the path:

Path for hitting all the integer grid points Start at the red "X" (the origin) on day 1, then follow the arrows to all the grid points.

To determine which hole to illuminate each day:

Pick an arbitrary hole to label hole zero, then number the rest like a number line. The hole ($H$) to illuminate on day $d$ is: $H = x + d \times y$. For example, on day 1, illuminate the arbitrarily chosen hole 0. On day 2, illuminate hole 1. On day 3 illuminate hole 3, etc. On day 16, the grid position is (1,2), so the hole would be number 33.

This ensures that no matter which hole the groundhog started in or how many holes it moves each day, the farmer will eventually catch him.

user3294068
  • 7,498
  • 23
  • 32
  • Each illumination actually eliminates an infinite number of possibilities: If after one day you check hole 1, then in addition to (1,0), you get to cross over (0,1), (2,-1), (-1,2) and all other possibilities on the straight line where the sum of coordinates (starting hole, speed) is 1. – Bass Apr 30 '19 at 07:22
  • It is true I did not optimize for speed. Then again, it is also true that, as you say, each illumination eliminates a new infinite number of possibilities. So it's not like any of the illuminaitons is wasted. – user3294068 Apr 30 '19 at 16:45
0

The farmer should

Look in the hole that is the number of days since started squared (e.g. 1, 2, 9, 16, etc.).

Because of this, the farmer will eventually catch the groundhog on day N, where

N is the number of holes the groundhog moves per day.

EDIT: Just realized that this will only work assuming you know which direction the groundhog starts travelling in. I will leave it here in case it gives someone an idea though.

APrough
  • 7,679
  • 1
  • 19
  • 49
  • 1
    doesn't this also assume that the farmer knows where the groundhog started? – Bass Apr 29 '19 at 14:43
  • @Bass - it does. I clearly did not understand all of the parameters of the question, but still leave this incredibly incorrect answer here as a potential jumping off point. – APrough Apr 29 '19 at 14:47