[EventHorizon]

Since the last post of this kind was so wildly popular (I was the only one to post....), I thought I would try another.

"For any positive integer, k, let Sk = {x1, x2, ... , xn} be the set of real numbers for which x1 + x2 + ... + xn = k and P = x1 x2 ... xn is maximised.

For example, when k = 10, the set {2, 3, 5} would give P = 30 and the set {2.2, 2.4, 2.5, 2.9} would give P = 38.25. In fact, S10 = {2.5, 2.5, 2.5, 2.5}, for which P = 39.0625.

Prove that P is maximised when all the elements of S are equal in value and rational."

Oooh....the British spelling of maximized....this must be a good problem....right?

And follow-up questions of my own design....

For a given k, what would n be? For this, assume you can have a real number for n. (The actual n would be either the ceiling or floor of the equation for n.)

Given your equation for n....would that make each element in the set still rational?

What is each element in the set? Are you surprised by this answer?

Edited April 2, 2008 by Martini

[EventHorizon]

You don't need to come up with a proof to be able to answer the follow-up questions. Just in case proofs scare you.

[EventHorizon]

One more follow-up question

If n could be a real number....what is the maximum product possible for a given k?

It follows easily from the other follow-up questions...

[bonanova]

Question 1: Prove that P is maximised when all the elements of S are equal in value and rational.

We have a set S_k of n terms whose sum is k and whose product P=Prod x_i is maximal.

Prove that the terms of S are equal and rational.

P is extremal when dP/dx_i = 0 for every i.

P is maximal when the second derivate is negative.

Here's a quick demonstration P is maximal, not minimal.

x+y=14

xy is extremal when x=y=7: xy=49

xy is maximal [not minimal] as seen by 6x8 = 48 and 48<49.

Here's a proof for n=2.

Suppose x + y = k

Let P = xy

Need a shorthand notation for partial derivative:

Let Partial derivative of F with respect to x be noted as pF/px.

[1] dP/dx = pP/px + pP/py x dy/dx = 0

[2] dp/dy = pP/py + pP/px x dx/dy = 0

since x + k = k, a constant, dy/dx = dx/dy = -1.

[1] and [2] thus become

[3] dP/dx = pP/px - pP/py = 0

[4] dP/dy = pP/py - pP/px = 0

both of which lead to pP/px = pP/py

since P=xy, pP/px = P/x; pP/py = P/y.

Thus, x=y.

This has a logical if cumbersome extension to n terms.

Thus x_i = k/n for all i.

Sunce k and n are integers, x_i are rational.

[Guest]

It kind of helps me to think of it in a sense of geometry. This simplifies the problem immensely, and is reminiscent of 2nd grade math problems.

Imagine you have a rectangle shape with a perimeter (surface area for 3 terms), and want to maximize the area (volume). The maximum will result from a square or cube shape, so when all the sides are the same, the area/volume will be the greatest.

I believe that a way to figure out n (not verified yet) is to take the larges square smaller than k. This is the amount of terms you should have, and they all should equal each other to maximise product. My thoughts on it so far...

EDIT

okay, after some testing, I have completely shot down my theory on figuring out n. So now, I'm trying to find another method...

Edited April 3, 2008 by Noct

[bonanova]

I calculated a bunch of numbers and found the product was maximized

when k was partitioned into rational numbers closest to the number e = 2.7182818284590452353602874713527...

That is, P = (k/n)ⁿ was maximized when k/n was closest to e, or more simply, when n was the integer closest to k/e.

The approximate product would thus be eⁿ.

Equivalently, ln[P] is approximately n.

Here are calculated values of k, n, k/n [which is close to e] and ln[P] for the n that maximizes (k/n)ⁿ for each k.

