Maths Olympiad Prep

Library / /172 of 299

Combinatorics Difficulty 6.6 National Olympiad Prove it Iran

SS and TT are two trees without having a vertex of degree 22. Each edge of them has a positive number named the length of the edge. The distance between two vertices is the sum of the length of the edges of the path between them. We call the vertices with degree 11, leaf. ff is an injective and surjective function from the set of leaves of SS to the set of leaves of TT with this property that for every two leaves uu and vv in SS, the distance between uu and vv in SS is equal to the distance between f(u)f(u) and f(v)f(v) in TT. Prove that there exists an injective and surjective function gg from the set of vertices of SS to the set of vertices of TT such that for every two vertices uu and vv in SS, the distance between uu and vv in SS, is equal to the distance between g(u)g(u) and g(v)g(v) in TT.

Solution

It is obvious that the total number of the leaves of SS and TT are equal. We solve the problem using induction. The base case for 22 leaves is trivial because there is no vertex of degree 22. Now suppose that S,TS, T have kk leaves. Let

S=S{u},T=T{f(u)} S' = S - \{u\}, \quad T' = T - \{f(u)\}

in which uu is a leaf. It means that we omitted leaf uu from SS, and leaf f(u)f(u) from TT. Assume the induction hypothesis holds for S,TS', T', so there is a correspondence between their vertices, like gg. Now let uu' be the neighbor of uu in SS', and uu'' be the neighbor of f(u)f(u) in TT'. It is enough that we prove that u=g(u)u'' = g(u') and the length of the edge uuuu' is equal to the length of the edge f(u)uf(u)u''.

First note that if v,wv, w be two leaves in SS and the path between v,uv, u, intersects the path between v,wv, w for the first time in vertex kk, then we have: (let l(uv)l(uv) denote the length of the path between uu and vv)
l(uk)=l(uv)+l(uw)l(vw)2 l(uk) = \frac{l(uv) + l(uw) - l(vw)}{2}
And since SS doesn't have a 22-degree vertex:
length of edge uu=minv,wSleaves{l(uv)+l(uw)l(vw)2}=minf(v),f(w)Tleaves{l(f(u)f(v))+l(f(u)f(w))l(f(v)f(w))2}=length of the edge f(u)u \begin{align*} \text{length of edge } uu' &= \min_{v,w \in S_{\text{leaves}}} \left\{ \frac{l(uv) + l(uw) - l(vw)}{2} \right\} \\ &= \min_{f(v), f(w) \in T_{\text{leaves}}} \left\{ \frac{l(f(u)f(v)) + l(f(u)f(w)) - l(f(v)f(w))}{2} \right\} \\ &= \text{length of the edge } f(u)u'' \end{align*}
Now do the same for TT. Thus, because these two values for a pair v,wv, w and its correspondence f(v),f(w)f(v), f(w), minimizes, so u=g(u)u'' = g(u') and the length of the edge uuuu' is equal to the length of the edge f(u)uf(u)u'', hence the induction and proof are complete.

Want a route through all this instead of 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 reproduced verbatim; metadata (topic, difficulty) added by this project.