[Guest]

There are five holes in the ground that a certain groundhog likes to hang out in. These holes are in a row. You are allowed to look in one of the holes at noon each day. Every night, while you aren't around, the groundhog will leave the hole he is in, and move to an adjacent hole. For example, if he's in hole #2, he can move to hole #1 or #3. If he's in hole #1, he can only move to hole #2. What search strategy can you use, to ensure that you will eventually find the groundhog? Using the most efficient strategy, what is the maximum number of days it could take you to find him?

[Wilson]

Zathros's 6 day solution in post #7 is one of four

optimal solutions. All possible groundhog moves

are covered by his solution. Plainglazed got it

first but I didn't spot it before editing this post.

2,3,4,2,3,4

2,3,4,4,3,2

4,3,2,2,3,4

4,3,2,4,3,2

Kudos to you and the other two posters

[Guest]

2 2(he is definitely not in 1st and second holes)4 4(hog should been in 3 one 3rd day on 4th he is on 2 his chances are 1 or 3 on 5th day) 3( he is on 1) 2(he will be there)

so according yo my calcs 6th day u should be catch him

[Guest]

Check in hole 2 twice and you found him. It says that three of them are in a row and that he will move to an adjacent hole so after two days max you've got him.

[witzar]

'-' denotes hole that may be empty or may contain the groundhog

'X' denotes hole that does not contains the groundhog

'!' denotes hole checked on given day

Holes: 1 2 3 4 5

Day1 : - ! - - -

Day2 : X - ! - -

Day3 : - X - ! -

Day4 : - - X ! X

Day5 : - ! - X X

Day6 : X ! X - X

Day7 : X X ! X -

Day8 : X X X ! X

There are others solutions as well, but I think 8 days limit cannot be improved.

Edited June 4, 2010 by witzar

[witzar]

'-' denotes hole that may be empty or may contain the groundhog

'X' denotes hole that does not contains the groundhog

'!' denotes hole checked on given day

Holes: 1 2 3 4 5

Day1 : - ! - - -

Day2 : X - ! - -

Day3 : - X - ! -

Day4 : - - X ! X

OK, I made a mistake here: I missed 'X' on hole 1 day 4. It should be:

Holes: 1 2 3 4 5

Day1 : - ! - - -

Day2 : X - ! - -

Day3 : - X - ! -

Day4 : X ! X - X

Day5 : X X ! X -

Day6 : X X X ! X

So 6 days is enough. On Day 4 you can check hole 4 instead of hole 2 due to symmetry of X-es and continue by analogy. You can also start with hole 4 instead hole 2 on day 1. This gives total of 4 optimal solutions.

[Guest]

x denoates placed checked

n mean the groundhog is not there

e means possible holes

1 2 3 4 5

e x e e e 1345

n x e e e 345

n x n e e 45

n n x e e 45

n n n x e 5

n n n caught n caught

so in 6 days the ground hog is caught

[Guest]

Most Systematic]I would start at one end or the other and work my way one hole at a time therefore if I started at hole one and followed that by hole two the next day, I could get lucky and catch him early, but when i look in the fourth hole on the fourth day, and he is not in there then he is in the fifth hole. It would take no longer than four days. Unless the little bugger runs.

I've see a number of possible solutions that have this same flaw. The "sweep" method does not work. If you look in 1 (with the intention to go to 2, 3, 4, and 5 next) and the groundhog is in 2, you will not find him, no matter how he moves. Understanding why, will help you solve the puzzle.

[Guest]

Day 1, choose hole 2: gopher can be in 1, 3, 4, 5

Day 2, choose hole 3: gopher can be in 2, 4, 5

Day 3, choose hole 4: gopher can be in 1, 3

Day 4, choose hole 4: gopher can be in 2

Day 5, choose hole 3: gopher can be in 1

Day 6, choose hole 2: gopher must be there!

Well done. This is my favorite type of puzzle. It will give you fits until some very simple principles pop into your head. Then it's easy. There is an important concept that hasn't been discussed that makes it very easy to understand this solution. So I will put it in the spoiler below:

The groundhog will move from an even hole to an odd hole, or vice versa, each and every day.

The first 2,3,4 sweep (or 4,3,2) will catch the groundhog if he started in an even hole. If you don't find him in three days, then he must have started in an odd hole. But since it's been three days, he will now be in an even hole. So, the 2,3,4 sweep will get him this time for sure.

You can generalize this solution for any number of holes.

[Guest]

x denoates placed checked

n mean the groundhog is not there

e means possible holes

1 2 3 4 5

e x e e e 1345

n x e e e 345

n x n e e 45

n n x e e 45

