Problem Solving, Part IV

In my last post, I was attempting to prove that the statement found here was true, by assuming it was false and attempting to arrive at a contradiction.

For now, I will attempt to prove that it is impossible for a cycle of size n to exist.

Clearly, a 1-cycle cannot exist. For all natural numbers >0, n/2 != n and 3n  + 1 != n. So f(n) != n, so a 1-cycle cannot exist.

2-cycle: There are 2 cases:

n is even: Then f(n) = n/2. Again, there are two cases to consider:

     f(n) is even: Then f(f(n)) = n/4. Since n/4 != n.  f(f(n)) != n.

     f(n) is odd:  Then f(f(n)) = 3(n/2) + 1 = 3/2n +1 != n.  So f(f(n)) != n.

n is odd: Then f(n) = 3n+1  and is even.

                 So f(f(n)) = (3n+1)/2 = 3/2n + 1/2 != n.  So f(f(n)) != n.

I could continue for 3,4,5 ... cycles, but the number of cases would become unmanageable, and I would never prove that a cycle cannot exist. There may be a way to solve this problem inductively, but it is difficult to relate an n-cycle to an (n+1)-cycle.

For now, this problem remains unsolved for me, but I at least gained a better understanding of the problem and why it is still unsolved.

Reflection

After attempting this problem, I decided to look it up and see what others have done with it. It turns out this is a famous unsolved problem from 1937 called the Collatz conjecture. Mathematicians have figured out the following:




 - No cycle of size 68 or less exists that does not contain 1.

 - All numbers up to 5 * 2^ 60  will eventually reach 1.
 - The problem is algorithmically undecidable (similar to the halting problem).

So it seems the approach of analysing cycles is useful. From this page, it seems that many mathematicians believe that this problem is unsolvable with our current mathematics, but they remain confident that soon we will have the tools necessary to solve it.