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 \displaystyle \prod_{j=1}^{k} x_j, for some positive integer k, where \displaystyle \sum_{j=1}^{k} x_j = 100 and x_js are all positive integers.

My (corrected) guess (Ansatz). The solution to your problem seems to be satisfied by k=33+2=34 variables, such as x_{1}=x_{2}=\ldots =x_{32}=3,x_{33},x_{34}=2.
 
Thus x_{1}x_{2}\cdots x_{32}x_{33}x_{34}=3^{32}2^2. If this is correct

 x_{1}=x_{2}=\ldots =x_{32}=\left\lceil e\right\rceil .

For x_{1}=x_{2}=\ldots =x_{49}=x_{50}=\left\lfloor e\right\rfloor =2, the product is only 2^{50}<3^{33}.

I noticed that the function x\longmapsto\dfrac{x}{e^{\ln x-1}}=e and 2<e<3. I have not yet a rigorous argument.

Solution by Neil Dickson. The maximum is 3^{32}2^2.

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, 3(n-3)>n, 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 2^3<3^2, 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 K_3‘s and 2 K_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

Sobre Américo Tavares

eng. electrotécnico reformado / retired electrical engineer
Esta entrada foi publicada em Matemática, Math, Number Theory, Problem, Problemas, Teoria dos Números com as etiquetas , , , . ligação permanente.

Deixar uma resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

WordPress.com Logo

Está a comentar usando a sua conta WordPress.com Log Out / Modificar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Log Out / Modificar )

Facebook photo

Está a comentar usando a sua conta Facebook Log Out / Modificar )

Google+ photo

Está a comentar usando a sua conta Google+ Log Out / Modificar )

Connecting to %s