Jump to content
BrainDen.com - Brain Teasers
  • 0


EventHorizon
 Share

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

Link to comment
Share on other sites

15 answers to this question

Recommended Posts

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

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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
Link to comment
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

Link to comment
Share on other sites

  • 0

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

Link to comment
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

Link to comment
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.

Link to comment
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
Link to comment
Share on other sites

  • 0

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.

Link to comment
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...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...