## 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+zyz 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.