Given a triple of positive integers x ≤ y ≤ z, derive a new triple as follows. Replace x and y by 2x and y - x (and reorder), or replace x and z by 2x and z - x (and reorder), or replace y and z by 2y and z - y (and reorder). Show that by finitely many tranformations of this type we can always derive a triple with smallest element zero.
Solution
Fairly easy.
Let the three integers in S be 0 < a ≤ b ≤ c. We show that we can make a finite series of transformations which give a set S' with an element a' satisfying 0 ≤ a' < a. A finite number of applications of such a series must yield a set with zero.
Let [b/a] = bnbn-1 ... b0 in base 2. Let ci = 1 - bi and k = the binary number cncn-1 ... c0. Then since [b/a] ≥ 2n and [b/a] + k = 2n+1 - 1, k < [b/a].
We now carry out n+1 transformations, for i = 0, 1, ... , n. Step i gives 2i+1a, b - (bibi-1...b0) a, c - (cici-1...c0) a. So we always double the first element and we subtract it from the second or third according as bi = 1 or 0. Note that this works because after step n, the second element is b - [b/a] a ≥ 0, and the third element is c - k a ≥ b - k a > b - [b/a] a ≥ 0. After the final step the second element is b - [b/a] a < a, as required.
© John Scholes
jscholes@kalva.demon.co.uk
12 Dec 1998