Help with Jane Street Interview Question

[nimo]

You have two squares with a combined area of 1. What is the smallest area of a rectangle, which can fit both squares inside it without the interiors of the squares overlapping? You can assume that the sides of the squares are parallel to the sides of the rectangle. Thanks.

Edit: sorry, I stated the problem incorrectly. You need to find the smallest area of the rectangle which can fit any two squares of combined area 1 without overlap.

 

[euroazn]

Am I missing something here? The rectangle is just the two squares side by side?

 

[nimo]

I believe you're correct, but they want to know the area of the rectangle.

Edit: sorry, I stated the problem incorrectly. You need to find the smallest area of the rectangle which can fit any two squares of combined area 1 without overlap.

 

[Yike Lu]

1 X 2/sqrt(2)

 

[nimo]

Can you show your work? This is as far as I got. You have two squares with sides x and y. Assume x>=y>0. The smallest rectangle is just the two squares side by side, so its area A = x * (x + y) = x^2 + x*y. We now have to find the maximum area of the rectangle given that x^2 + y^2 = 1.

 

[Yike Lu]

There are two extreme cases to consider, one in which the first square has all the area except some small epsilon. The other is where both squares are exactly equal. When they are exactly equal, we have 2 x^2 = 1 <=> x = 1/sqrt(2). Then the total horizontal length is 2/sqrt(2). This is the maximum total length for one side of the rectangle. The minimum is the case where the first square has all the area, where the side is 1.

Hence 1 x 2/sqrt(2).

I know this isn't a fully rigorous answer, but it was the intuitive one for me. The underlying reasoning has to do with how "efficient" an arrangement of two boxes is with regard to maximum area for minimum length, and minimum area for maximum length.

 

[financeguy]

Can you show your work? This is as far as I got. You have two squares with sides x and y. Assume x>=y>0. The smallest rectangle is just the two squares side by side, so its area A = x * (x + y) = x^2 + x*y. We now have to find the maximum area of the rectangle given that x^2 + y^2 = 1.

Think the responders misunderstood the question.
Using Lagrange multipliers...

2x+y=L*2x
x=L*2y
x^2+y^2=1

2xy+y^2=L*2xy
x^2=L*2xy
x^2=2xy+y^2
2x^2=x^2+2xy+y^2
2x^2=(x+y)^2
xsqrt(2)=x+y
x(sqrt(2)-1)=y

x^2+x^2(sqrt(2)-1)^2=1
x^2+x^2(2-2sqrt(2)+1)=1
x^2(4-2sqrt(2))=1
x=1/sqrt[4-2sqrt(2)] ~ .92
y=(sqrt(2)-1)/sqrt[4-2sqrt(2)] ~ .38

x*(x+y)=1/sqrt[4-2sqrt(2)]*sqrt(2)/sqrt[4-2sqrt(2)] =sqrt(2)/(4-2*sqrt(2)) ~ 1.2071 (this is the number you want)

 

[nimo]

Yes, you are correct, financeguy. A friend of mine came up with the answer using trig:

Let x = cos(t), y = sin(t) for some t in (0, pi/4).
A = cos(t) * [cos(t) + sin(t)]
A = cos^2(t) + cos(t)*sin(t)
A' = -2*cos(t)*sin(t)+cos^2(t)-sin^2(t)

Using the double-angle identities we have:
cos(t)*sin(t) = 1/2 * sin(2t)
cos^2(t) - sin^2(t) = cos(2t)

A' = cos(2t) - sin(2t)
Setting this equal to 0, we have:
cos(2t) = sin(2t)
=> t = pi/8

A = cos^2(pi/8) + cos(pi/8)*sin(pi/8)
A = 1/2 * [1 + cos(2*pi/8)] + 1/2 * sin(2*pi/8)
A = [1 + sqrt(2)] / 2

 

[Kirill Al]

The smallest area of a rectangle would equal to 1. The question doesn't specify that squares cannot be equal, therefore, in the case when two squares are of equal size, with side = 1/sqrt(2), the area of rectangle made by joining this squares side-by-side is 1.

 

[Yike Lu]

Sorry, neither of you guys are making any sense as far as how you're interpreting this question. First it's the smallest rectangle, then you have to find the maximum (wtf?) area of the rectangle given x^2 + y^2 = 1.

Then financeguy throws in Lagrange multipliers, which seems like complete overkill, as do the trig identities.

Draw a picture and upload it.

 

[AndrewChang]

no proof required, the minimum area is 1. for the case of non equal rectangles, the answer STILL doesn't change from the fact that the minimum rectangle to put both of them inside, is still the two squares next to each other. therefore the answer is sqrt(Area 1st rectangle) * (sqrt(Area 1st) + sqrt(Area 2nd)).

 

