# Using your Head is Permitted

## August 2015 solution

The mention of Erdős in the riddle, and specifically the reminder of his
connection to last month's riddle, was actually a hint. I was referring to his
result, detailed in the July solution, that any integer, *y*, can be
represented as the sum of integers of the form
2^{a}3^{b} such that no two divide each other.
The name given to such a representation is a *d*-representation.
Erdős initially posed this problem as a challenge to his friends, but, to
use his own words, overestimated the difficulty of the problem. It was solved
almost immediately. For completeness, let us recap the proof:

Let *y* be the smallest integer not representable in this way. If
*y* is even,
*y*=2*k*, multiply by 2 each number used in the representation of
*k*. If *y* is odd, it must be in the range
3^{i}≤*y*<3^{i+1} for some *i*.
By subtracting 3^{i} we either solve the problem or reduce it
to an even number such that its half is less than 3^{i}, so
proceeding as in the case where *y* is even solves the problem.

Now, consider our generalised "3^{x}n+1" problem. We claim that
there is always a path from any *n* to 1. Consider what such a path looks
like. I'll give, again, the example of 7, using the standard Collatz function:

(((((7*3+1)/2*3+1)/2*3+1)/2^{2}*3+1)/2^{3}*3+1)/2^{4}=1
Multiplying both sides by a high-enough power of 2 we can always make this into
an integer equation. After opening the parentheses, it looks like this:

7*3^{5}+3^{4}+2*3^{3}+2^{2}*3^{2}+2^{4}*3+2^{7}=2^{11}
Under the generalised conditions we are interested in, the equation looks much
the same, except for the fact that powers of three can drop rapidly from one
summand to the next, whereas here they reduce by one each time. Specifically,
we are trying to find, for a given *n*, an *a* and a *b* such
that the difference 2^{b}-*n**3^{a} has a
*d*-representation where the highest power of 3 used is less than *a*.

Note, however, that for any *n* there will be some *a* for which
there is a power of 2 in the range
(*n**3^{a}, (*n*+1)*3^{a}).
(This is clear when considering the problem in log-scale, noting that
log_{2}3 is irrational.) Let that power of 2 be 2^{b}.

Because any integer has a *d*-representation, this will also be true
specifically for 2^{b}-*n**3^{a}. Because
the difference is less than 3^{a}, we know that any power of 3
used will necessarily be smaller than *a*.

Q.E.D.

Back to riddle

Back to main page