. 1 1 1.00000 .00
. 2 1 2.00000 .69
. 3 1 3.00000 1.10
. 4 2 2.00000 1.39
. 5 2 2.50000 1.83
. 6 2 3.00000 2.20
. 7 3 2.33333 2.54
. 8 3 2.66667 2.94
. 9 3 3.00000 3.30
. 10 4 2.50000 3.67
. 20 7 2.85714 7.35
. 30 11 2.72727 11.04
. 40 15 2.66667 14.71
. 50 18 2.77778 18.39
. 60 22 2.72727 22.07
. 70 26 2.69231 25.75
. 80 29 2.75862 29.43
. 90 33 2.72727 33.11
. 100 37 2.70270 36.79
. 200 74 2.70270 73.57
. 300 110 2.72727 110.36
. 400 147 2.72109 147.15
. 500 184 2.71739 183.94
. 600 221 2.71493 220.73
. 700 258 2.71318 257.52
. 800 294 2.72109 294.30
. 900 331 2.71903 331.09
. 1000 368 2.71739 367.88

.	k	n  k/n		 ln[P] <- should be about equal to n.

[bonanova]

For an n-partition S = {x_i} of k -- that is Sum{i=1,n}[x_i] = k, the product P is maximized with respect to the elements x_i when x_i = k/n.

It appears from calculations that P is maximized with respect to n when n is the integer that is closest to k/e.

Prove that conjecture.

P = (k/n)ⁿ. Maximize P with respect to n.

P is maximal when dP/dn = 0. Take the logarithm of the above equation.

ln[P] = n ln[k/n] = n(ln[k] - ln[n]) and differentiate.

(1/P)dP/dn = (ln[k] - ln[n]) + n(0 - 1/n)

dP/dn = P(ln[k] - ln[n] - 1) = 0 at extrema. Since P is nonzero, divide by P:

(ln[k] - ln[n] - 1) = 0

ln[k] - ln[n] = 1

ln[k/n] = 1

k/n = e , or, n = k/e.

Answers to specific questions:

What would n be?

k/e

Would that make each element rational?

No

What is each element in the set?

e.

Are you surprised by that answer?

It's quite surprising.

If n could be a real number what is the maximum product for a given k?

P_max = e^k/e

[EventHorizon]

For an n-partition S = {x_i} of k -- that is Sum{i=1,n}[x_i] = k, the product P is maximized with respect to the elements x_i when x_i = k/n.

It appears from calculations that P is maximized with respect to n when n is the integer that is closest to k/e.

Prove that conjecture.

P = (k/n)ⁿ. Maximize P with respect to n.

P is maximal when dP/dn = 0. Take the logarithm of the above equation.

ln[P] = n ln[k/n] = n(ln[k] - ln[n]) and differentiate.

(1/P)dP/dn = (ln[k] - ln[n]) + n(0 - 1/n)

dP/dn = P(ln[k] - ln[n] - 1) = 0 at extrema. Since P is nonzero, divide by P:

(ln[k] - ln[n] - 1) = 0

ln[k] - ln[n] = 1

ln[k/n] = 1

k/n = e , or, n = k/e.

Answers to specific questions:

What would n be?

k/e

Would that make each element rational?

No

What is each element in the set?

e.

Are you surprised by that answer?

It's quite surprising.

If n could be a real number what is the maximum product for a given k?

P_max = e^k/e

yup, good job.

I do want to mention that I got the problem from another website (why the problem is in quotes) and I said I did, but the name of the site was removed...

As for the original problem, I thought I would give my proof for it...

P = abc...z(S-a-b-c-...-z)), where S is the sum of all elements of the set. So the set is {a,b,c,...,z,(S-a-b-c-...-z)}

dP/da = bc...zS - 2abc...z -b²c...z - bc²...z - ... - bc...z²

dP/da = bc...z(S-b-c-...-z)-2abc...z

Setting this to 0 will give the maxima.

0 = bc...z(S-b-c-...-z)-2abc...z

2abc...z = bc...z(S-b-c-...-z)

a = bc...z(S-b-c-...-z) / (2bc...z)

a = (S-b-c-...-z)/2

In other words, if you keep all but 2 of the elements of the set constant then the product is maximized when the remaining two are equal.

Since there is no real difference between any of the elements of the set, you can choose any two unequal elements in the set and increase the total product by setting them both to their average.

Assume you have the set that maximizes the product and the there are at least 2 elements of that set that are unequal. By the previous reasoning you can replace two unequal elements in the set with their average and increase the product. This results in a set with a greater product...which contradicts our assumption that the set given was the one that maximized the product. The assumption that there are at least 2 unequal elements in the set that maximizes the product is incorrect. So the set that maximizes the product must therefore have all its elements equal.

