Maximum of the produt of k positive integers, the sum of which is 100. Problem by Vishal Lama and a solution by Neil Dickson

Problem by Vishal Lama. Maximize the value of the expression , for some positive integer , where and s are all positive integers.

My (corrected) guess (Ansatz). The solution to your problem seems to be satisfied by variables, such as .
 
Thus . If this is correct

 .

For , the product is only .

I noticed that the function and . I have not yet a rigorous argument.

Solution by Neil Dickson. The maximum is .

Rough proof:
It’s definitely the case that no factor can be 1 in the maximum, since the 1 could just be added to any other factor to increase the product.  It’s also true that for any integer 5 or greater, , so it could be split into 3 and n-3 to give a larger product and equal sum.  Any 4 can be split into 2 and 2 giving the same sum and product.  Therefore only 2 and 3 are needed to represent the maximum.  Because , maximizing the number of 3′s should give the maximum product.  The maximum number of 3′s you can fit into 100 with an even remainder is 32, leaving 4, which is two 2′s.

This turns out to also be equivalent to asking “What’s the maximum number of maximal independent sets that can occur in a graph of 100 nodes?”  The graph that satisfies this condition is just 32 ‘s and 2 ‘s (it’s 34 disconnected components, but it’s still a graph).  I’ve been using this lately to construct very bad cases to test out a couple of quantum algorithms I’ve been working on.

About these ads