PUMaC 2011 · 代数（B 组） · 第 6 题

PUMaC 2011 — Algebra (Division B) — Problem 6

[ 6 ] 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?

解析

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 . 5 10