Author |
Topic: Interview question: wolves and sheep (Read 14262 times) |
|
Benny
Uberpuzzler
Gender: 
Posts: 1024
|
 |
Interview question: wolves and sheep
« on: Apr 20th, 2010, 3:45pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Interview question: wolves and sheep
« Reply #1 on: Apr 20th, 2010, 5:45pm » |
Quote Modify
|
64 wolves (and one sheep).
First note that the number of sheep is unchanging: a wolf eats a sheep and becomes a sheep--still one sheep.
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.
Any even number of wolves is stable, any odd number results in a single wolf eating the sheep.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Interview question: wolves and sheep
« Reply #2 on: Apr 21st, 2010, 10:38am » |
Quote Modify
|
Yes.
Would you get a different outcome if the number of sheep at the start is more than 1, say, 2, 3,...?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Interview question: wolves and sheep
« Reply #3 on: Apr 21st, 2010, 12:00pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
sqnwk
Newbie
Posts: 2
|
|
Re: Interview question: wolves and sheep
« Reply #4 on: Apr 24th, 2010, 10:41pm » |
Quote Modify
|
in the end, you'll have one sheep
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Interview question: wolves and sheep
« Reply #5 on: Apr 25th, 2010, 2:56pm » |
Quote Modify
|
on Apr 24th, 2010, 10:41pm, 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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Interview question: wolves and sheep
« Reply #6 on: Apr 25th, 2010, 3:13pm » |
Quote Modify
|
My response to your second question indicates that more clarification is needed: are the wolves allowed to strategize with one another?
|
|
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Interview question: wolves and sheep
« Reply #7 on: Apr 25th, 2010, 3:58pm » |
Quote Modify
|
on Apr 25th, 2010, 3:13pm, 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.
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Interview question: wolves and sheep
« Reply #8 on: Apr 25th, 2010, 4:13pm » |
Quote Modify
|
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.)
|
| « Last Edit: Apr 25th, 2010, 4:31pm by Obob » |
IP Logged |
|
|
|
Benny
Uberpuzzler
Gender:
Posts: 1024
|
|
Re: Interview question: wolves and sheep
« Reply #9 on: May 7th, 2010, 11:32am » |
Quote Modify
|
Thank you Obob. Have you studied combinatorial game theory?
|
|
IP Logged |
If we want to understand our world — or how to change it — we must first understand the rational choices that shape it.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Interview question: wolves and sheep
« Reply #10 on: May 7th, 2010, 11:44am » |
Quote Modify
|
No. You just need induction to analyze this.
|
|
IP Logged |
|
|
|
cynder
Newbie
Posts: 3
|
|
Re: Interview question: wolves and sheep
« Reply #11 on: May 28th, 2010, 7:12pm » |
Quote Modify
|
on Apr 20th, 2010, 3:45pm, 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.
|
| « Last Edit: May 28th, 2010, 7:15pm by cynder » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Interview question: wolves and sheep
« Reply #12 on: May 28th, 2010, 10:22pm » |
Quote Modify
|
on May 28th, 2010, 7:12pm, cynder wrote:
After that you have 65 sheep living happily on grass. Theyre commies.
|
|
Don't you mean 'hippies'? 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
cynder
Newbie
Posts: 3
|
|
Re: Interview question: wolves and sheep
« Reply #13 on: May 29th, 2010, 5:31pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interview question: wolves and sheep
« Reply #14 on: May 30th, 2010, 1:38am » |
Quote Modify
|
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.
|
| « Last Edit: May 30th, 2010, 1:39am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cartoonle
Junior Member
Gender:
Posts: 56
|
|
Re: Interview question: wolves and sheep
« Reply #15 on: Dec 13th, 2012, 4:08am » |
Quote Modify
|
| hidden: | | If the wolves can't resist the sheeps, you'll have one sheep at the end. |
|
|
IP Logged |
friv - something i've built
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print