Lions and Gazelle: Backward Induction
A magical savanna has an odd number $n$ of lions and one gazelle. The lions are hungry and want to eat the gazelle, but if a lion eats a gazelle (or another lion that has become a gazelle), it falls asleep and transforms into a gazelle itself -- making it vulnerable to being eaten by the remaining lions.
Each lion is rational: it wants to eat if possible, but it values survival above all else. A lion will only eat if it can guarantee it won't be eaten afterward.
How many gazelles are consumed when $n = 15$?
Hints
- Don't try to analyze 15 lions directly -- start with 1 lion, then 2, then 3, and look for a pattern.
- The key question for each lion is: if I eat and become a gazelle, is the resulting configuration with $n - 1$ lions safe for me?
- The answer depends entirely on parity. With an odd number of lions, eating reduces to an even number where nobody eats. With an even number, eating reduces to an odd number where someone will eat you.
Worked Solution
How to Think About It: This is a classic backward induction puzzle. Don't try to reason about 15 lions directly -- start from the simplest case and build up. The key tension is that eating makes you vulnerable, so a lion will only eat if the resulting configuration is "safe" for it. The trick is figuring out which configurations are safe.
Quick Estimate: The answer is going to depend on the parity of $n$. With 1 lion, it obviously eats. With 2 lions, eating is suicidal. The pattern should alternate, and since 15 is odd, we expect 1 gazelle consumed.
Approach: Build the solution inductively from $n = 1$ upward.
Formal Solution:
- $n = 1$: One lion, one gazelle. The lion eats freely since no other lion can threaten it. Gazelles consumed: $1$.
- $n = 2$: If lion A eats the gazelle, A becomes a gazelle and we are in the $n = 1$ scenario with lion B. Lion B will eat lion A. Since lion A values survival, it does not eat. Gazelles consumed: $0$.
- $n = 3$: If lion A eats the gazelle, A becomes a gazelle and we are in the $n = 2$ scenario. We just showed that with 2 lions, neither eats. So lion A is safe after eating. Lion A eats. Gazelles consumed: $1$.
- $n = 4$: If lion A eats, we reduce to $n = 3$. With 3 lions, one lion eats -- meaning lion A (now a gazelle) gets eaten. So lion A does not eat. Gazelles consumed: $0$.
The pattern is clear:
- Odd $n$: Exactly 1 gazelle is consumed. The first lion to eat knows the remaining even number of lions will be in a stalemate.
- Even $n$: No gazelles are consumed. Eating would leave an odd number of lions, and the eater (now a gazelle) would be eaten.
For $n = 15$ (odd), exactly one lion eats the gazelle, and then the remaining 14 lions are in a stalemate.
Answer: With $n = 15$ lions, exactly $1$ gazelle is consumed.
Intuition
This problem is a beautiful example of backward induction in game theory -- the same reasoning that drives subgame perfect equilibrium in sequential games. Each lion solves the game "from the end" before making its decision. The parity structure emerges because each action flips the game between two regimes: safe (even, stalemate) and dangerous (odd, someone acts).
This pattern appears throughout finance and trading. Market makers face analogous reasoning: taking a position (eating) exposes you to adverse selection (being eaten). Whether it's safe to act depends on how many other rational agents remain and what they'll do in response. The key lesson is that in sequential games with rational agents, you must reason backward from the terminal state, not forward from the current one. The answer is often surprisingly simple once you identify the recursive structure.