17th Mexico 2003 Problem B3 Given a positive integer n, an allowed move is to form 2n+1 or 3n+2. The set S n is the set of all numbers that can be obtained by a sequence of allowed moves starting with n. For example, we can form 5 → 11 → 35 so 5, 11 and 35 belong to S 5 . We call m and n compatible if S m ∩ S n is non-empty. Which members of {1, 2, 3, ... , 2002} are compatible with 2003?
166, 333, 500, 667, 1001, 1335, 1502 Solution Let D be the operation a → 2a+1, and T the operation a → 3a+2. Note first that D and T commute, and they are obviously injective. Now we claim that if a = D m b = T n c, then we can find d such that b = T n d and c = D m d. We use induction on m. Consider first m = 1. Note that k is odd iff Tk is odd. Now a = Db, so a is odd. But a = T n c, so c is odd. Hence we can find d such that c = Dd. Then Db = DT n d, so b = T n d, and the result is true for m = 1. Suppose it is true for m and that a = D m+1 b = T n c. Then T n c is odd, so c is odd, so c = De. Hence D m b = T n e. So, by induction, we can find d such that b = T n d, e = D m d. Then c = D m+1 d, b = T n d, as required. So the result is true for m+1 and hence for all m. It follows that if a = D r T s b = D m T n c, then b and c can both be obtained from some d. (wlog r ≥ m, so D r- m T s b = T n c. If s ≥ n, then we are home since c = D r-m T s-n b, if not then D r-m b = T n-s c and we use the result just proved.) Thus if we take m to be the smallest number which can lead to n, then we have n = D r T s m for some r,s and so the numbers which can lead to n are just D a T b m for 0 ≤ a ≤ r, and 0 ≤ b ≤ s. (For if k leads to n, then we can find d which leads to m and k, but d cannot be smaller than m, so d = m.) Thus if k ∈ S 2003 ∩ S n , then 2003 and n can both be obtained from some d. Working backwards, we find that 2003 = D 2 T 166, where 166 is not odd and not 2 mod 3, so cannot be obtained from anything else. Hence the only numbers that lead to numbers derived from 2003 are those that derive from 166. We get 333 = D 166, 500 = T 166, 667 = D 2 166, 1001 = DT 166, 1335 = D 3 166, 1502 = T 2 166 (the others are all ≥ 2003). 17th Mexican 2003 © John Scholes jscholes@kalva.demon.co.uk 1 March 2004 Last corrected/updated 2 Mar 04