Olympiad Maths Prep

Library / /16 of 29

Combinatorics Difficulty 6.4 National olympiad Prove it Iran

A weighted complete graph with distinct positive weights is given such that every triangle is degenerate, i.e., the weight of one of the edges is equal to the sum of the two others. Prove that one can assign values to the vertices of this graph such that the weight of each edge is equal to the difference between the values assigned to its endpoints.

Solution

Let dX,Yd_{X,Y} be the weight assigned to the edge XYXY of the graph. Clearly, in each triangle the maximum weight of an edge is the sum of the two others. Let dA,Bd_{A,B} be the maximum weight among all weights assigned to the edges. Now assign 00 to vertex AA and dA,Xd_{A,X} to any other vertex XX. Obviously, this labeling works for all edges including AA. We claim that it works for all other edges.

Assume to the contrary that the labeling doesn't work for an edge XYXY of the graph. So dX,Yd_{X,Y} is not the difference between dA,Xd_{A,X} and dA,Yd_{A,Y}, which means dX,Y=dA,X+dA,Yd_{X,Y} = d_{A,X} + d_{A,Y}. Note that BB cannot be any of X,YX, Y. Since dA,Bd_{A,B} is the maximum edge number, we have dB,X=dA,BdA,Xd_{B,X} = d_{A,B} - d_{A,X} and dB,Y=dA,BdA,Yd_{B,Y} = d_{A,B} - d_{A,Y}. Now consider triangle BXYBXY. If dX,Yd_{X,Y} is the maximum weight of an edge in this triangle, we have
dX,Y=dB,Y+dB,X    [t]dX,Y=dA,BdA,Y+dA,BdA,X=2dX,Y=2dA,B. d_{X,Y} = d_{B,Y} + d_{B,X} \implies \begin{aligned}[t] d_{X,Y} &= d_{A,B} - d_{A,Y} + d_{A,B} - d_{A,X} \\ &= 2d_{X,Y} = 2d_{A,B}. \end{aligned}
Which is impossible since the weights are distinct. So the maximum edge weight in triangle BXYBXY is not dX,Yd_{X,Y}. Without loss of generality, assume that dB,Yd_{B,Y} is the maximum one. So we have
dB,Y=dB,X+dX,Y    [t]dA,BdA,Y=dA,BdA,X+dA,X+dA,Y=dA,Y=0. d_{B,Y} = d_{B,X} + d_{X,Y} \implies \begin{aligned}[t] d_{A,B} - d_{A,Y} &= d_{A,B} - d_{A,X} + d_{A,X} + d_{A,Y} \\ &= d_{A,Y} = 0. \end{aligned}
Which is again a contradiction. This completes the proof. ■

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.