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.



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 c1, c2, ... , cm 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 c1a1 + c2a2 + ... + cmam where ai 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 ci = 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 ci with sum 1 such that the number assigned to C is c1a1 + ... + cmam + cm+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 c1a1 + ... + cmam + cm+1x for some non-negative ci with sum 1. If an adjacent point is red then its number is ai for some i. Note that this can also be regarded as a linear combination of aj with non-negative coefficients having sum 1. So kx = b1a1 + ... + bmam + bm+1x, where the bi are non-negative and have sum k. There was at least one red neighbour, so bm+1 < k. Hence we can solve for x to get x = ∑ (bi/(k - bm+1) ai. Note that each of the coefficients (bi/(k - bm+1) is non-negative and that their sum is 1. Now for any other blue point we have that the number is c1a1 + ... + cmam + cm+1x = ∑ (ci + cm+1bi/(k - bm+1) ai. Again each coefficient is non-negative and their sum is 1. So the induction is complete.


Note that we need the conditions ci non-negative and ∑ ci = 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 ai joined to P + sum of numbers of blue points joined to P = (by induction) ∑ ciai + hx. But if h = k, we get stuck at this point.



35th IMO shortlist 1994

© John Scholes
18 Sep 2002