2
$\begingroup$

Consider this example of constructing two numbers by concatenating the numbers of the set $S = \{0,1,2,\ldots,9\}$ without repetition in such a way that the product of the two numbers formed is maximum. Here concatenation means that we can place a number to the left or to the right of another number from the set $S$ but using numbers as a power etc is not allowed. E.g. the numbers $12345$ or $98607$ is a concatenations but $123^{45}$ is not a concatenation under our definition.

In the above example, the largest product is given by two pairs $(96420,87531)$ and $(9642,875310)$. We shall call these two pairs as the maximal pairs. Now let us generalise this simplistic example.

Let $d_1 \le d_2 \le \ldots \le d_n$ be $n$ non-negative integers, not necessarily distinct. How do we form $k$ numbers, $2 \le k < n$ such that their product is maximum i.e. how to form the maximal $k$-tuples.

My heuristic progress: The $k$-tuple is given by $$ a_i = d_{n-k+i}d_{n-2k+i} \cdots d_{n-rk+i} $$

where $1 \le i \le k$ and $r$ is the largest integer such that $n-rk+i \ge 1$.

$\endgroup$
1
$\begingroup$

With your example, we construct the numbers as follows:

First we pick the two largest numbers of the set,namely $9$ and $8$

Then we pick the next two largest, say $7$,and $6$ and compare $$97\times 86$$ with $$96\times 87$$ and pick the pair with the larger product which is $$96\times 87$$

Continue and you get $964\times 875$, $9642\times 8753$, $$96420\times 87531=8439739020$$

Same process works for the general case.

$\endgroup$
  • $\begingroup$ Thats how it found out the two pairs. But this is a hit and trial approach. What I am looking for is a closed form formula like the one I have mentioned. $\endgroup$ – Nilos Nov 10 '18 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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