Designing Under Constraints

Problem. A school has a fencing budget of $408$ dollars for a rectangular garden. The two edges parallel to the sidewalk cost $12$ dollars per meter each. The two edges perpendicular to it cost $8$ dollars per meter each. Assume the site can fit all three proposals below, fence can be bought in the exact lengths needed, and the full enclosed area is plantable.

• Plan A. $12$ m parallel to the sidewalk by $6$ m perpendicular.
• Plan B. $10$ m parallel by $10$ m perpendicular.
• Plan C. $12$ m parallel by $9$ m perpendicular.

Find the cost and area of each plan. Which feasible proposal has the most planting area?

Solution. Call the dimension parallel to the sidewalk $s$ and the perpendicular dimension $d$, both in meters. Multiply each dimension by its rate and by two because the fence has two edges of each kind.

$$\begin{aligned} \text{Cost in dollars}&=2(12s)+2(8d),\\ \text{Area in square meters}&=sd. \end{aligned}$$

For A, the cost is $2(12)(12)+2(8)(6)$ dollars, or $384$ dollars. Its area is $12(6)$ square meters, or $72$ square meters.

For B, $2(12)(10)+2(8)(10)$ gives a cost of $400$ dollars. Its area is $10(10)$ square meters, or $100$ square meters.

For C, $2(12)(12)+2(8)(9)$ gives a cost of $432$ dollars. Its area is $12(9)$ square meters, or $108$ square meters.

B gives the most planting area among the feasible proposals. C has more area, but its cost exceeds the cap. A leaves more money unspent, but the objective is planting area.

Problem. The school reconsiders the same three garden plans. It still has a $408$ dollar cap. Previously, each of the two edges parallel to the sidewalk cost $12$ dollars per meter and each of the two perpendicular edges cost $8$ dollars per meter. An existing fence can supply one whole parallel edge of any proposal at no cost. The other rates, dimensions, and planting areas stay the same.

• Plan A. $12$ m parallel by $6$ m perpendicular. Its old cost was $384$ dollars.
• Plan B. $10$ m parallel by $10$ m perpendicular. Its old cost was $400$ dollars.
• Plan C. $12$ m parallel by $9$ m perpendicular. Its old cost was $432$ dollars.

Find the new costs and choose the feasible proposal with the most planting area. What can you conclude if the three plans are only a sample?

Solution. Each plan saves $12$ dollars for every meter of one parallel edge. The savings are $144$ dollars for A and C and $120$ dollars for B.

C now meets the budget. It is the best tested plan because its area is greater than the other two areas. Its area was already greatest of the three before the change. Using the existing fence made that area affordable.

If the list is a sample, the recommendation applies to these three plans. To claim a proven optimum, we would need to know the full range of layouts the site permits and show that none of them can do better.

Problem. A tray is $27$ cm wide and $19$ cm deep inside. Each rectangular tile is $8$ cm by $5$ cm. Use one layer with edges parallel to the tray edges. Each row runs across the tray width and has just one tile orientation. Rows may differ in orientation. Tiles can touch, and rows cannot overlap. What is the most tiles that fit under these rules?

Solution. A $5$ cm deep row holds $3$ tiles across. Three widths of $8$ cm use $24$ cm, and a fourth would need $32$ cm. An $8$ cm deep row holds $5$ tiles across. Five widths of $5$ cm use $25$ cm, and a sixth would need $30$ cm.

At most two $8$ cm deep rows can fit in $19$ cm. For each possible number, fill the remaining depth with as many $5$ cm deep rows as will fit.

The maximum in this layout family is $11$ tiles. One $8$ cm row and two $5$ cm rows use $18$ cm of depth and achieve that count. The cases cover all allowed row counts. For layouts that break these row rules, the table gives no upper bound. A different argument would be needed to decide whether any such layout can hold more.

Problem. A closed rectangular box with a lid needs $480\text{ cm}^3$ of total inside volume and a height of $5$ cm. It has a full-height divider spanning the width. The box width can be any positive length up to $9$ cm, and there is no separate length limit. Ignore board thickness, overlaps, and cutting waste. Find the length and width that use the least board for the six outside faces and the divider. Prove the minimum and give the board area.

Solution. Measure the width $w$ and length $\ell$ in centimeters. The height and volume fix the base area at $96$ square centimeters.

$$w\ell=\frac{480}{5}.$$

The base and lid together need $192$ square centimeters of board. Two walls and the divider each have area $5w$. The other two walls each have area $5\ell$. Therefore the board area in square centimeters is

$$S=192+5(3w+2\ell).$$

A board-area bound for every feasible width#

Try width $6$ cm and length $16$ cm. The two terms $3w$ and $2\ell$ have numerical values $18$ and $32$. Their product is $576$ and their sum is $50$. Compare that with two equal terms of $24$: their product is also $576$, but their sum is only $48$.

For any feasible width, put $a=3w$ and $b=2\ell$. Their product is always $576$ because $w\ell$ is fixed at $96$. The identity below compares their sum with their difference.

$$\begin{aligned} (a+b)^2&=4ab+(a-b)^2,\\ (a+b)^2&=2304+(a-b)^2. \end{aligned}$$

The square of the difference is at least zero. Since both terms are positive, their sum is at least $48$. The bound is reached when the difference vanishes, so the two terms must both be $24$. This requires width $8$ cm and length $12$ cm. The width meets the $9$ cm cap, and the volume is $8\cdot12\cdot5$ cubic centimeters, or $480$ cubic centimeters. The equality case is therefore feasible.

∎

The minimum board area is $192+5(48)$ square centimeters, or $432$ square centimeters. Every permitted size was covered because the proof used only the fixed product and positivity before checking the width cap at the equality case.

Problem. A shop can order either of two closed rectangular packages. It needs exactly $480\text{ cm}^3$ of capacity, and both designs fit the shelf. The board costs $0.5$ cents per square centimeter of board used or wasted. Each package also has a fixed cutting fee. Initially the shop budgets for no waste.

• Design A. Inside dimensions $12$ cm by $10$ cm by $4$ cm. Cutting fee $12$ cents.
• Design B. Inside dimensions $10$ cm by $8$ cm by $6$ cm. Cutting fee $36$ cents.

Ignore board thickness and overlaps. Which package costs less per unit at first? Which costs less if A needs an extra $12\text{ cm}^2$ of board per package for waste and B still has no waste?

Solution. The products $12\cdot10\cdot4$ and $10\cdot8\cdot6$ both give $480\text{ cm}^3$, so both packages meet the capacity requirement.

For A, the six faces use $2(120+48+40)$ square centimeters of board, or $416$ square centimeters.

For B, they use $2(80+60+48)$ square centimeters, or $376$ square centimeters.

Multiply the purchased area by $0.5$ and add the cutting fee to get the cost in cents.

For A, $0.5(416)+12$ gives $220$ cents initially.

For B, $0.5(376)+36$ gives $224$ cents initially.

The revised estimate adds $6$ cents to A because the shop pays for $12$ more square centimeters.

A is cheaper at first by $4$ cents per package. With the revised waste estimate, B is cheaper by $2$ cents. An additional $8$ square centimeters for A would add exactly $4$ cents, enough for a tie. That threshold shows how sensitive the first decision is to the waste estimate.