VastoLorde95's blog

By VastoLorde95, history, 4 years ago, , Hi, In this problem, I am using the idea that AM >= GM just like in the editorial but with slightly different steps. Equality should hold when all elements are equal. So according to me, x = y = z and the solution I arrive at is that x = y = z = S / 3

But this is incorrect as seen from the test case

S = 10

a = 1, b = 6, c = 3

My solution gives x = y = z = 3.33 and hence xa·yb·zc =  169350.87

But the optimal solution is x = 1.0, y = 6.0, z = 3.0 with xa·yb·zc =  1259712

What is the flaw in my math? Is this not a correct way to use GM <= AM? I don't understand why my solution differs from the solution given in the editorial even though the principle behind both is the same. math, Comments (13)
 » why equal? •  » » 4 years ago, # ^ | ← Rev. 2 →   But for AM=GM inequality to hold shouldn't all elements be equal? So ax+by+cz means a x's b y's and c z's should all be equal right?http://www.artofproblemsolving.com/wiki/index.php/AM-GM says: "The equality condition of this inequality states that the arithmetic mean and geometric mean are equal if and only if all members of the set are equal"
 » 4 years ago, # | ← Rev. 2 →   As far as I understood, you have to solve with x + y + z = S, where a, b, c, S is given.
•  » » But for AM=GM inequality to hold shouldn't all elements be equal? So ax+by+cz means a x's b y's and c z's should all be equal right?
 » You wrote which is true and that equality will hold at x = y = z which is also true but there is no fixed value for the right hand side so it may be better for you to be less than a huge value than equal to a smaller one.This is why we go according to this method therefore, I would have gone on but I am tired of manipulating LaTex symbols.Some manipulation should show you that the term we want to maximize is now bounded above by a constant value (this is where the difference is between what your solution and authors solution) so you know that you can only get to that constant when and x + y + z = S.
•  » » Why is it an issue if there is no fixed value on the right hand side? Also if x+y+z <= S then it has to be bounded right?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   Look at the example you have given.For the solution you find (x=y=z=3.33) lhs = rhs, but for the optimum solution(x=1,y=6,z=3) lhs < rhs.What I am saying is that if your rhs is extremely huge and your lhs is slightly smaller than it then that is better than having a small rhs and an equal lhs.Hence, you want a constant rhs so that you know that the term you are maximizing can never do better than that.
•  » » » » Aahhhhh... I get it. So I found the condition for equality of AM and GM but that is not the condition for upper bound of GM?From what I understand you have manipulated to use AM >= GM in such a way that the AM is the upper bound and equality also guarantees optimality. Am I right?
•  » » » » » Exactly.
•  » » » » » » Thanks a ton! Spent 5 hours on this!
•  » » » » » Why should GM give maximum when you use it that way?
•  » » » » » » You have found an inequality which gives a constant upper bound for the GM. Now you know the conditions for which you can achieve equality. You use those conditions to maximize GM.I would prefer it if someone more experienced than me would verify my approach but I can't see any reason as of now for it to be wrong.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   I found out for 2 dimension why x/a = y/b gives maximum.I am assuming NO z at all so eq. is (x^a)*(y^b) and x+y=S x=S-y so the eqn. becomes ((S-y)^a)*(y^b)for max. we derive w.r.t y and equate to 0 i.e -a*(S-y)^(a-1)*(y^b) + b*(y^(b-1))*(S-y)^a = 0 solving we get (S-y)*b — a*y =0 => b*x=a*y => x/a=y/b i.e if x/a=y/b the eq. will be a maximum or minimum (Double derive and check i think it will be maximum) I have no idea how to do for 3d i.e with z included
{"ft_lang_label":"__label__en","ft_lang_prob":0.9473285,"math_prob":0.9887289,"size":3560,"snap":"2019-43-2019-47","text_gpt3_token_len":962,"char_repetition_ratio":0.11698537,"word_repetition_ratio":0.077885956,"special_character_ratio":0.27808988,"punctuation_ratio":0.08742515,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99884444,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22],"im_url_duplicate_count":[null,null,null,null,null,2,null,null,null,null,null,1,null,1,null,1,null,1,null,1,null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-20T12:31:11Z\",\"WARC-Record-ID\":\"<urn:uuid:2ec935fc-08f7-4030-bc65-91ff5747ec6d>\",\"Content-Length\":\"134049\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d9c1f9bb-6284-40fc-82de-adbc514ea93e>\",\"WARC-Concurrent-To\":\"<urn:uuid:f02915d3-9e86-4bd1-a67a-d916d8e09803>\",\"WARC-IP-Address\":\"81.27.240.126\",\"WARC-Target-URI\":\"http://codeforces.com/blog/entry/18493\",\"WARC-Payload-Digest\":\"sha1:HG7TLNN54JQGODHMK2D3EMBBLWPVCDIA\",\"WARC-Block-Digest\":\"sha1:TUKTS2QKJWCKAUNDGWTASZD72LKLWOIY\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570986707990.49_warc_CC-MAIN-20191020105426-20191020132926-00435.warc.gz\"}"}