3
$\begingroup$

Let $n>0$ be an integer. Consider all partitions of $n$, i.e. all possible ways of writing $n$ as a finite sum of positive integers, $$n=n_1+n_2+\cdots+n_k.$$ What partition maximizes the product $n_1n_2\cdots n_k$?

Examples:

  • $2=2$
  • $3=3$
  • $4=2+2$
  • $5=3+2$
  • $6=3+3$
  • $7=3+2+2$
  • $8=3+3+2$
  • $9=3+3+3$
  • $10=3+2+2$
  • $20=3+3+3+3+3+3+2$
  • $30=3+3+3+3+3+3+3+3+3+3$
  • $40=3+3+3+3+3+3+3+3+3+3+3+3+2+2$
  • $50=3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+2$

Conjecture: It is the partition that has the maximum number of $3$'s among those consisting only of $3$'s and $2$'s.

$\endgroup$

marked as duplicate by Brian M. Scott, Claude Leibovici, user91500, user1551, Henrik Jul 17 '16 at 11:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $2$ and $3$ are surprisingly similar to $e$ $\endgroup$ – cronos2 Jul 15 '16 at 8:57
  • $\begingroup$ Because $2\cdot(k-2)>k$ when $k>4$ and $3\cdot3>2\cdot2\cdot2$ it always pays to split $k>4$ as $2+(k-2)$ and prefer $3+3$ over $2+2+2$. A simple argument based on this leads to your result. It has been done on our site before. Did you search? $\endgroup$ – Jyrki Lahtonen Jul 15 '16 at 9:02
  • 5
    $\begingroup$ See here or here or here $\endgroup$ – Jyrki Lahtonen Jul 15 '16 at 9:03
  • $\begingroup$ No matter, good job figuring this out on your own! $\endgroup$ – Jyrki Lahtonen Jul 15 '16 at 9:15
1
$\begingroup$

Here is a rough idea. The problem can be divided into two parts. Firstly, given a $n$, for a fixed number of partitions $k$, it is not hard to find that all of the partitions should be equal. However, since we are dealing with integers, we might need to find the nearest integers.

Having the first part, we would like to know for which $k$ we get the optimum solution. we want to optimize the logarithm of the product instead. Please note that I have simplified things by letting numbers to be real.

$ln(n)=\sum_{i=1}^{k}ln(x_i)$

considering all $x_i$ are the same, we get

$ln(n)=k*ln(\frac{n}{k})$

taking the derivative of the function with respect to $k$ and putting it equal to zero, we get

$ln(\frac{n}{k})=1$

Therefore

$k\simeq\frac{n}{e}$

finally

$\frac{n}{k}=e\simeq2.7$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.