IMO shortlist 1994/C2 solution

35th IMO 1994 shortlist

Problem C2

A finite graph is connected. A positive real number is assigned to each point. Each point is colored red or blue and at least one point is colored red. Show that, given a knowledge of (1) the points and edges of the graph, (2) the number assigned to each red point, and (3) for each blue point the average of the numbers for the points joined to it, one can find the number assigned to each point.

Solution

We use induction on the number n of blue points. Suppose there are m red points. The induction hypothesis is that for each blue point C there are non-negative real numbers c₁, c₂, ... , c_m with sum 1 which depend only on the graph (and not on the numbers assigned to the points) such that the number assigned to the point C is c₁a₁ + c₂a₂ + ... + c_ma_m where a_i are the numbers assigned to the red points. For n = 0 there is nothing to prove. For n = 1, suppose the blue point P is adjacent to k red points. Then we can take c_i = 1/k for points adjacent to P and 0 for points not adjacent to P.

So now suppose the result holds for n. Consider a graph with m red points and n+1 blue points. Since the graph is connected we can find a blue point P which is joined to at least one red point. Suppose P has the number x. If we change the color of P to red, then for each remaining blue point C we can find non-negative numbers c_i with sum 1 such that the number assigned to C is c₁a₁ + ... + c_ma_m + c_m+1x. Suppose there are k points adjacent to P. Then kx = sum of numbers of adjacent points. If an adjacent point is blue, then its number is c₁a₁ + ... + c_ma_m + c_m+1x for some non-negative c_i with sum 1. If an adjacent point is red then its number is a_i for some i. Note that this can also be regarded as a linear combination of a_j with non-negative coefficients having sum 1. So kx = b₁a₁ + ... + b_ma_m + b_m+1x, where the b_i are non-negative and have sum k. There was at least one red neighbour, so b_m+1 < k. Hence we can solve for x to get x = ∑ (b_i/(k - b_m+1) a_i. Note that each of the coefficients (b_i/(k - b_m+1) is non-negative and that their sum is 1. Now for any other blue point we have that the number is c₁a₁ + ... + c_ma_m + c_m+1x = ∑ (c_i + c_m+1b_i/(k - b_m+1) a_i. Again each coefficient is non-negative and their sum is 1. So the induction is complete.

Comment

Note that we need the conditions c_i non-negative and ∑ c_i = 1 are needed to make the induction work. If we had the simpler hypothesis that the number for each blue point is a linear combination of the red numbers, then we could still change one blue point P with number x to red. But then we would have kx = sum of a_i joined to P + sum of numbers of blue points joined to P = (by induction) ∑ c_ia_i + hx. But if h = k, we get stuck at this point.

35th IMO shortlist 1994