Using your Head is Permitted
November 2008 solution
One possible candidate for M(x) is 3log3(x),
corrected for x=1 to M(1)=1.
The three conditions on M() can be proven as follows:
For any x, M(x)≤N(x)
In the optimal representation for any x>1,
the top-level operation is either
addition or multiplication, representing x as either y+z
or yz, where, in both cases, both y and z are
smaller than x. It suffices, therefore, to show by induction that if
M(y)≤N(y) and
M(z)≤N(z) then also
M(x)≤N(x). For multiplication, this is obviously
true because N(x)=N(y)+N(z) and
M(x)=M(y)+M(z).
For addition, N(x)=N(y)+N(z),
whereas M(x) = 3log3(x) =
3log3(y+z). Supposing, however, that
y+z≤yz then
M(x)≤3log3(yz) =
M(y)+M(z)≤N(x).
This inequality is true whenever both y and z are greater than
1. Having checked that the inequality is satisfied for the base case of
x=1, as well as for x=1+1 and x=1+1+1, the rest of the
proof lies in the fact that for x≥3,
3log3(x+1)<3log3(x)+1.
For any x, N(x)<1.6M(x)
Let us describe x by use of its binary notation. For example:
23=10111BIN=((2*2+1)*2+1)*2+1=(((1+1)*(1+1)+1)*(1+1)+1)*(1+1)+1, so
N(23)≤11. More generally, every bit of x costs two 1's to
represent if the bit is zero and three 1's to represent if the bit is one
(except for the most significant bit). This means that
N(x)≤3log2(x)<1.6M(x) for
all x>1. The special case x=1 is handled by our explicit
correction to M(1).
There exists an infinite number of values, x, for which
M(x)=N(x)
Consider all x of the form 3n for natural
n. These can clearly be represented as (1+1+1)*(1+1+1)*(1+1+1)*...
reaching the optimum.
Also, in case you were wondering: 1+6+7+9=23.
Back to riddle
Back to main page