n n n x e 5

n n n caught n caught

so in 6 days the ground hog is caught

Your day 3 search is flawed. The groundhog can be in the 3 hole after you search that day. If he started in the 3, went to the 4, and then went back to the 3, he would be in that hole.

[Guest]

Day 1, choose hole 2: gopher can be in 1, 3, 4, 5

Day 2, choose hole 3: gopher can be in 2, 4, 5

Day 3, choose hole 4: gopher can be in 1, 3

Day 4, choose hole 4: gopher can be in 2

Day 5, choose hole 3: gopher can be in 1

Day 6, choose hole 2: gopher must be there!

I agree with your solution. I had the same solution, except it took me 7 days. I guessed hole #2 on the first and the second day before guessing 3,4,4,3,2. I read through your answer and agree that I didn't need to guess #2 twice at the beginning. The only think I disagree with on your solution, is that on day 3 when you say he "could be in 1 or 3" I think he actually could be in 1 , 3, OR 5. It doesn't affect the number of days, I'm just sayin

[Guest]

There are five holes in the ground that a certain groundhog likes to hang out in. These holes are in a row. You are allowed to look in one of the holes at noon each day. Every night, while you aren't around, the groundhog will leave the hole he is in, and move to an adjacent hole. For example, if he's in hole #2, he can move to hole #1 or #3. If he's in hole #1, he can only move to hole #2. What search strategy can you use, to ensure that you will eventually find the groundhog? Using the most efficient strategy, what is the maximum number of days it could take you to find him?

in that case,second hole has to be searched firstly,continued with the 3rd and 4th respectively,lastly the 5th hole,if it is'nt found in all 4,it is deemed to be found in the 1st!!IT TAKES 4 CONTINUOUS NOONS TO FIND THE GROUNDHOG!!

[Guest]

in that case,second hole has to be searched firstly,continued with the 3rd and 4th respectively,lastly the 5th hole,if it is'nt found in all 4,it is deemed to be found in the 1st!!IT TAKES 4 CONTINUOUS NOONS TO FIND THE GROUNDHOG!!

If you use your solution, and you have looked in holes 2, 3, and 4 in order with no luck so far. Looking in hole 5 in day 4 has a 0% chance of finding the groundhog. Think about why, and it will help you solve the puzzle.

[Guest]

Is this correct?

Day 1- hole 2

Day 2- hole 4

Day 3- hole 3

Day 4- hole 5

That way by noon of the 4th day we know that the groundhog is in the 1st hole

[Guest]

Is this correct?

Day 1- hole 2

Day 2- hole 4

Day 3- hole 3

Day 4- hole 5

That way by noon of the 4th day we know that the groundhog is in the 1st hole

I thought too soon

[Guest]

If you use your solution, and you have looked in holes 2, 3, and 4 in order with no luck so far. Looking in hole 5 in day 4 has a 0% chance of finding the groundhog. Think about why, and it will help you solve the puzzle.

I gave this problem to a friend of mine yesterday and he came up a totally different solution in a matter of minutes. It's pretty cool

2

2 (now the groundhog can only be in 3,4 or 5)

4

4 (now he can only be in 1 or 3)

4

2

Strange but true

[plainglazed]

...am not sure it works:

Day 1 choose 2 but empty then must be in either 1,3,4,5 - Night 1 moves to either 2,3,4,5

Day 2 choose 2 but empty then must be in either 3,4,5 - Night 2 moves to either 2,3,4,5

so on Day three the pesky little bugger could be in room 2 as well and after choosing room 4, the following day would be like starting from square one.

[EventHorizon]

...am not sure it works:

Day 1 choose 2 but empty then must be in either 1,3,4,5 - Night 1 moves to either 2,3,4,5

Day 2 choose 2 but empty then must be in either 3,4,5 - Night 2 moves to either 2,3,4,5

so on Day three the pesky little bugger could be in room 2 as well and after choosing room 4, the following day would be like starting from square one.

Agreed.

Format = check-groundhog

2-3 or 5

2-4

4-3

4-2

4-3

2-4

or

2-4

2-3

4-2

4-3 or 1

4-2

2-3

So if the groundhog starts anywhere but 1 or 2 there's a path he could take and never be found.

[Guest]

...am not sure it works:

Day 1 choose 2 but empty then must be in either 1,3,4,5 - Night 1 moves to either 2,3,4,5

Day 2 choose 2 but empty then must be in either 3,4,5 - Night 2 moves to either 2,3,4,5

so on Day three the pesky little bugger could be in room 2 as well and after choosing room 4, the following day would be like starting from square one.

Oops. I guess, strange, but not true