Monday, January 2, 2017

Lagrange multiplier to solve "Mushroom Scientists" problem

Yesterday I was trying to solve this problem on codeforces and found its solution very interesting .. to be honest I had to do alot of research to understand the editorial solution .. so I managed to write a clearer documentation for how to solve these kind of problems.

First of all the problem is that you are trying to maximize f(x,y,z) = x^a Y^b Z^c with the constraint function g(x,y,z) = X+Y+Z = S ..

First of all if (a,b,c) = (0,0,0) then the maximum you get for f(x,y,z) is 1 :) .. otherwise lets solve the problem of at least having one of them > 0.

We can use Lagrange multiplier to solve this problem by doing the following:

=> f(x,y,z) = ƛg(x,y,z) -> Lagrange multiplier
=> x^a . y^b . z^c = ƛ(x+y+z)

by taking derivative d/dx we get:

=> ax^(a-1) . y^b . z^c = ƛ(1+0+0) = ƛ -> (1)

by taking the derivative d/dy we get:

=> bx^a . y^(b-1) . z^c = ƛ(0+1+0) = ƛ -> (2)

by taking the derivative d/dz we get:

=> cx^a . y^b . z^(c-1) = ƛ(0+0+1) = ƛ -> (3)

This implies the following:

=>  ax^(a-1) . y^b . z^c = bx^a . y^(b-1) . z^c = cx^a . y^b . z^(c-1) = ƛ
=> (1) = (2) = (3)

By solving  (1) and (2) together we get:

=> ax^(a-1) . y^b . z^c = bx^a . y^(b-1) . z^c = ƛ
=> ax^(a-1) . y^b = bx^a . y^(b-1)
=> bx = ay
=> a/x = b/y -> (4)

By solving (2) and (3) we get:

=>  bx^a . y^(b-1) . z^c = cx^a . y^b . z^(c-1)
=> bz = cy
=> c/z = b/y -> (5)

From (4) and (5) we get:

a/x = b/y = c/z -> (6)

Now we can use this fact in g(x,y,z) we get:

=> x+y+z = S
=> x+bx/a+cx/a = S
=> ax+bx+cx = Sa
=> x = Sa/(a+b+c) -> (7)

Doing the same for y and z you get:

=> y = Sb/(a+b+c)
=> z = Sc/(a+b+c)

Now the problem is solved and here is my code: