Home » Ask & Discuss » Mathematics. » Algebra « Back to Discussion

Algebra

Forum Expert

Joined:	10 Jul 2008
Post:	598

1 Dec 2008 18:38:07 IST

0 People liked this

1066

A problem in maximization: Everyone's invited

None

Find positive integers $n$ and $a_1$ , $a_2$ , $\ldots$ , $a_n$ so that $\sum_{i=1}^n a_i =1000$ and the product $a_1\cdot a_2 \cdot \ldots \cdot a_n$ is as large as possible.

Share this article on:

Comments (16)

Ankit Rana

Blazing goIITian

Joined: 29 Nov 2008

Posts: 461

1 Dec 2008 20:46:43 IST

Like 0 people liked this

Anant Kumar

Forum Expert

Joined: 10 Jul 2008

Posts: 598

1 Dec 2008 22:40:33 IST

Like 0 people liked this

Are you sure that you have applied AM-GM correctly?

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

2 Dec 2008 09:13:15 IST

Like 0 people liked this

4.3³³² ? My credo was: "Keep 'em close to e"

Anant Kumar

Forum Expert

Joined: 10 Jul 2008

Posts: 598

2 Dec 2008 10:12:02 IST

Like 0 people liked this

Indeed, the maximum product is what hsbhatt sir has obtained. The numbers n and a's?

Conjurer

Blazing goIITian

Joined: 20 Feb 2008

Posts: 629

2 Dec 2008 10:25:11 IST

Like 0 people liked this

I remember such a problem in the book Problem Solving Through Problems by Larsen, but I didnt get the logic.

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

2 Dec 2008 10:46:00 IST

Like 2 people liked this

There will be 332 3's and 2 2's. So a total of 334 numbers. So n = 334

I had done a similar problem once earlier. But there was no restriction that the numbers be natural. I will give you the link http://goiit.com/posts/list/algebra-write-271-as-the-sum-of-positive-real-numbers-so-as-73541.htm#364087

Now if you follow that procedure, you will notice that if all a_i are real, the maximum always occurs when all the a_i are equal to e. This is actually independent of the sum of the a_i

But here they got to be natural numbers. So, we must choose our numbers in such a way that they are close to 2.71. So choose as many 3's as possible, and ensure that the deviation $\sum |a_i-e|$ is minimized

Our first instinct would be to go for 333 3's and one 1. But look at 332 3's and 2 2's. This has lesser deviation than the earlier combination and its easy to check that indeed the product is greater in this case.

Thus the winning combination is 332 3's and 2 2's giving the product as 4. 3³³². You can even check with their sum being 10. The max product of 36 occurs when we choose 3 3's and 2 2's.

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

2 Dec 2008 11:00:34 IST

Like 1 people liked this

@conjurer-could you tell me which chapter of that book? Just want to check what logic was used there.

edit: ok got it. its the 1st chapter (not inequalities as I thought). At first sight the procedure looks a bit like conjecture. Got to see what their logic is. But the conclusion is the same as i have indicated. 2 two's and rest all three's.

Maybe we can get bolder and generalise: for n>5

If n = 3k, then all the a_i equal 3

If n = 3k+1 2 two's and rest all three's. (1000 falls in this category)

If n = 3k+2, then 1 two and rest all 3's

Ankit Rana

Blazing goIITian

Joined: 29 Nov 2008

Posts: 461

2 Dec 2008 13:17:53 IST

Like 1 people liked this

how bout this

using AM>= GM

{ (x₁ + x₂ +....+x_n )/n }ⁿhas to be maximized which is discrete

so f(x) = ( N / x )^x has to be max. (this fun is continuous)

for maxima f'(x)=0

i.e. (N/x)^x {log (N/x) - 1} = 0

i.e N/x = e

or x = N/e

here N=1000

so it should be divided in parts

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

2 Dec 2008 14:56:27 IST

Like 0 people liked this

@ankit: that would be the reckoning if the a_i were +ve real numbers. But here we are restricted to natural numbers. But in my solution, I have used the observation that solution from real numbers is each a_i is close to e whatever be the constant sum of the a_i. So the natural numbers should be chosen as close as possible to 2.71

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

3 Dec 2008 11:38:23 IST

Like 0 people liked this

kaymant sir, is there any alternative solution? Any feedback?

Anant Kumar

Forum Expert

Joined: 10 Jul 2008

Posts: 598

3 Dec 2008 14:25:18 IST

Like 0 people liked this

Sorry for the delayed response. And yes, there is an alternative.

Given: $\sum_{i=1}^n a_i = 1000$

We can assume that $a_1\le a_2\le \ldots\leq a_n$ . Let $P=a_1\cdot a_2\cdot\ldots\cdot a_n$ . The following observations can be made:

1) $a_j-a_i\geq 2$ does not yield the maximum value of $P$ , since replacing $a_i$ , $a_j$ by $a_i + 1$ , $a_j-1$ increases $P$ without altering the sum.

2) $a_1=1$ does not yield the maximum, since replacing $1,\, a_n$ by $2$ and $a_n -1$ increases the product.

3) $a_i\geq 5$ does not yield the maximum, since $2(a_i-2)=2a_i-4> a_i$ . Also, since $4=2^2$ , we can assume that all the $a_i$ 's are either $2$ or $3$ . And thus $P_{max}=2^k3^m$ where $2k + 3m =1000$ .

4) $k\geq 3$ does not yield the maximum value, since $2^3<3^2$ .

Hence $k\leq 2$ . Since, $k\neq 1$ (since that would imply $3m = 998$ which is not possible), we get $k=2$ , in which case $m = 332$ . Hence, $P_{max}=2^2\cdot 3^{332}$ and so $n = 334$ .

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

3 Dec 2008 14:29:45 IST

Like 0 people liked this

ah! that explains the observations in the solution by larson.

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

4 Dec 2008 09:50:35 IST

Like 1 people liked this

Quite by accident, I discovered this problem in two places:

This is from IMO 1976 and the solution in the IMO Compendium is the same as what sir has given.

I was a bit apprehensive whether my method was a lot of hand-waving. Luckily, this morning, in the very last chapter of the book "Art and Craft of Problem Solving" I discovered this IMO problem solved by them with the same argument as mine. The caveat is that it is in a section called "Eulerian methods" which refers to intuitive but not entirely rigorous solutions that yet work!

So it may be better to go by the "official IMO solution" which sir has also given.

Anant Kumar

Forum Expert

Joined: 10 Jul 2008

Posts: 598

4 Dec 2008 11:02:06 IST

Like 0 people liked this

I knew the solution but I didn't know that it was an IMO problem. In fact, the solution was a joint effort of mine and one of my student.

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

4 Dec 2008 11:32:36 IST

Like 1 people liked this

a student! who is this prodigy?? is he on this forum? anyway great work

Anant Kumar

Forum Expert

Joined: 10 Jul 2008

Posts: 598

4 Dec 2008 15:08:36 IST

Like 0 people liked this

No, he is not in the forum. He went to the IMO 2008 selection camp and was also awarded some kind of Elegant Solution award. Some other of my students are in the forum though -- jishnu, rajat sen, ronty, hamba.

Quick Reply

Reply

	Some HTML allowed.
	Keep your comments above the belt or risk having them deleted.
	Signup for a avatar to have your pictures show up by your comment
	If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team