Tigers and a sheep

FreeGame theoryEasyJane StreetSIGDE Shaw

On a magic island covered in grass live 100 tigers and 1 sheep. The tigers can eat grass but prefer sheep. Each time, only one tiger may eat the sheep, and after doing so it turns into a sheep itself. All tigers are intelligent, perfectly rational, and value survival. Will the sheep be eaten?

Solution

We determine the outcome by backward induction on the number of tigers, nn. The key observation is that a tiger will eat the sheep only if doing so guarantees its own survival after it turns into a sheep.

  • n=1n=1: The lone tiger eats the sheep, becomes a sheep, and faces no remaining tigers. It survives, so the sheep is eaten.
  • n=2n=2: If a tiger eats the sheep, it becomes a sheep, leaving one tiger and one sheep. By the n=1n=1 case, that remaining tiger will eat the new sheep, so the first tiger would die. Since tigers value survival, neither will eat. The sheep survives.
  • n=3n=3: If a tiger eats, it becomes a sheep, leaving two tigers and one sheep. From n=2n=2, the two tigers will not eat the sheep (they would die), so the eating tiger survives. Hence some tiger will eat, and the sheep is eaten.
  • n=4n=4: Eating leads to the n=3n=3 case, where the sheep is eaten, so the eating tiger would die. No tiger eats; the sheep survives.

Continuing this logic, the sheep is eaten if and only if nn is odd. For n=100n=100 (even), no tiger will eat the sheep.

Related problems