Problem:
When a positive integer is fed into a machine, the output is a number calculated according to the rule shown below:
For example, starting with an input of , the machine will output . Then if the output is repeatedly inserted into the machine five more times, the final output is .
When the same -step process is applied to a different starting value of , the final output is . What is the sum of all such integers
Answer Choices:
A.
B.
C.
D.
E.
Solution:
To see which numbers we can make by inverting it, let's make an inverting machine. This would take and yield either if is even (which it always is) or if is an odd integer. Note that is an integer only if . Also, if is even, then is odd. That would mean would be odd. Therefore, our inverter machine yields and also if and is even.
Now, we must see what the inverting machine can yield after moves:
- From , we can only get .
- From , we can only get .
- From , we can get and .
- From , we can get only ; from , we can only get .
- From , we can get only ; from , we can get and .
- From , we can get and ; from , we can get ; from , we can get .
Move can yield , , , and , and their sum is . Thus, the correct answer is .
Answer: .
The problems on this page are the property of the MAA's American Mathematics Competitions