[EventHorizon]

1. Now the groundhog can leave holes 1 and 5 going away from the other holes, realize there is no hole there, and run back to the hole he was in. Now that he can stay in 1 or 5, what would be the maximum number of days that it could take to find the groundhog using the most efficient strategy? If there is no strategy that will be sure to find the groundhog in a finite number of days, prove it. (Too easy?)

2. Now there are 12 holes arranged like the numbers on an analog clock. The groundhog must move to a neighboring hole every night, like usual. You realize there is no strategy that guarantees finding the groundhog in finite time, so you hire another person to check a hole once every day. What would be the maximum number of days before finding the groundhog using the most efficient strategy?

3. Same as 2, but with 3 people checking holes.

4. You have a 5 by 5 grid of holes, and the groundhog can move in the four cardinal directions. What is the minimum number of people needed before you can be sure to find the groundhog in a finite amount of time? How long does it take with that number of people?

(yeah, I tend to put multiple problems in threads... it's like a shotgun approach, hopefully 1 or 2 are really good.)

[Guest]

You cannot guarantee to find the groundhog in a finite number of days. No matter what hole you pick the groundhog could be in any hole after he moves. Say you picked 2. The groundhog could go stay in 1 from 1, go to 2 from 1, go to 3 from 4, go to 4 from 3 or go to 5 from 4. And you are right back where you started. This is true for any hole you might pick so you can never be guaranteed to find the groundhog.

[Guest]

Name the holes from 1 to 12 like the hours on a clock.

If the groundhog is not in the 2 holes adjacent to a hole, he cannot then move to that hole overnight.

Day|Holes the groundhog cannot be in today|Holes you have checked today

-----------------------------------------------------------------------

 1 |              n/a                     |      11, 1

 2 |               12                     |      10, 2

 3 |              1,11                    |       9, 3

 4 |             2,10,12                  |       8, 4

 5 |            1,3,9,11                  |       7, 5

 6 |          2,4,6,8,10,12               |      11, 1

 7 |         1,3,5,7,9,11,12              |      10, 2

 8 |        1,2,4,6,8,10,11,12            |       9, 3

 9 |       1,2,3,5,7,9,10,11,12           |       8, 4

10 |      1,2,3,4,6,8,9,10,11,12          |       7, 5

[Guest]

Similar to 2:

Day|Holes the groundhog cannot be in today|Holes you have checked today

-----------------------------------------------------------------------

 1 |                 n/a                  |      10,12, 2

 2 |                 1,11                 |       9, 3, 5

 3 |               2,4,10,12              |       6, 7, 8

 4 |             1,3,5,7,9,11             |      10,12, 2

 5 |          1,2,4,6,8,10,11,12          |       5, 7, 9

 6 |        1,3,5,6,7,8,9,10,11,12        |       2, 4

Edited June 10, 2010 by Tuckleton

[Guest]

I can do it with 3 in 32 days. Might be able to do better but that and an explanation will have to wait until later, I've lost too much time already

[plainglazed]

Dont think you can do this one either. Two people can only eliminate one (different) hole per day.

[plainglazed]

Best I can do is 10 days

1 1,2,3 4,5,6,7,8,9,10,11,12 1,3,4,5,6,7,8,9,10,11,12
2 1,3,4 5,6,7,8,9,10,11,12 1,4,5,6,7,8,9,10,11,12
3 1,4,5 6,7,8,9,10,11,12 1,5,6,7,8,9,10,11,12
4 1,5,6 7,8,9,10,11,12 1,6,7,8,9,10,11,12
5 1,6,7 8,9,10,11,12 1,7,8,9,10,11,12
6 1,7,8 9,10,11,12 1,8,9,10,11,12
7 1,8,9 10,11,12 1,9,10,11,12
8 1,9,10 11,12 1,10,11,12
9 1,10,11 12 1,11,12
10 1,11,12

Day    Choose		   Not in at noon	      	  Can move to at night

[plainglazed]

Think I can do it with 6 people in 14 days?

[Guest]

If knowing which hole the groundhog is in is enough, then 3 people can do it in 30 days. If you actually have to look in the hole the groundhog is in, then 3 people can do it in 31 days. Still trying to figure out an efficient and clear way of presenting my answer without resorting to an exhaustive description of the day-by-day choices and eliminations, though I may end up having to do that when I get time...

[Guest]

Ok, so I did one better than I previously thought. 3 people, 29 days if you only need to know where it is and 30 if you have to look in it's hole.

. = a hole the groundhog could be in today.

X = a hole the groundhog cannot be in today.

L = a hole that is checked today.

  1	  2	  3	  4	  5	  6	  7	  8	  9	 10	 11	 12	 13	 14	 15


.L.L.	L.X..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.	X.X.L	.X.X.	X.X.X	.X.X.

..L..	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.	X.X.X

.....	L....	.L...	X....	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.

.....	.....	L....	.L...	X....	.L...	X....	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X.L

.....	.....	.....	L....	.....	L....	.L...	X....	.L...	X....	.L...	X.L..	.X...	X.L..	.X.LL


 16	 17	 18	 19	 20	 21	 22	 23	 24	 25	 26	 27	 28	 29	 30


XLXLX	LXXX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX	XXXXL	XXXXX	XXXXX	XXXXX

.XLX.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX	XXXXX

X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX

.X.X.	X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXXL

X.X.X	.X.X.	X.X.X	LX.X.	X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXXLX

[EventHorizon]

Dont think you can do this one either. Two people can only eliminate one (different) hole per day.

If you leave one person checking the same hole every day, the problem essentially turns into the original groundhog problem but with 11 holes. But this is nowhere near optimized.

[EventHorizon]

Ok, so I did one better than I previously thought. 3 people, 29 days if you only need to know where it is and 30 if you have to look in it's hole.

. = a hole the groundhog could be in today.

X = a hole the groundhog cannot be in today.

L = a hole that is checked today.

  1	  2	  3	  4	  5	  6	  7	  8	  9	 10	 11	 12	 13	 14	 15


.L.L.	L.X..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.	X.X.L	.X.X.	X.X.X	.X.X.

..L..	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.	X.X.X

.....	L....	.L...	X....	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X..	.X.L.	X.X.L	.X.X.

.....	.....	L....	.L...	X....	.L...	X....	.L...	X.L..	.X...	X.L..	.X...	X.L..	.X.L.	X.X.L

.....	.....	.....	L....	.....	L....	.L...	X....	.L...	X....	.L...	X.L..	.X...	X.L..	.X.LL


 16	 17	 18	 19	 20	 21	 22	 23	 24	 25	 26	 27	 28	 29	 30


XLXLX	LXXX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX	XXXXL	XXXXX	XXXXX	XXXXX

.XLX.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX	XXXXX

X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXX.	XXXLX	XXXXL	XXXXX

.X.X.	X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXX.X	XXLX.	XXXLX	XXXXL

X.X.X	.X.X.	X.X.X	LX.X.	X.X.X	LX.X.	XLX.X	XX.X.	XLX.X	XX.X.	XLX.X	XXLX.	XXX.X	XXLX.	XXXLX

Wow. That's really cool. Wish I would have tried to answer it myself before looking. I hadn't really thought about the answer that much when I came up with the question, either. Actually, I think I may program up a simulator so people can play around with these easily (both with deterministic and non-deterministic groundhogs). Also, it seems like it would make a nice little mini-game for my will-only-ever-exist-in-my-mind RPG.

You got the answer I did for 2, and used the method I thought I would for 3. So, as for this thread... I'll have to say it's answered by Tuckleton (unless someone happens to beat your time). Good Job.

[EventHorizon]

You cannot guarantee to find the groundhog in a finite number of days. No matter what hole you pick the groundhog could be in any hole after he moves. Say you picked 2. The groundhog could go stay in 1 from 1, go to 2 from 1, go to 3 from 4, go to 4 from 3 or go to 5 from 4. And you are right back where you started. This is true for any hole you might pick so you can never be guaranteed to find the groundhog.

The groundhog always has a choice of two holes to go to, and you can only check one of them. QED

[Guest]

4 times!!

[Guest]

Wow. That's really cool. Wish I would have tried to answer it myself before looking. I hadn't really thought about the answer that much when I came up with the question, either. Actually, I think I may program up a simulator so people can play around with these easily (both with deterministic and non-deterministic groundhogs). Also, it seems like it would make a nice little mini-game for my will-only-ever-exist-in-my-mind RPG.

You got the answer I did for 2, and used the method I thought I would for 3. So, as for this thread... I'll have to say it's answered by Tuckleton (unless someone happens to beat your time). Good Job.

Yeah I had a lot of fun with it, thanks for posting! I thought it was cool how the solutions are basically all the same as the original, where the answer was 234234, the solutions for 2 and 4 were basically combing through the holes twice in the same way, around opposite sides of the circle in 2 and in diagonal lines in the 4th.

[xp2008]

For 1st question, we can't guarantee to find it. Supposing groundhog knows your strategy, thus knows which hole you check next day, it can always avoid it because it has always 2 choices for next's hole.