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

Question

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

Share this post


Link to post
Share on other sites

15 answers to this question

Recommended Posts

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

Share this post


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

Share this post


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

Share this post


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

:P

Share this post


Link to post
Share on other sites
  • 0

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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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

;)
  • Like 1

Share this post


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

Share this post


Link to post
Share on other sites
  • 0

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.

 

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