2016 Eighth Romanian Master of Mathematics

Question

A set of n points in Euclidean 3-dimensional space, no four of which are coplanar, is partitioned into two subsets A and B. An AB-tree is a configuration of n-1 segments, each of which has an endpoint in A and the other in B, and such that no segments form a closed polyline. An AB-tree is transformed into another as follows: choose three distinct segments A_1B_1, B_1A_2 and A_2B_2 in the AB-tree such that A_1 is in A and A_1B_1 + A_2B_2 > A_1B_2 + A_2B_1, and remove the segment A_1B_1 to replace it by the segment A_1B_2. Given any AB-tree, prove that every sequence of successive transformations comes to an end (no further transformation is possible) after finitely many steps. Russia

Accepted Answer

The configurations of segments under consideration are all bipartite geometric trees on the points

n

whose vertex-parts are

A

and

B

, and transforming one into another preserves the degree of any vertex in

A

, but not necessarily that of a vertex in

B

.

The idea is to devise a strict semi-invariant of the process, i.e., assign each

A B

-tree a real number strictly decreasing under a transformation. Since the number of trees on the

n

points is finite, the conclusion follows.

f (T^{'}) - f (T) = p_{T^{'}} (A_{1} B_{2}) \cdot A_{1} B_{2} + (p_{T^{'}} (A_{2} B_{1}) - p_{T} (A_{2} B_{1})) \cdot A_{2} B_{1} + (p_{T^{'}} (A_{2} B_{2}) - p_{T} (A_{2} B_{2})) \cdot A_{2} B_{2} - p_{T} (A_{1} B_{1}) \cdot A_{1} B_{1} = p_{T} (A_{1} B_{1}) (A_{1} B_{2} + A_{2} B_{1} - A_{2} B_{2} - A_{1} B_{1}) < 0.