wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Interview question: wolves and sheep
        
(Message started by: BenVitale on Apr 20th, 2010, 3:45pm)
Title: Interview question: wolves and sheep
Post by BenVitale on Apr 20th, 2010, 3:45pm
Imagine that there are some wolves and some sheep living on a field. Sheep love to eat grass and wolves love to eat sheep. But the caveat is that if a wolf eats a sheep, he becomes a sheep. So, assuming the wolves are rational and want to avoid dying as much as possible (assume that they have another food source that is not as tasty as sheep), if you start with 65 wolves and one sheep, how many wolves do you have after a while?
Title: Re: Interview question: wolves and sheep
Post by SMQ on Apr 20th, 2010, 5:45pm
[hide]64 wolves (and one sheep).
[/hide]
[hide]First note that the number of sheep is unchanging: a wolf eats a sheep and becomes a sheep--still one sheep.
[/hide]
[hide]Now work by induction:
- 1 sheep, 0 wolves -- happy sheep.
- 1 sheep, 1 wolf -- wolf eats sheep, happy sheep.
- 1 sheep, 2 wolves -- no wolf eats the sheep.
- 1 sheep, 3 wolves -- a wolf eats the sheep, then stable.
- etc.
[/hide]
[hide]Any even number of wolves is stable, any odd number results in a single wolf eating the sheep.
[/hide]
--SMQ
Title: Re: Interview question: wolves and sheep
Post by BenVitale on Apr 21st, 2010, 10:38am
Yes.

Would you get a different outcome if the number of sheep at the start is more than 1, say, 2, 3,...?
Title: Re: Interview question: wolves and sheep
Post by Obob on Apr 21st, 2010, 12:00pm
With 2 wolves and 2 sheep, either the 2 wolves agree to eat sheep simultaneously, or neither can eat a sheep for fear of having a 50% chance of being eaten by the remaining wolf.
Title: Re: Interview question: wolves and sheep
Post by sqnwk on Apr 24th, 2010, 10:41pm
in the end, you'll have one sheep
Title: Re: Interview question: wolves and sheep
Post by BenVitale on Apr 25th, 2010, 2:56pm

on 04/24/10 at 22:41:28, sqnwk wrote:
in the end, you'll have one sheep


Wow, could you please explain how you reached that conclusion?


P.S. The second question I posted is a question of combinatorial game theory (CGT). I won't attempt to solve it using CGT becoz I haven't studied yet, but I will next semester.

Perhaps we could try to address the second question without using CGT.
Title: Re: Interview question: wolves and sheep
Post by Obob on Apr 25th, 2010, 3:13pm
My response to your second question indicates that more clarification is needed:  are the wolves allowed to strategize with one another?
Title: Re: Interview question: wolves and sheep
Post by BenVitale on Apr 25th, 2010, 3:58pm

on 04/25/10 at 15:13:50, Obob wrote:
My response to your second question indicates that more clarification is needed:  are the wolves allowed to strategize with one another?


Yes, the sheep and the wolves are all rational.

Actually, I thought about the second question and have asked my math prof about how to address it. He asked me to wait till I take combinatorial game theory.

I also wondered whether I could use Aesop's "Wolf in Sheep's Clothing" fable in this problem.
Title: Re: Interview question: wolves and sheep
Post by Obob on Apr 25th, 2010, 4:13pm
Assuming simultaneous eating is allowed:

With 2 sheep:

1 wolf:  the wolf eats a sheep.
2 wolves:  the wolves both simultaneously eat both sheep.
3 wolves:  no sheep are eaten.
4 wolves:  one wolf eats a sheep.
5 wolves:  two wolves simultaneously eat both sheep.
6 wolves:  no sheep are eaten.
7 wolves:  one wolf eats a sheep.
etc.

With 3 sheep:

1 wolf:  wolf eats.
2 wolves:  both wolves simultaneously eat.
3 wolves:  all 3 wolves simultaneously eat.
4 wolves:  no sheep are eaten.
5 wolves:  one wolf eats a sheep.
6 wolves:  two wolves simultaneously eat.
7 wolves:  three wolves simultaneously eat.
8 wolves:  no sheep are eaten.
etc.

The general pattern is clear from this.  If the wolves aren't allowed to eat simultaneously, the story is different.

Without simultaneous eating:

2 sheep:

1 wolf: wolf eats
2 wolves:  no sheep eaten
3 wolves:  one wolf eats
4 wolves:  no sheep eaten

etc.  Without simultaneous eating, there is essentially no difference between the cases with more than 1 sheep and the case with 1 sheep.  (This is assuming that when a wolf is deciding whether to eat a sheep or not, he either has no preference for sheep that didn't used to be wolves, or can't tell which sheep used to be wolves; if they can tell which sheep used to be wolves, they could essentially copy the simultaneous eating strategy.)
Title: Re: Interview question: wolves and sheep
Post by BenVitale on May 7th, 2010, 11:32am
Thank you Obob. Have you studied combinatorial game theory?
Title: Re: Interview question: wolves and sheep
Post by Obob on May 7th, 2010, 11:44am
No.  You just need induction to analyze this.
Title: Re: Interview question: wolves and sheep
Post by cynder on May 28th, 2010, 7:12pm

on 04/20/10 at 15:45:27, BenVitale wrote:
Imagine that there are some wolves and some sheep living on a field. Sheep love to eat grass and wolves love to eat sheep. But the caveat is that if a wolf eats a sheep, he becomes a sheep. So, assuming the wolves are rational and want to avoid dying as much as possible (assume that they have another food source that is not as tasty as sheep), if you start with 65 wolves and one sheep, how many wolves do you have after a while?


The wolves agree to slay the sheep and then share the meat. After that you have 65 sheep living happily on grass. Theyre commies.

Added: Incase they need to eat a whole sheep to turn into a sheep you will end with 65 wolves and 0 sheep.
Title: Re: Interview question: wolves and sheep
Post by ThudanBlunder on May 28th, 2010, 10:22pm

on 05/28/10 at 19:12:01, cynder wrote:
After that you have 65 sheep living happily on grass. Theyre commies.

Don't you mean 'hippies'?  ::)
Title: Re: Interview question: wolves and sheep
Post by cynder on May 29th, 2010, 5:31pm
Youre absolutely right, that would better explain the love for grass.

On another note; I have no idea what the original "correct" awnser means. Why is 64 wolves + 1 sheep stable and why is, for example, 63 wolves + 1 sheep not stable? It just doesnt make any logical sense to me, could someone please explain the awnser in a logical manner?
Title: Re: Interview question: wolves and sheep
Post by towr on May 30th, 2010, 1:38am
It depends on induction.
* If there's only a sheep, that's stable right?
* If by eating a sheep you go to a stable situation, then it is safe to do so, which makes the current state unstable (since you change it to another).
* If by eating a sheep you move to an unstable state, then it is not safe to eat the sheep, because you risk being eaten once turned into a sheep. So therefore you shouldn't eat the sheep, which thus makes the current state stable (since you won't change it).
And so the stable and unstable states alternate: if there are 2n wolves and a sheep the state is stable, and when there are 2n+1 wolves and a sheep it is not.
Title: Re: Interview question: wolves and sheep
Post by cartoonle on Dec 13th, 2012, 4:08am
[hideb]If the wolves can't resist the sheeps, you'll have one sheep at the end.[/hideb] :)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board