http://www.codechef.com/problems/J7
I submitted this problem and got “correct ans”,the problem is really simple if u assume that the rectangle is a square.I saw about 15 other submissions all assuming the same thing Vol is max when rect is a square but CAN ANYONE PROOVE THIS?
Assuming that you can partially differentiate something, make both partials equal to 0 (to find the min/max point) and equate them together… (I should have checked this before writing anything!)
Let x, y and z be the dimensions in their respective axes
As there are 4 edges in each dimension, of equal length
(1) P = 4x + 4y + 4z where P is the length of the wire.
(2) V = xyz where V is the volume
Rearrange equation (1) to give
(3) z = B - x - y, where B = P/4
Substitute (3) into (2) to give
(4) V = (B - x - y)xy
Rearranging to give
(5) V = Bxy - yx^2 - xy^2
Remembering that P is not considered a function of x, y or z as it is a constant,
partially differentiate in terms of x to give
(6) V’x = By - 2xy - y^2
And Partially differentiate in terms of y to give
(7) V’y = Bx - 2xy - x^2
Let these both equal 0 as we are looking for the point which their gradient is zero:
(8) By - 2xy - y^2 = 0
(9) Bx - 2xy - x^2 = 0
We can then simplify to give
(10) B - 2x - y = 0
(11) B - 2y - x = 0
Equating together:
(12) B - 2x - y = B - 2y - x
Rearranging (the Bs cancel) to give:
(13) x = y
Therefore, as x, y and z were arbitrarily chosen (and fully interchangeable), we have proved that the optimal volume is when x = y = z.
Saying this, Ive just noticed the link to the original problem… which disregards what Ive written. Intuition says that if the sheet has a greater area than the perfect x=y=z cuboid, the optimised result CANNOT be x=y=z. Ill come back to this one as the wife’s getting angry!
!— EDIT
Aha, ignore my ‘intuition’… the last attempt can be built upon to include the surface area condition. (Bit more rushed and less mathematical:)
As a consequence of the proof above… Consider when the sheet with area A is compared to the surface area S (created by the optimised cube x=y=z)
Case1, A > S:
There is excess sheet material, but the cuboid cannot be expanded in any dimension as this would create less volume, due to P being limited. Therefore the cuboid is still the optimised x=y=z. Area of sheet wasted: S - 6x^2. P is fully used.
Case2, A<S:
The cuboid must decrease in size to account for less sheet material. If the optimal cube decreases to the size at which its surface area equals the area of the sheet, it has retained it’s maximum volume efficiency. Therefore the cuboid is still the optimised x=y=z. Length of wire wasted: P - 12x. A is fully used.
Case3, A=S:
The optimal case where all of the wire is efficiently used and the same goes for the sheet. Therefore the cuboid is still the optimised x=y=z.
Conclusion
Due to this being all possible cases, the shape being a perfect cube is an invariant, true in all cases. The variables for the length of wire and area of sheet will not change the optimal scenario being x = y = z for the dimensions. This is why the assumption can be made.
Last line won, man! 