Jump to content
BrainDen.com - Brain Teasers
  • 2
Sign in to follow this  
EventHorizon

Groundhog in a Hole - Yet Again

Question

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--/

Share this post


Link to post
Share on other sites

18 answers to this question

Recommended Posts

  • 1

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 by xp2008

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


Link to post
Share on other sites
  • 0

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.

 

Share this post


Link to post
Share on other sites
  • 0
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?

Share this post


Link to post
Share on other sites
  • 0

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?

 

Share this post


Link to post
Share on other sites
  • 0
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. :P

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0
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 by xp2008

Share this post


Link to post
Share on other sites
  • 0

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 ai, such that

an >= 3*sumi<nai

we can easily verify that ai = 4i 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|<ap = 4p

Then after ( a1 + a2 + .. +ap ) days, the range we just checked is the range of last ap days, which is about -1.5*ap  -> 1.5*ap, while the range of groundhog could be is

-|P| -  ( a1 + a2 + .. +ap ) ->  |P|+( a1 + a2 + .. +ap ),

on the other hand, we have 

|P|+( a1 + a2 + .. +ap ) - 1.5*ap = |P|+( a1 + a2 + .. +ap-1) - 0.5*ap < ap/6 +ap/3-0.5*ap = 0,

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

Edited by xp2008

Share this post


Link to post
Share on other sites
  • 0
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.

  • Like 1

Share this post


Link to post
Share on other sites
  • 0
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

sumi<=P+1ap<3*ap+2=3*43*ap-1<3*43*6P, which is O(P).

Share this post


Link to post
Share on other sites
  • 0

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.

 

Share this post


Link to post
Share on other sites
  • 0
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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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
> 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.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...