One hundred tigers and one sheep live on a magic island covered in grass. Tigers can eat grass, but they would rather eat sheep. A tiger that eats the sheep turns into a sheep itself, and can then be eaten by another tiger. Every tiger is perfectly rational and wants above all to survive. Will the sheep be eaten?
Short answer: No. With an even number of tigers the sheep is safe, and 100 is even.
Step 1: Shrink the island to one tiger
One hundred rational tigers is too many to reason about directly, so start with the smallest island that still has a decision on it. With one tiger and one sheep, the tiger eats the sheep without hesitation. It becomes a sheep, but there is no other tiger left to eat it, so it is perfectly safe. One tiger: the sheep is eaten.
With two tigers, either tiger that eats becomes a sheep on an island with one tiger. We have just shown that a one-tiger island ends with the sheep eaten. So eating is suicide, both tigers know it, and both eat grass. Two tigers: the sheep is safe.
Step 2: Build the induction
With three tigers, a tiger that eats turns the island into two tigers and one sheep, which we know is safe for the sheep. So the first tiger to eat is safe, and the sheep is eaten. With four tigers, eating creates a three-tiger island, where the new sheep would be eaten, so nobody eats.
The pattern alternates: odd numbers of tigers eat, even numbers do not. Formally, let eaten(n) be true if the sheep is eaten with n tigers. eaten(1) is true, and eaten(n) is true exactly when eaten(n - 1) is false, because a tiger eats only when the island it creates is safe for the new sheep. So eaten(n) is true exactly when n is odd.
Step 3: Apply it to 100 tigers
One hundred is even, so no tiger eats. Each tiger reasons that eating would leave 99 tigers and one sheep, an odd island where that sheep, the tiger itself, gets eaten. The grass is the rational choice, and the sheep lives on.
The assumption that does the heavy lifting is common knowledge of rationality: every tiger knows every other tiger can run the same induction to the bottom. Drop it and the answer is no longer a clean parity rule. That is worth saying in the interview, because it shows you know which assumption the proof depends on rather than just remembering the word even.
Step 4: Why it is in the same family as the pirates
This is the same backward-induction pattern as Screwy Pirates: the answer for n depends only on the answer for n - 1, so you solve the smallest case and climb. Recognising that family on sight is what interviewers are really testing, because the next puzzle they give you will wear a different story.
Why interviewers ask it
State the base case, the recursive step and the parity conclusion in that order. Candidates who guess 'yes, the hungriest tiger eats' without testing small cases are exactly who this question screens out.
Knowing the proof is half of it. Work Tiger and Sheep interactively, then take it under a clock with the rest of the Outcry simulators.