Splitting Up a Number

Question

Given some $n\in N$, how can I partition $n$ into other natural numbers which sum n such that the total product of all elements in the partition is maxmimised?

Solution

Consider some valid partition $P$ of $n$:

$$P=(a_1,a_2,...)$$

And let:

$$f(P)=a_1\ast a_2\ast ...$$

Note that all natural numbers > 1 can be written as a sum of 2s and 3s exclusively, ie

$$a_1=2+2+...+3+3+...$$

What we will now show is that taking all the elements in the partition and breaking them up into 2s and 3s, will give a better partition.

Lemma 1: The product of some sequence of 2s and 3s is always greater or equal to the corresponding sum with equality holding iff the sequence is (2, 2), (2,) or (3,). Proof:

$$2\ast 2=2+2$$ $$3\ast 2>3+2$$ $$3\ast 3>3+3$$

Hence if:

$$\text{Double subscripts: use braces to clarify}$$

Then

$$\text{Double subscripts: use braces to clarify}$$

With equality holding iff $a_1<5$. From this it is clear that the optimal partition will consist of some sequence of 2s and 3s. For most numbers however there are many ways to split a number into sums of 2s and 3s. We will now show how to find the optimal partition. Note:

$$3+3=2+2+2$$ $$3\ast 3>2\ast 2\ast 2$$

This implies that there will be no more than two lots of 2s in the optimal partition. If $3|n$ then the optimal partition is three lots of $\frac{n}{3}$. If we consider trying to improve upon this partition by breaking up a 3 into a 2 and a 1 , we decrease the product. And if we try to improve upon the partition by combining 3s we decrease the product by lemma 1. Therefore the partition is optimal in this case. Now consider:

$$1)n\equiv 1mod3\Rightarrow \mathrm{\exists }k\in Ns.tn=3k+1$$ $$2)n\equiv 2mod3\Rightarrow \mathrm{\exists }k\in Ns.tn=3k+2$$

For 1) we can choose from (1, 3 k times) or (2, 2, 3 (k - 1)) times. Given 2 * 2 > 3 * 1 we can identify the latter case as optimal.

For 2) the only option containing no ones or less than three 2s is (2, 3 k times).

Question Extension

What if $n\in R+$ and the elements of the partition can be any positive real?

Extension Solution

Unlike the previous solution we will use some calculus. Consider:

$$(x,x),(x-a,x+a)$$

Where $x,a\in R^{+},x>a$.

Note the two tuples have the same sum but:

$$x^2>x^2-a^2$$

From this it is apparent that all elements of the optimal partition must be the same number. Let this number be $k_n$ Consider the function:

$$f(x)=x^{\frac{n}{x}}$$

For some constant $n$. Then $k_n$ is the maximum of this function with the added restriction that $x|n$.

Rewrite $f(x)$:

$$f(x)=e^{\frac{n\ln x}{x}}$$

We find the stationary point by differentiating and equating to 0:

$$(\frac{n}{x^2}-\frac{n\ln x}{x^2})e^{\frac{n\ln x}{x}}=0$$

$f(x)\ne 0\mathrm{\forall }x\in R$ hence we have:

$$(\frac{n}{x^2}-\frac{n\ln x}{x^2})=0$$

$$\Rightarrow lnx=1$$

$$\Rightarrow x=e$$

Hence the sole stationary point of the function occurs at $x=e$ and is independent of $n$. If we note that:

$$\underset{x\to 0+}{lim}f(x)=\underset{x\to \mathrm{\infty }}{lim}f(x)=0$$

Then we can identify the stationary point as a global maximum of the function, and reason that our desired k_n lies somewhere around $e$.