MathDB

6

Part of 2016 Romanian Master of Mathematics

Problems(1)

as if 2D combo geo wasn't hard enough already

Source: 2016 RMM #6

2/28/2016
A set of nn points in Euclidean 3-dimensional space, no four of which are coplanar, is partitioned into two subsets A\mathcal{A} and B\mathcal{B}. An AB\mathcal{AB}-tree is a configuration of n−1n-1 segments, each of which has an endpoint in A\mathcal{A} and an endpoint in B\mathcal{B}, and such that no segments form a closed polyline. An AB\mathcal{AB}-tree is transformed into another as follows: choose three distinct segments A1B1A_1B_1, B1A2B_1A_2, and A2B2A_2B_2 in the AB\mathcal{AB}-tree such that A1A_1 is in A\mathcal{A} and ∣A1B1∣+∣A2B2∣>∣A1B2∣+∣A2B1∣|A_1B_1|+|A_2B_2|>|A_1B_2|+|A_2B_1|, and remove the segment A1B1A_1B_1 to replace it by the segment A1B2A_1B_2. Given any AB\mathcal{AB}-tree, prove that every sequence of successive transformations comes to an end (no further transformation is possible) after finitely many steps.
combinatoricscombinatorial geometrygeometryRMMRMM 2016