Understanding the solution of a riddle about lions and sheep.

Question

I heard a riddle once, which goes like this:

There are N lions and 1 sheep in a field. All the lions really want to eat the sheep, but the problem is that if a lion eats a sheep, it becomes a sheep. A lion would rather stay a lion than be eaten by another lion. (There is no other way for a lion to die than to become a sheep and then be eaten).

I was presented with this solution:

If there were 1 lion and 1 sheep, then the lion would simply eat the sheep.

If there were 2 lions and 1 sheep, then no lion would eat the sheep, because if one of them would, it would surely be eaten by the other lion afterwards.

If there were 3 lions, then one of the lions could safely eat the sheep, because it would turn in to the scenario with 2 lions, where no one can eat.

Continuing this argument, the conclusion is as follows:

• If there is an even number of lions, then nothing happens.

• If there is an odd number of lions, then any lion could safely eat the sheep.

But to me this seems utterly absurd. I think this is similar to the Unexpected Hanging Paradox (Link: http://en.wikipedia.org/wiki/Unexpected_hanging_paradox). I might have forgotten some assumptions, and those assumptions might actually solve this problem.

Is there a fault in the argument which I haven't discovered? Does anyone have any insights? Is the argument sound?

Answer 1

I am still looking for a better answer on this: here's my thoughts so far - hope it gives a basis for a better response.

"Continuing this argument" is like pulling a rabbit out of a hat, or the proof that all odd numbers are prime (1 is prime, 3 is prime, 5 is prime, so "continuing the argument" they all are).

Let's set up a formal proof by induction.

The inductive hypothesis is "for n lions, a lion can safely eat the sheep if n is odd, and if n is even it is not safe and so nothing happens". You have shown this is true for n = 1, 2, and 3.

The inductive proof requires we if we assume true for n then we show true for n + 1 (for n >= 3 as already proved for n = 1, 2).

If n + 1 is odd and a lion eats a sheep then we have n lions remaining, and n is even so nothing happens. If n + 1 is even then n is odd so the lion that just ate the sheep will be eaten - hence if n + 1 is even no lion should eat the sheep.

So we have shown that if true for n then also true for n + 1. I.e. the inductive proof is complete.

However, I also remain unconvinced.

P.S. My understanding of the resolution of the unexpected hanging paradox is that the initial statement that 'the prisoner will be hung by surprise one day next week" contains a contradiction, i.e. if it is Friday then it isn't a surprise. The paradox is resolved when the statement is changed to 'the prisoner will be hung one day next week: either on Friday, or by surprise".

I don't think that the scenario here is the same.

Answer 2

Maybe you have doubts whether lions can count up to 101 or have the notion of odd and even. So here is another version of the story:

A certain university has just one math chair, which is inhabited right now. There are $N$ (male) mathematicians aspiring for that chair, and the guy who kills the prof becomes his successor.

Answer 3

If all the lions acts rational and all the lions are aware of that and aware of the other circumstances, it is safe for the moment for a lion to eat the sheep if the number of lions is odd. But if there are any doubt of the rationality or doubt of that all the lions fully understand the situation, it is very unsafe, regardless of the number of lions.

Also, lions could loose their memory or otherwise turn less perfect. So if I was a lion I wouldn't eat, especially since I'm a vegetarian.

But, if a lion know that the other lions wouldn't dare anyway, it could eat the sheep and be safe for the moment.

If the sheep only can die by be eaten, the probability for eternal status quo is zero as long as the sheep is alive, regardless the number of lions. So the lion with most patience would wait an indefinite period to be the last lion, and would then decide if he want to eat the ship and live alone or want the company of the sheep for the rest of its life.

Answer 4

The answer is you have missed an assumption at your question which you have brought it at your comments, "lions want to eat the sheep but not in cost of death". You have mentioned at your question that lions want to eat the sheep and if a lion eats the sheep, it will become the sheep himself and then it is in danger of being eaten and death. The argument you have brought after it is using the statement "A lion eat the sheep if and only if it won't die." and your argument currently is using the induction so the fault is not using induction or not, the fault is you didn't mention that is the key statement a fact or a guess.

Answer 5

Let me try to set an equivalent to this up in a different and more game-like fashion:

Suppose we play a game with $N$ people (say mathematicians) standing in a line where one ore more persons can win a prize. The prizes are distributed following some simple rules:

1. At any state of the game, the person in front is allowed to leave the line claiming a big prize of 100,000 dollars
2. But only the last person who left and made such a claim will actually get to receive that prize
3. On the other hand, everyone who is still in the line when at some point the front person decides to stay whereby the game ends, will each receive 100 dollars

So the question is how these $N$ mathematicians will act depending on $N$. Should the front person go for the big prize, or will that result in that person loosing everything since the next person will take over the claim? And we assume they have no social skills (very realistic, since they are mathematicians ;) so each person plays for his/her own benefit and they won't share the money afterwards.

Answer 6

My guess is the Lion will think only in the short term.

• Lion sees sheep, eats it, become one.
• Lion sees sheep, eats it, become one.
• Lion sees sheep, eats it, become one.
• Lion sees sheep, eats it, become one.

Note that at any point in this process there is only one sheep in your arrangement.

---

If these lion agents are more cognizant, maybe they will notice their colleagues turning in to sheep and refrain. They seem to be indifferent about whether or not they are sheep? From a game theory point of view, there is a slight Prisoner's Dilemma situation. The optimal strategy is unstable. If the lions do not fully cooperate, they all kill each other in succession.

If even one lion does not cooperate at any time, it renders the situation unstable for all lions.

I have been thinking about what happens if one of the lions temporarily leaves the room, and it becomes optimal to eat the sheep once. Then if the lion returns, and it becomes optimal for the sheep to be eaten again.

These propositions I make need proof, but I feel your solution has some instability. You might see this discussion in philosophy class, and I have pointed to Stanford's encyclopedia.

Answer 7

I think that the confusion perhaps arises at least partially because there's no defined order in which the lions would eat. The fact that every lion would want to eat the sheep if there were an odd number of lions seems suspicious. I think the easiest way to visualize the solution is this:

Number the lions from $1$ to $n$, where the order is such that $i^{th}$ will eat before the $(i-1)^{th}$ lion - thus the $n^{th}$ lion eats first and the $1^{th}$ lion eats last. We can call each lion either "hungry" or "scared", according to its strategy. Call the $i^{th}$ lion is hungry if it would eat the $(i+1)^{th}$ lion, were it to eat - equivalently, the $i^{th}$ lion would eat if it were the highest numbered remaining lion. If it would not eat, then the lion shall be called "scared".

We can easily see that the lion #1 is always hungry because, were he to have the opportunity to eat, there would be no other lions remaining to eat him. Lion #2 is scared, knowing that lion #1 is hungry and would eat him should he eat. Lion #3 is again hungry, knowing that lion #2 is scared and will not eat him. More generally, the $i^{th}$ lion is scared whenever the $(i-1)^{th}$ is hungry and is hungry only when their predecessor is scared.

Thus, it is clear that, when ordered this way, the lions should have alternating strategies, and the first lion (i.e. the last to eat) is hungry. Easily, from this, you see that all even lions are scared and all odd ones are hungry - and thus, if $n$ is odd, the $n^{th}$ lion, the only one who actually gets a choice, is hungry, and thus eats, but if $n$ is even, the $n^{th}$ lion is scared, and thus does not eat.

This approach strikes me as more intuitive than the naive inductive approach, since we can create a infinite string of H's (hungry) and S's (scared), where the $i^{th}$ lion has the strategy given by the $i^{th}$ character, and that this string does not change given the number of lions - so the lions do not need to count to solve it, they just need to know whether their predecessor is hungry. The string being, of course:

H S H S H S H S ...

And the situation of $n$ lions is merely what arises when we truncate that to the first $n$ characters.

Answer 8

Some insight comes from experimental game theory. What we find is that equilibrium solutions that should hold in theory and use induction often don't hold in practice. I think one reason that the theory doesn't correspond to the empirical evidence is because the induction argument is very hard to grasp when we are far away from the base case. One example, among many, is the Centipede game (http://en.wikipedia.org/wiki/Centipede_game) where the best response is always to defect and accept a small prize but in practice we always find that the players continue until near the final stages.

Answer 9

None of the answers posted here are actually fully correct.

Let us use the formulation of the problem as posted on the braingle website: http://www.braingle.com/brainteasers/teaser.php?id=9026&comm=0

The backward induction solution to the problem (where the sheep survives if the number of lions is even, and gets eaten if the number of lions is odd) can only be applied if lions have common knowledge of lion rationality. It is not enough for lions to just be "infinitely logical, smart, and completely aware of their surroundings". It is even not enough for lions to know that all other lions are rational! Common knowledge is much stronger than that, and means that everyone knows that everyone knows that everyone knows ... etc. etc.

Only then can we start applying backward induction! And the original problem formulation makes no such statement about common knowledge of rationality - which is a very strong statement to make!

Note that when I used the word "knowledge" above, I used a very strict definition of knowledge - knowledge is a true belief, which holds regardless of any new information becoming available.

Merely having common belief in rationality is not enough for a backward induction solution here! Imagine a situation with 4 lions: what happens if the 4th lion decides to eat the sheep, contrary to what the backward induction solution says he should do? This will invalidate the common belief of all the other lions in common rationality, which was the prerequisite for the backward induction solution! So lion 3 can no longer assume that lion 2 will never eat the sheep - after all, lion 4 just did! And since above all, lions do not want to be eaten, lion 3 will no longer eat the sheep. Turns out the behavior of lion 4 was rational after all, assuming lions did not have common knowledge in rationality at the start!

This explains why a lot of people feel unsatisfied with the backward induction solution to this problem, and why they feel that this problem is a paradox. They are completely right to be unsatisfied! Common knowledge in rationality is an extremely strong condition, and is unrealistic in most practical scenarios. And in fact in this problem, even common belief in rationality is not stated, merely the rationality of each individual lion, which completely invalidates the backward induction solution - even with only 2 lions, lion 2 cannot reason about what 1 lion would do if he doesn't hold a belief or knowledge of that lion's rationality (which cannot automatically be assumed)!