YesNoOk
avatar

monkey shootin' (Read 4214 times)

Started by Valodim, September 29, 2012, 09:47:11 pm
Share this topic:
monkey shootin'
#1  September 29, 2012, 09:47:11 pm
  • ******
    • Germany
Here's a little something to think about:

There are trees next to each other to form a line of n trees. In one of these trees, there is a monkey. You are a hunter, and you want to shoot the monkey, but you don't know which tree he is in. You can shoot any tree, if the monkey is in it you win, if he isn't, he will move to a tree next to the one he was in before. This tree could also be the one you just shot.

Is there a way for the hunter to be sure to hit the monkey eventually? If so, in how many steps for n trees?

Hint: try small instances of n first. Don't google. Also, use the [spoiler] tag and note if there is a hint, solution or discussion inside.
Re: monkey shootin'
#2  September 29, 2012, 10:02:32 pm
  • avatar
  • ******
    • Thailand
I'll get the easy solutions out of the way.

Spoiler: Solution for 2 trees (click to see content)

Spoiler: Cheating Solution (click to see content)

     Posted: September 29, 2012, 10:06:53 pm
Spoiler: Solution for 3 trees (click to see content)
Re: monkey shootin'
#3  September 29, 2012, 10:34:51 pm
  • ******
  • [E]
    • Mexico
rajaa: this is similar to a programming question in a contest, the most important thing here is that N can be any number.
spoiler for brute force answer
Spoiler, click to toggle visibilty
Re: monkey shootin'
#4  September 29, 2012, 10:41:53 pm
  • ******
    • Germany
spoiler for brute force answer
Spoiler, click to toggle visibilty

the monkey can move to the tree you just shot.
Re: monkey shootin'
#5  September 29, 2012, 10:49:24 pm
  • avatar
  • ******
    • Thailand
rajaa: this is similar to a programming question in a contest, the most important thing here is that N can be any number.
spoiler for brute force answer
Spoiler, click to toggle visibilty

That's why those are only the solutions for 2 and 3 trees. Not a formula to get the monkey for any amount of trees. The concept is easy to grasp, the single solution for all number of trees, if there is one, requires some thought.


And as Valodim, said your solution doesn't work. If there are three trees and you shoot the first tree and the monkey is in the second tree, then the monkey could either move to the first tree or third tree and your "shoot across all trees until you get it" solution could go on forever, given the monkey is lucky and you are unlucky (probability-wise).
Last Edit: September 29, 2012, 10:52:49 pm by Rajaa
Re: monkey shootin'
#6  September 29, 2012, 10:50:36 pm
  • ******
  • Double-Crosser
  • I'm not standing out. This isn't weird at all.
    • USA
Spoiler: most logical answer (click to see content)
Re: monkey shootin'
#7  September 29, 2012, 11:10:42 pm
  • ******
  • Unity of Hearts
    • Spain
Not really good at this but let's try it:

Spoiler, click to toggle visibilty

Unfortunately, developing a formula from these conclusions is something I'm not really good at.
Last Edit: September 29, 2012, 11:13:59 pm by Nanashi_1337
Re: monkey shootin'
#8  September 29, 2012, 11:11:32 pm
  • ******
  • [E]
    • Mexico
spoiler for brute force answer
Spoiler, click to toggle visibilty

the monkey can move to the tree you just shot.

yeah, good point, the real hint is that the monkey has to move.

Spoiler, click to toggle visibilty
Last Edit: September 29, 2012, 11:17:25 pm by [E]
Re: monkey shootin'
#9  September 30, 2012, 01:19:26 am
  • *****
  • The Only Easy Day was Yesterday
    • USA
    • www.facebook.com/truemicah
Spoiler, click to toggle visibilty
Last Edit: September 30, 2012, 01:58:11 am by TRUEMicah
Re: monkey shootin'
#10  September 30, 2012, 01:31:02 am
  • ******
  • 日本は素晴らしい国です。
he can go back, so if you shoot tree one, and he was in tree two, he can move to tree one as you reposition yourself to shoot tree 2.

So the answer is,
Spoiler, click to toggle visibilty
Re: monkey shootin'
#11  September 30, 2012, 01:41:41 am
  • avatar
  • ****
    • USA
Spoiler, click to toggle visibilty
Re: monkey shootin'
#12  September 30, 2012, 01:48:36 am
  • ******
  • 日本は素晴らしい国です。
Spoiler, click to toggle visibilty

     Posted: September 30, 2012, 01:51:23 am
wait what about


Spoiler, click to toggle visibilty
Re: monkey shootin'
#13  September 30, 2012, 01:53:09 am
  • ******
    • Germany
-  Start shooting at tree #1.
-  Shoot all trees in line order until you've shot n amount of trees.
   -  With this process, the monkey will eventually have no place to run. 

nice job using spoilers there.

also you're all wrong :P
Re: monkey shootin'
#14  September 30, 2012, 01:56:22 am
  • avatar
  • **
    • florin_matei1996@hotmail.com
Another way
Spoiler, click to toggle visibilty
Re: monkey shootin'
#15  September 30, 2012, 01:59:07 am
  • ******
    • Germany
this is not a thinking outside the box thing, you can't shoot all trees at once or something like that :P
Re: monkey shootin'
#16  September 30, 2012, 02:07:37 am
  • avatar
  • **
    • florin_matei1996@hotmail.com
Spoiler, click to toggle visibilty
Re: monkey shootin'
#17  September 30, 2012, 02:10:30 am
  • ******
    • Germany
it's not a statistical thing either, the question is, how do I reliably and deterministically shoot the monkey, and how many shots do I need

@Bea: or @Cybaster: to the rescue :)
Re: monkey shootin'
#18  September 30, 2012, 02:12:07 am
  • avatar
  • ****
    • USA
Spoiler, click to toggle visibilty
Re: monkey shootin'
#19  September 30, 2012, 02:13:20 am
  • avatar
  • ****
    • Canada
    • www.mugencoder.com
I swear this is related to something of a sort algorithm.. namely bubble sort.

Spoiler, click to toggle visibilty

Bea

Re: monkey shootin'
#20  September 30, 2012, 02:41:49 am
  • *****
  • MUGEN Grandma
    • Brazil
    • www.smeenet.org
I am too busy drinking wine and dressing up for tonight's date to look at this thing right now.

I'd probably use something akin to

Spoiler, click to toggle visibilty

to shot the bloody monkey down.
Princess Adora: "My friend saw She-Ra take her dress off in the shower. She said she has an 8 pack. She said She-Ra is shredded."

SF2NES is dead. Long live SF2NES.