[nimo]

Sorry, it was my fault for not explaining it properly. You need to find the smallest area of the rectangle that can fit any two squares with a combined area of 1. Let's say you have two equal squares with sides of 1/sqrt(2). The smallest rectangle is simply the two squares side by side, which has an area of 1/sqrt(2) * 2/sqrt(2) = 1. However, squares with sides of 0.8 and 0.6 also have a combined area of 1. The smallest rectangle that encompasses both of those has an area of 0.8*1.4 = 1.2. So now we know that the first rectangle with an area of 1 is too small to encompass the squares with sides 0.8 and 0.6. Is 1.2 too small as well to fit another pair of squares whose area also adds up to 1? That's what is meant by finding the maximum area of the rectangle. It needs to be just big enough to fit all possible pairs of squares with combined area 1.

 

[aaronhotchner]

That's what is meant by finding the maximum area of the rectangle. It needs to be just big enough to fit all possible pairs of squares with combined area 1.

We call that a minimum.

 

[aaronhotchner]

The 1.2071 answer appears to be correct. The area required by the squares hits a maximum when one of the squares has side length somewhere between 0.92 and 0.93 as best I can tell.

>> for i = .5:.00001:.99999
areaOfI = i^2;
areaOfJ = 1 - areaOfI;
lengthOfJ = sqrt(areaOfJ);
rectangle(floor(i*100000.00001 - 49)) = max(i,lengthOfJ) * (i + lengthOfJ);
end
>> max(rectangle)
ans =
1.207106781184437

 

[AndrewChang]

The 1.2071 answer appears to be correct. The area required by the squares hits a maximum when one of the squares has side length somewhere between 0.92 and 0.93 as best I can tell.

>> for i = .5:.00001:.99999
areaOfI = i^2;
areaOfJ = 1 - areaOfI;
lengthOfJ = sqrt(areaOfJ);
rectangle(floor(i*100000.00001 - 49)) = max(i,lengthOfJ) * (i + lengthOfJ);
end
>> max(rectangle)
ans =
1.207106781184437

http://www.wolframalpha.com/input/?i=maximize+sqrt(x)+*+(+sqrt(x)+++sqrt(1-x))

 

[Radoslav]

that is not completely accurate. you are maximizing the quantity \(\sqrt{x}(\sqrt{x}+\sqrt{1-x})\) over \((0,1)\), which what you want only when \(\sqrt{x}\geq\sqrt{1-x}\) --- think about it --- which happens exactly when \(x\geq 1/2\).

in other words, denoting x to be the bigger area/side (\(x\geq 1-x\)), you don't need software to see that this \(x+\sqrt{x-x^2}\) is a decreasing function on \([1/2,1)\), so the maximum is obtained at \(x=1/2\), that is, when both squares have the same side.

 

[aaronhotchner]

I think you're solving the absolute opposite problem. If both squares are identical, then the rectangle has area 1 because it is identical to the sum of the squares. That is the solution to the problem "what is the smallest rectangle that can hold 2 squares with total area 1," and unsurprisingly that rectangle also has area 1.

Also, that is not a decreasing function on [1/2, 1), so I guess you do need software after all.

 

[AndrewChang]

that is not completely accurate. you are maximizing the quantity \(\sqrt{x}(\sqrt{x}+\sqrt{1-x})\) over \((0,1)\), which what you want only when \(\sqrt{x}\geq\sqrt{1-x}\) --- think about it --- which happens exactly when \(x\geq 1/2\).

in other words, denoting x to be the bigger area/side (\(x\geq 1-x\)), you don't need software to see that this \(x+\sqrt{x-x^2}\) is a decreasing function on \([1/2,1)\), so the maximum is obtained at \(x=1/2\), that is, when both squares have the same side.

this is totally irrelevant, but i do not believe that is a picture of you but (y)

 

[Radoslav]

Also, that is not a decreasing function on [1/2, 1), so I guess you do need software after all.

hahahah, of course — it is not decreasing there — that was pretty stupid, sorry. still, modulo this "overlooking", the solution is still not hard: want to find where \(1+\frac{1-2x}{\sqrt{x-x^2}}=0\) on \([1/2,1)\), so effectively you're solving \(8x^2-8x+1=0\). The roots are \(x_{1,2}=\frac12\pm\frac{\sqrt{2}}{4}\), so the quantity is increasing on \([1/2,1/2+\sqrt{2}/4]\) and decreasing on \([1/2+\sqrt{2}/4,1)\).

and no, that is not me on picture

 

[aaronhotchner]

Yes, that's all fine, and it leads to the solution that has been confirmed multiple times: the area of the resulting rectangle is ~1.2071.