To have all the elements of the set equal would mean they would need to be equal to k/n. k/n is rational because k and n are integers.

Edited April 3, 2008 by EventHorizon

[bonanova]

yup, good job.

I do want to mention that I got the problem from another website (why the problem is in quotes) and I said I did, but the name of the site was removed...

As for the original problem, I thought I would give my proof for it...

P = abc...z(S-a-b-c-...-z)), where S is the sum of all elements of the set. So the set is {a,b,c,...,z,(S-a-b-c-...-z)}

dP/da = bc...zS - 2abc...z -b²c...z - bc²...z - ... - bc...z²

dP/da = bc...z(S-b-c-...-z)-2abc...z

Setting this to 0 will give the maxima.

0 = bc...z(S-b-c-...-z)-2abc...z

2abc...z = bc...z(S-b-c-...-z)

a = bc...z(S-b-c-...-z) / (2bc...z)

a = (S-b-c-...-z)/2

In other words, if you keep all but 2 of the elements of the set constant then the product is maximized when the remaining two are equal.

Since there is no real difference between any of the elements of the set, you can choose any two unequal elements in the set and increase the total product by setting them both to their average.

Assume you have the set that maximizes the product and the there are at least 2 elements of that set that are unequal. By the previous reasoning you can replace two unequal elements in the set with their average and increase the product. This results in a set with a greater product...which contradicts our assumption that the set given was the one that maximized the product. The assumption that there are at least 2 unequal elements in the set that maximizes the product is incorrect. So the set that maximizes the product must therefore have all its elements equal.

To have all the elements of the set equal would mean they would need to be equal to k/n. k/n is rational because k and n are integers.

I tried the explicit formula for more than two terms and it got immediately complicated.

I do think it can be shown that dP/da [not just the partial derivative] = dP/db = ... = dP/dz at the extremum.

And then you can do a pair-wise proof for zero [as we both did] so they all are zero when all terms are k/n.

I'm still working it out on paper - it's harder to do the formatting on the display

Nice puzzle; and I used the Web as a refresher also in crafting my answer, mainly to reduce the steps,

but also ... taking the log before differentiating was a step I did not see on my own.

As a moderator of the site, I have to say I'm not sure this was so much a puzzle as a math exercise, but

[1] I enjoyed working it out ... and seeing the surprise answer, and

[2] the answer gave it a puzzle-like flavor.

[EventHorizon]

...

Nice puzzle; and I used the Web as a refresher also in crafting my answer, mainly to reduce the steps,

but also ... taking the log before differentiating was a step I did not see on my own.

As a moderator of the site, I have to say I'm not sure this was so much a puzzle as a math exercise, but

[1] I enjoyed working it out ... and seeing the surprise answer, and

[2] the answer gave it a puzzle-like flavor.

Yeah, I was a bit rusty on differentiation as well and ended up looking up taking the log too.

I think many good puzzles are simply math or logic exercises wrapped in a story. I'm sure if I took the time that I could hide much of the mathiness from the description of it.

[Guest]

Since the last post of this kind was so wildly popular (I was the only one to post....), I thought I would try another.

"For any positive integer, k, let Sk = {x1, x2, ... , xn} be the set of real numbers for which x1 + x2 + ... + xn = k and P = x1 x2 ... xn is maximised.

For example, when k = 10, the set {2, 3, 5} would give P = 30 and the set {2.2, 2.4, 2.5, 2.9} would give P = 38.25. In fact, S10 = {2.5, 2.5, 2.5, 2.5}, for which P = 39.0625.

Prove that P is maximised when all the elements of S are equal in value and rational."

Without using derivations, it can be easily proved that x1 must be equal to x2, while x1+x2 is constant, and x1*x2 is intended to be maximized.

Let S = x1+x2

let x1=S/2 + a

since x2=S-x1

x2=S - (S/2+a)

x2=S/2-a

then

x1*x2=(S/2+a)*(S/2-a)

x1*x2=S^2 - a^2

S^2 is constant and we want x1*x2 to be maximized

then a should be 0 for a^2 to be minimum, as a^2 is always positive.

If a= 0 then x1=x2.