© Friederike Hofmann, MATH+
Author: Christian Hercher (Europa-Universität Flensburg)
Challenge
Elf Collean likes to pass her free time by playing with positive integers. In doing so, she has noticed that whenever she considers an odd positive integer n , its triple is odd again; that is, 3n+1 is divisible by two. Therefore, she invents the following two rules to calculate a positive integer from a given positive integer n :
- If the given number n is even, she divides it by two and gets another positive integer, namely \tfrac{n}{2} . Since the result is smaller then the starting number, Collean calls this operation a decreasing step.
- If the given number n is odd, she first multiplies it by three, then adds one, and finally divides everything by two. The result \tfrac{3n+1}{2} is, as we have seen above, another positive integer. Here, the result is bigger than the starting number. Hence, Collean calls this operation an increasing step.
In this way, starting with any positive integer, Collean produces more and more positive integers. For example, if she starts with the number 11, the next number she gets is 17, then 26, 13, 20, 10, 5, 8, 4, 2, and finally 1. Then, something peculiar happens: after 1, according to her rules, she gets 2 again, then 1 again, then 2 again, and so on.
Collean wonders if this is always the case: no matter what number you start with, do you always eventually end up with this loop from 1 to 2 and back? All the examples she calculates point in this direction. Of course, this is far from being a proof …
However, as a mathematically interested elf, she is not satisfied with stating such a conjecture. Although its proof is probably still beyond her reach, she is perhaps able to make some related observations and then prove or disprove them. Thus, she postulates the following claims concerning her two rules:
Claim A: If a positive integer n can be written as a\cdot 2^k-1 (where a and k are positive integers), then starting with n one can perform at least k increasing steps in a row.
Claim B: There is a positive integer n which is followed only by increasing steps.
Claim C: Let n be an odd positive integer that is first followed at least one increasing and then two decreasing steps in a row, resulting in a number m . Then, this number m could have also been obtained by starting with \tfrac{n-1}{2} .
Claim D: If there exist starting numbers that will never reach 1, then the remainder of the smallest of these numbers when divided by 6 is 1 or 3.
Which of the above claims are correct?
Possible answers:
- All four claims are correct.
- A, B, and C are correct, D is wrong.
- A, B, and D are correct, C is wrong.
- A, C, and D are correct, B is wrong.
- B, C, and D are correct, A is wrong.
- A and B are correct, C and D are wrong.
- B and C are correct, A and D are wrong.
- A is correct, B, C, and D are wrong.
- D is correct, A, B, and C wrong.
- All four claims are wrong.
Sunday Bonus + Error: For this challenge, you will get a time bonus of 48 hours.