Using your Head is Permitted

August 2015 riddle

UPDATE (1 September): As there were no correct solutions to the August riddle as of yet, the riddle will run a second month in parallel to a new September riddle.

However, I will give the following hint: consider the solution to the previous month's riddle.

Let me introduce you to my greatest nemesis.

Its name is the Collatz conjecture, though it is known by many other names, the most popular of which perhaps being the "3n+1" problem. It is a problem that has wasted many mathematician man-years, and continues to waste at least 2-3 days of my time whenever anybody mentions it, because I find it impossible to do anything other than to think about it.

Paul Erdős, whom we mentioned last month, reportedly said about it that "Mathematics may not be ready for such problems," and it remains today as open as it ever was, almost a century after it was first posed.

Describing the conjecture is very easy: take any natural, n. If it is even, divide by 2. If it is odd, multiply by 3 and add 1. You now have a new natural. Repeat the process, continuing to repeat as many times as necessary. The conjecture is that after enough repetitions, one always eventually reaches n=1.

As an example, take n=7. Because it is odd, we multiply it by 3 and add 1, reaching 22. Because 22 is even, we divide by 2 to reach 11. Repeating this further we get 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Done.

Here is this month's problem:

Prove that the conjecture is true if we relax it by allowing one to multiply by 3x instead of 3 when n is odd, where x is an integer greater than zero that one can choose freely, and can be different each time a multiplication is needed throughout the process.

List of solvers:

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page