Groundhog in a Hole - Yet Again

[EventHorizon]

There is an infinite line of holes in an infinite field.  You know there is a groundhog hiding in one of the holes.  You can check a hole once a day.  At night the groundhog will move one hole to the left or one hole to the right.  Knowing you cannot find the groundhog yourself, you enlist a friend to help.  Now you can check 2 holes a day.  Can you find the groundhog?  If so, how would you do it?

 

Original: http://brainden.com/forum/topic/11943--/

My Additions: http://brainden.com/forum/topic/12010--/

[xp2008]

To solve the question without knowing parity, we follow almost the same steps, except we change hypothesis of parity alternatively each time we go to next round. And it may take us one more round to find it, because we find it only when in the same parity.

Edited May 19, 2020 by xp2008

[plasmid]

On 11/1/2020 at 2:16 PM, EventHorizon said:

  Reveal hidden contents

In both xp2008's and my solutions, you don't scan over the same range twice, once for each parity.  You increase the range by the scale factor every time you switch the parity.

 

Ah, I see. So in that spirit you could present your solution #2 this way (not particularly efficient, but crystal clear that it works)

Spoiler

Suppose the groundhog started at hole #0. Check hole #0 on the first day, and if he’s there then you’re done.

Suppose the groundhog started at hole -1 or hole 1. By the second day (after you’ve checked hole 0) he’ll be at hole -2, 0, or 2. Have the two of you check holes ±2 on the second day, and if you don’t find him and he started at hole ±1 then he must have gone to hole 0 for the second day and will be at hole ±1 on the third day. Check holes ±1 on the third day and you’ll find him.

Suppose the groundhog started at hole -2 or hole 2 on the first day. By the fourth day (after you’ve taken care of the cases where he starts at -1, 0, or 1) he’ll be at an odd numbered hole from -5 to 5. Search holes ±5 on the fourth day and if he’s not found then he was in an odd numbered hole from -3 to 3 and will be in an even numbered hole from -4 to 4 on the next day. Check holes ±4 on the fifth day, then holes ±3 on the sixth day, etc. until you’ve taken care of all the cases where he started at hole -2 or 2.

Suppose the groundhog started at hole -3 or hole 3, or in general hole -N or N where you’ve already taken care of all of the smaller numbers. If you’ve taken D days to search, then he must be in hole -(N+D) to (N+D), so search holes ±(N+D) and work your way inward.

After taking care of that case, move on to the next higher N. No matter where he initially started, you’ll eventually find him.

 

[CaptainEd]

Interesting! Does the line of boxes have an origin? Like 1 to infinity? Or is it from negative infinity to positive infinity?

[EventHorizon]

Negative infinity to positive infinity.  You could pick any hole to be the origin.

[Wilson]

Barring blind luck, I don't think it can be caught with two hunters. Thoughts....

Spoiler

Think minimum required is two teams of 3. From origin one team heads -ve, other goes +ve. Teams can check two new holes each day, whilst  preventing the hog from backtracking. They will be moving twice speed of hog so will eventually capture.

 

[EventHorizon]

8 hours ago, Wilson said:

Barring blind luck, I don't think it can be caught with two hunters. Thoughts....

  Reveal hidden contents

Think minimum required is two teams of 3. From origin one team heads -ve, other goes +ve. Teams can check two new holes each day, whilst  preventing the hog from backtracking. They will be moving twice speed of hog so will eventually capture.

 

Spoiler

You can cut one hunter off your strategy by alternating which direction checks two new holes and which only checks one.

Can anyone find the groundhog using less than 5 hunters?

[EventHorizon]

Perhaps this question will help move things along...

Spoiler

If I were to tell you on the first day that the groundhog was an odd number of holes away from the origin, could you then find the groundhog with 2 hunters?

 

[HotRodCow]

If they started from either end worked to the middle they would eventually find it... provided they lived for eternity

[EventHorizon]

20 hours ago, HotRodCow said:

If they started from either end worked to the middle they would eventually find it... provided they lived for eternity

There is no end to start from.  Every hole has an infinite number of holes on both sides of it.

And, yes, both you and the groundhog are immortal.  Your friend, not so much.  Luckily, you'll always be able to enlist a member of his posterity to help check one hole each day, so close enough.

[xp2008]

On 5/12/2020 at 3:04 AM, EventHorizon said:

Perhaps this question will help move things along...

  Hide contents

If I were to tell you on the first day that the groundhog was an odd number of holes away from the origin, could you then find the groundhog with 2 hunters?

 

If we know first day's parity then we can. Supposing it was odd, then I will check

1. 1 3
2. 4 6
3. 1 -1
4. -2 -4
5. 6 8
6. 9 11
7. ...

Which is to say,

day 4k+1, I check 5K+1, 5K+3

day 4k+2, I check 5K+4, 5K+6

day 4K+3, I check -5K+1, -5K-1

