2
$\begingroup$

How do I find the minimum height of this table?

+---+---+---+
| a |   |   |
+---+---+---+
|   | b |   |
+---+---+---+
|   |   | c |
+---+---+---+

$a$, $b$, and $c$ are the known (and fixed) areas of their respective cells.

Each cell's area is the height of its row multiplied by the width of its column. In other words:

$$ a = w_0 \cdot h_0 $$ $$ b = w_1 \cdot h_1 $$ $$ c = w_2 \cdot h_2 $$

The total width of the table is also fixed and known:

$$ W = \sum_i w_i $$ $$ 0 = \sum_i \frac{d}{dt}w_i $$

You can see that the height of the table is:

$$ H = h_0 + h_1 + h_2 $$ $$ = \frac{a}{w_0} + \frac{b}{w_1} + \frac{c}{w_2} $$

Now, normally I would set $\frac{d}{dt}H = 0$. So let's try that:

$$ \frac{d}{dt}H = 0 = - \frac{a}{w_0^2} \cdot \frac{d}{dt}w_0 - \frac{b}{w_1^2} \cdot \frac{d}{dt}w_1 - \frac{c}{w_2^2} \cdot \frac{d}{dt}w_2 $$

Hmm. I can eliminate a variable by assuming that one of the column widths changes at the same rate as $t$:

$$ \frac{d}{dt}w_0 = 1 $$

But I still need a lot more equations to solve this. Where do I get them?

Note: all column widths are non-negative, the total table width is positive, and the cell areas are non-negative. Or all these things can be positive if it makes it easier.

P.S. By understanding how to solve this simple case I'm hoping to inch closer to a solution to another question of mine.

$\endgroup$
1
  • 1
    $\begingroup$ Read about "Lagrange multipliers" somewhere. $\endgroup$ – David C. Ullrich Aug 1 '19 at 20:45
3
$\begingroup$

This problem has two degrees of freedom: there are three column widths, but the sum of those widths is known so the degrees of freedom are reduced to only two. Therefore this will be easier to solve if we use two variables.

Let's use $x$ for the width of the first column and $y$ for the width of the second. Then the width of the third column is $W-x-y$ where $W$ is the known sum of the widths.

Then, using the known areas of the cells on the main diagonal, the heights of the three rows are

$$\frac ax,\ \frac by,\ \frac{c}{W-x-y}$$

The height of the complete table is then

$$H = \frac ax + \frac by + \frac{c}{W-x-y}$$

The values of $x$ and $y$ are limited by $0 < x,\ 0 < y,\ x+y < W$ so there are no boundaries. Thus the minimum value of $H$, if one exists, is where the two partial derivatives are zero. So we get

$$\frac{\partial H}{\partial x} = -\frac{a}{x^2}+0-\frac{c}{(W-x-y)^2}(-1)=0 $$

and

$$\frac{\partial H}{\partial y} = 0-\frac{b}{y^2}-\frac{c}{(W-x-y)^2}(-1)=0 $$

So we get

$$\frac{c}{(W-x-y)^2}=\frac{a}{x^2}$$

and

$$\frac{c}{(W-x-y)^2}=\frac{b}{y^2}$$

Equating the two right-hand sides and solving yields

$$y=\sqrt{\frac ba}x$$

We now are down to only one independent variable, $x$. You substitute the expression for $y$ into either of the two expressions for $\frac{c}{(W-x-y)^2}$ and solve for $x$. Finally, you substitute that expression for $x$ into the formula for $H$ and get your final answer. But a shorter way is to see that the problem is symmetric in $a, b, c$ and we could have set $x$ and $y$ to the first and last columns. Following our work above would then yield

$$z=W-x-y=\sqrt{\frac ca}x$$

I'll let you finish from here, as in the bulk of @Henry's answer. Note that the intuition of @Henry regarding the proportions of each column/row is correct: $\sqrt a: \sqrt b: \sqrt c$.

$\endgroup$
3
  • $\begingroup$ Can you help me understand why "the minimum value of H, if one exists, is where the two partial derivatives are zero"? At David's urging in a comment above I'm reading up on Lagrange multipliers. Are they the reason? $\endgroup$ – Matt Thomas Aug 2 '19 at 12:35
  • 1
    $\begingroup$ @MattThomas: Lagrange multipliers do use that idea but more is involved. I prefer to avoid Lagrange multipliers and use independent variables, as in my answer. My idea uses a theorem from 2nd year calculus. Any local minimum value, if any exists, of a function of multiple variables that is not on a boundary of the domain is attained at a point where the partial derivatives are zero or undefined. In your problem there is no boundary (the domain is an open triangle) and the derivatives are always defined. Thus either there is no minimum or we search for zero derivatives. Is that clear? $\endgroup$ – Rory Daulton Aug 2 '19 at 12:59
  • $\begingroup$ Yes, awesome. For me it's been about a decade since 2nd year calculus, and unfortunately my line of work hasn't required it until now :) $\endgroup$ – Matt Thomas Aug 2 '19 at 13:10
1
$\begingroup$

Intuitively I feel that the heights and widths should each be in the ratio $\sqrt{a}:\sqrt{b}:\sqrt{c}$

and so the widths should be $\sqrt{a}\frac{W}{\sqrt{a}+\sqrt{b}+\sqrt{c}}$, $\sqrt{b}\frac{W}{\sqrt{a}+\sqrt{b}+\sqrt{c}}$, $\sqrt{c}\frac{W}{\sqrt{a}+\sqrt{b}+\sqrt{c}}$

so the heights should be $\sqrt{a}\frac{\sqrt{a}+\sqrt{b}+\sqrt{c}}{W}$ , $\sqrt{b}\frac{\sqrt{a}+\sqrt{b}+\sqrt{c}}{W}$ , $\sqrt{c}\frac{\sqrt{a}+\sqrt{b}+\sqrt{c}}{W}$

leading to the minimum overall height being $\dfrac{(\sqrt{a}+\sqrt{b}+\sqrt{c})^2}{W}$

and empirical experimentation suggests this is correct


As for a proof, let's initially forget $c$ and try to minimise the height $H=h_a+h_b$ of $2\times 2$ boxes knowing $w_a+w_b=W$ and $h_aw_a=a$ and $h_bw_b=b$

We can say that $H = \frac{a}{W-w_b}+\frac{b}{w_b}$

so $\frac{dH}{dw_b} = \frac{a}{(W-w_b)^2}-\frac{b}{w_b^2} = \frac{a}{w_a^2} -\frac{b}{w_b^2}$ and it is not difficult to see that this is zero when $w_a^2: w_b^2$ is the same as $a:b$ which is $h_aw_a : h_bw_b$, i.e. when $w_a: w_b$ is the same as $ h_a : h_b$ and so the same as $\sqrt{a}:\sqrt{b}$, and that this minimises the height of this $2\times 2$ selection

Thus we know that this bit of the height is minimised when the respective widths and heights are each in the ratio $\sqrt{a}:\sqrt{b}$ and any other possibility is not optimal. The same is true with any other similar pairs, so the widths and heights of second and third columns and rows need to be in the ratio $\sqrt{b}:\sqrt{c}$ and the widths and heights of first and third columns and rows need to be in the ratio $\sqrt{a}:\sqrt{c}$. The only way to do this is in the way I initially explained. It is easily extended to other similar $n \times n$ questions

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.