# Using your Head is Permitted

## November 2008 solution

One possible candidate for *M*(*x*) is 3log_{3}(*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 *y**z*, 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*) = 3log_{3}(*x*) =
3log_{3}(*y*+*z*). Supposing, however, that
*y*+*z*≤*y**z* then
*M*(*x*)≤3log_{3}(*y**z*) =
*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,
3log_{3}(*x*+1)<3log_{3}(*x*)+1.

### For any *x*, *N*(*x*)<1.6*M*(*x*)

Let us describe *x* by use of its binary notation. For example:
23=10111_{BIN}=((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*)≤3log_{2}(*x*)<1.6*M*(*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 3^{n} 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