day 4K+4, I check -5K-2,  -5K-4

We can see my range is ( -5K-4, 5K+6 ) , while    lim ( 5K - 4K) = lim (K) -> infinity, thus we could always find the groundhog in this case.

[EventHorizon]

16 hours ago, xp2008 said:

If we know first day's parity then we can. Supposing it was odd, then I will check

1. 1 3
2. 4 6
3. 1 -1
4. -2 -4
5. 6 8
6. 9 11
7. ...

Which is to say,

day 4k+1, I check 5K+1, 5K+3

day 4k+2, I check 5K+4, 5K+6

day 4K+3, I check -5K+1, -5K-1

day 4K+4, I check -5K-2,  -5K-4

We can see my range is ( -5K-4, 5K+6 ) , while    lim ( 5K - 4K) = lim (K) -> infinity, thus we could always find the groundhog in this case.

Unfortunately, that does not work for the known parity case.

Notice day 4 checks even holes, and day 5 also checks even holes.  So days 5-8 are checking the wrong parity.

Fixing this, the numbers change such that day 4k+x checks hole 4k+y, so the groundhog can escape by fleeing away from hole 0.

[xp2008]

3 hours ago, EventHorizon said:

Unfortunately, that does not work for the known parity case.

Notice day 4 checks even holes, and day 5 also checks even holes.  So days 5-8 are checking the wrong parity.

Fixing this, the numbers change such that day 4k+x checks hole 4k+y, so the groundhog can escape by fleeing away from hole 0.

Apologise I considered it to be 2 days after when they come back to positive half axis, yeah, after fixing this 4K hole doesn't work for 4k day.

Is this an open question or you know there's an answer ?

Edited May 19, 2020 by xp2008

[xp2008]

I tried again like this, supposing we know the parity case, for example odd on first day

By checking (1,3),(4,6),(7,9),..., we can check a range of (3k-1) in k days. Now I construct a sequence of numbers a_i, such that

a_n >= 3*sum_i<na_i

we can easily verify that a_i = 4ⁱ qualifies.

The strategy now becomes,

in the first a1=4 days, we check (-5,-3),(-2,0),(1,3),(4,6), which is a range of -5 -> 6

in the next a2 = 16 days, we check (-23, -21),(-20,-18),...(-2,0),(1,3),..,(22,24), which is a range of -23 -> 24

etc.

Supposing groundhog is at P, while |6P|<a_p = 4^p

Then after ( a₁ + a₂ + .. +a_p ) days, the range we just checked is the range of last a_p days, which is about -1.5*a_p  -> 1.5*a_p, while the range of groundhog could be is

-|P| -  ( a₁ + a₂ + .. +a_p ) ->  |P|+( a₁ + a₂ + .. +a_p ),

on the other hand, we have 

|P|+( a₁ + a₂ + .. +a_p ) - 1.5*a_p = |P|+( a₁ + a₂ + .. +a_p-1) - 0.5*a_p < a_p/6 +a_p/3-0.5*a_p = 0,

which is to say, groundhog's range is included by our last searching range.  

Edited May 19, 2020 by xp2008

[EventHorizon]

15 minutes ago, xp2008 said:

To solve the question without knowing parity, we follow almost the same steps, except we change hypothesis of parity alternatively each time we go to next round. And it may take us one more round to find it, because we find it only when in the same parity.

You got it.  Well done.  I'll post my solutions later.

[xp2008]

6 minutes ago, EventHorizon said:

You got it.  Well done.  I'll post my solutions later.

Thanks !

We can see the days we need is

sum_i<=P+1a_p<3*a_p+2=3*4³*a_p-1<3*4³*6P, which is O(P).

[EventHorizon]

My thoughts and solutions:

Spoiler

Solution 1:  If you have one person check, for instance, holes 0 and 3 on alternating days, you can keep the groundhog trapped in holes 1-2.  Using this, you can have the other scan over the area being guarded.  And once the scan is done, trap progressively larger areas alternating the assumed parity for each time a new area is selected.  You can easily choose a multiplicative factor to increase the size of the areas by to make the time spent on the previous areas practically meaningless compared to the new area size, so the groundhog couldn't escape by running away.

 

Solution 2:  Not that the groundhog, if the correct parity, cannot get past the person making the scan of the area.  Then you can have one person start at one end of a chosen area and the other at the other end, and if the groundhog has the right parity and is in the area, it will be caught.  This is simpler than solution 1 since both checkers have the same job.  It also doubles the speed of solution 1.

 

---Additional thoughts---

Solution 1 was what I initially thought of when coming up with this puzzle.  Using this idea you could also have a puzzle like two squares of holes with a shared edge, have one person alternate at the two intersection points and then have the other scan the 3 connected segments for the assumed parity, then clear it again with the other parity.

 

xp2008's solution was rather interesting.  He showed that you didn't even need to have an area trapped if you scan in one direction using both checkers.

 

