Problem

Source: 2002 Estonia National Olympiad Final Round grade 9 p5

Tags: combinatorics



There were $n> 1$ aborigines living on an island, each of them telling only the truth or only lying, and each having at least one friend among the others. The new governor asked each aborigine whether there are more truthful aborigines or liars among his friends, or an equal number of both. Each aborigine answered that there are more liars than truthful aborigines among his friends. The governor then ordered one of the aborigines to be executed for being a liar and asked each of the remaining $n- 1$ aborigines the same question again. This time each aborigine answered that there are more truthful aborigines than liars among his friends. Determine whether the executed aborigine was truthful or a liar, and whether there are more truthful aborigines or liars remaining on the island.