PUMaC 2011 · 代数（A 组） · 第 3 题

PUMaC 2011 — Algebra (Division A) — Problem 3

[ 4 ] Shirley has a magical machine. If she inputs a positive even integer n , the machine will output n/ 2, but if she inputs a positive odd integer m , the machine will output m + 3. The machine keeps going by automatically using its output as a new input, stopping immediately before it obtains a number already processed. Shirley wants to create the longest possible output sequence possible with initial input at most 100. What number should she input? 3 2

解析

First, note that the possible end states of the machine are { 4 , 2 , 1 } and { 6 , 3 } , and that the machine will invariably halve itself at most every other operation, since when m is odd then the output m + 3 is even. Therefore, when operating in reverse order, the longest sequence will be the one that halves exactly every other time. Since the ending period { 1 , 2 , 4 } is longer than { 6 , 3 } and obtains smaller values than 6, then { 1 , 2 , 4 } end will result in the longer chain. Operating in reverse order, we can see that { 1 , 2 , 4 , 8 , 5 , 10 , 7 , 14 , 11 , 22 , 19 , 38 , 35 , 70 , 67 } is the longest possible chain, and so the answer is 67 .