Looking at solution 2, you can see that if the line of holes has an end on one side (ie, one sided infinity), you only need 1 person to find the groundhog.

 

The solutions for my original additions back in the day all had solutions that were rather elegant extensions of the original problem's solution.  This one turns out to be the same.  Using solution 2, if you center the checking around hole 0 (ie, when one person checks hole x, the other checks -x), start with checking an odd number, and have the scale factor an odd number 5 or more (3?)... it seems much like a simple extension of the solution to the original problem.  The requirements of starting at odd hole and having the scaling factor be odd makes the parity naturally alternate with each new area.  Also, like how you never need to check holes 1 or 5 in the original, you never check hole 0 in this solution.

 

[harey]

On 6/6/2020 at 12:13 PM, EventHorizon said:

My thoughts and solutions:

  Hide contents

Solution 1:  ....You can easily choose a multiplicative factor to increase the size of the areas by to make the time spent on the previous areas practically meaningless compared to the new area size, so the groundhog couldn't escape by running away.

 

Never mind how big the area you chose, I always can say "Bad luck, the groundhog is somewhere about 17 holes outside the defined area."

I agree that the size of the cleared area will -> inf. Just the size is expressed as a number. No matter how big it is, there always is a bigger number.

[EventHorizon]

While the hole that the groundhog starts in is unknown, it is one specific hole and its movements are as described.  No matter what hole it starts in, given its described movement, the strategy given will eventually find it.  You make it seem like the groundhog can teleport just because it's starting hole was unknown.

Given your "about 17 holes outside" example, it would take just one or two (depending on parity) rounds of area clearing/expansion to get it.  It does not matter that there are more holes outside the area, it will eventually be trapped and caught.

[harey]

Thinking it over and over again, I always finish with a problem I cannot solve.

The holes are numbered 1, 2, 3....

Three hunters check:
1 2 3
      3 4 5
            5 6 7
....

On day n, they will have checked up to the hole 2 * n +1

The groundhog starts in the hole k and moves to the right.
On day n, he will be in the hole k+n

Question 1: Will the hunters catch the groundhog (and if so, when)?
2 * n +1 grows faster than k + 1, I already have the answer. Nevertheless:
2 * n + 1 = k + n
n ⁼ k + 1
No matter how high the number of the starting hole the groundhog choses, it will be caught.

Question 2: Is there  a starting hole so that the groundhog is not discovered on day n?
k + n > 2 * n + 1
k > n + 1
No matter how long the hunters hunt, it always is possible that the groundhog started in a hole leading him outside the checked area.

[plasmid]

I'm afraid I might be missing something, because it seems like whenever you switch parity you end up losing all the ground you previously covered.

Consider xp2008's solution...

Spoiler

If you assume the initial parity is odd and you search (-5,-3),(-2,0),(1,3),(4,6), then where could the groundhog be on day 4 if he's not caught? If he started from hole -7 then he could have reached hole -4 by day 4, and he could be at hole +8 on day 4, or anywhere outside that range.

If you then switch to cover the even parity case and search for four days, in the odd parity case the groundhog could have moved from hole -4 on day 4 to hole 0 on day 8, and could have moved from hole +8 on day 4 to hole +4 on day 8. So after you've searched both parities, now all you know for the odd parity case is that the groundhog is not in the range from hole 1 to hole 3. So when you resume your odd parity search on the next day, the groundhog could be in any odd hole. Have you really made any progress?

Similarly for EventHorizon's first solution

Spoiler

Take the case of having bounds of 0 and N (where N is odd) for an initial scan. If you assume initial even parity, then you could scan (0,2), (N,3), (0,4), (N,5), ... (0,N-1) and it would take you N-1 days. You could then re-scan the area covering the initial odd parity case, but after scanning for another N-1 days the groundhog could get anywhere within the even parity case again by the time you start the next scan.

You could argue that if you start off covering a finite area, then cover a slightly larger area, then cover a slightly larger area, etc. then you will eventually catch the groundhog because the groundhog must be at some finitely numbered hole which you will eventually reach. My counterargument to that is:

Spoiler

xp2008's strategy would cover holes -5 through 6 for the odd parity case and finish after 4 days. If you then cover the even parity cases, you could cover holes -6 through 5 for the even parity case and finish both the odd and even parity cases after 8 days.

Similarly, it would cover holes -23 to 24 for the odd parity case over the next 16 days, so if you start doing that on day 9 (after finishing the odd and even parity cases for -6 to 6) then you would finish on day 24. Then you would cover the even parity cases for that range over the next 16 days and finish on day 40.

If I'm a groundhog and I don't want to be caught, I start on hole +2 and move to the next higher hole every day. You'll never catch me.

 

[EventHorizon]

Spoiler

In both xp2008's and my solutions, you don't scan over the same range twice, once for each parity.  You increase the range by the scale factor every time you switch the parity.