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

14 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

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