IMO 1994 SL C2

Origin: COL | Category: Combinatorics

Problem

In a certain city, age is reckoned in terms of real numbers rather than integers. Every two citizens x and x′ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens x = x0, x1, . . . , xn = x′ for some integer n \geq2 such that xi−1 and xi know each other. In a census, all male citizens declare their ages, and there is at least one male citizen. Each female citizen provides only the information that her age is the average of the ages of all the citizens she knows. Prove that this is enough to determine uniquely the ages of all the female citizens.

Solution

Let a1, a2, . . . , am be the ages of the male citizens (m \geq1). We claim that the age of each female citizen can be expressed in the form c1a1+\cdot \cdot \cdot+cmam for some constants ci \geq0, and we will prove this by induction on the number n of female citizens. The claim is clear if n = 1. Suppose it holds for n and consider the case of n + 1 female citizens. Choose any of them, say A of age x who knows k

citizens (at least one male). By the induction hypothesis, the age of each of the other n females is expressible as c1a1 + \cdot \cdot \cdot + cmam + c0x, where ci \geq0 and c0 + c1 + \cdot \cdot \cdot + cm = 1. Consequently, the sum of ages of the k citizens who know A is kx = b1a1 + \cdot \cdot \cdot + bmam + b0x for some constants bi \geq0 with sum k. But A knows at least one male citizen (who does not contribute to the coefficient of x), so b0 \leqk −1. Hence x = b1a1+\cdot\cdot\cdot+bmam k−b0 , and the claim follows.