Wednesday, January 30, 2013

Curious Cuboids, Part 2


Many of the problems in my previous post were instances of a general question:

Given three positive numbers V, S, and E, does there exist a cuboid with volume V in cubic inches, surface area S in square inches, and edge sum E in inches? 

When I considered this question, I found that such a cuboid exists if and only if


   E^2 S^2 - 2 S^3 - 16 E^3 V + 36 E S V - 108 V^2 >= 0.


The inequality was easy to obtain as soon as I realized that the desired cuboid exists if and only if the following polynomial in p has three positive roots:


 p^3 - E p^2  + (S/2) p -V.

(The left-hand side of the inequality is the discriminant of the polynomial.) Proof sketches are appended at the end.

***

The VSE inequality can be expressed in terms of two variables, the scaled surface area s = S/(2E^2) and scaled volume v = V/(E^3). In terms of these parameters, the space of all possible cuboids looks like so:


Each light-blue or dark-blue point corresponds to a cuboid (except for the dashed line along the bottom, which is s = 0). The two curved boundaries are where the discriminant vanishes, indicating a repeated root. Along the left boundary, there is a double root and its value is smaller than the other root; these are the rod-shaped cuboids. Along the right boundary, there is a double root and its value is larger than the other root; these are the tile-shaped cuboids. The right and left boundaries meet at a point right at the top; this cuboid is both rod-shaped and tile-shaped, i.e., it is a cube.

I put a little tour of the space up on YouTube here.

***



Well, it turns out that a cuboid can't have V, S, and E numerically equal when measured in the same system of units. Seems a shame, really. Well, there's a desperate example in one of my notebooks with edge lengths 2, i, and -i.

But to keep it real, let's open things up to other shapes. Define the diameter of a 3D shape to be the greatest possible distance between two of its points. Can you find a shape for which the volume, surface area, and diameter are all numerically equal when measured in the same system of units? (A few examples are on my whiteboard right now.)


***

It is nice to have an if-and-only-if condition, but the inequality is bit complicated. A few simpler, "only-if" inequalities (necessary conditions) are easy consequences of the inequality relating arithmetic and geometric means:  Given n nonnegative numbers c_1, ..., c_n,

   (1/n)(c_1+c_2 + ...+c_n)  >=  (c_1 c_2 ... c_n)^(1/n),

with equality if and only if all the c_i are equal. (This inequality played a role in one of our previous puzzles.)

If we choose the c_i to be the edge lengths x, y, and z, then we find

   E >= 3V^(1/3),

with equality if and only if the cuboid is a cube.

This inequality verifies our intuition that a cuboid can't enclose a given volume using arbitrarily little edge length. For example, there is no cuboid with a volume of a million cubic inches and an edge sum of 1 inch.

The inequality can also be written

   (E/3)^3 >= V

again with equality if and only if the cuboid is a cube.

The two forms of the inequality correspond to two optimal properties of the cube:  Of all cuboids with a given volume, the cube has the least edge sum; and of all cuboids with a given edge sum, the cube has greatest volume.

(Proof of the second property: Let C be a cuboid with edge sum E. Suppose K is any cuboid with edge sum E that is not a cube. Denote the volumes by V_C and V_K. Applying the inequality to K, we have (E/3)^3 > V_K. But of course, (E/3)^3 = V_C. Therefore V_C > V_K.)

Now take the c_i to be xy, yz, zx. This gives

   S >= 6V^(2/3)


again with equality if and only if the cuboid is a cube.


This again establishes something intuitively obvious, which is that a cuboid can't enclose a given volume using arbitrarily little surface area. For example, there is no cuboid with a volume of 1 cubic inch and a surface area of a millionth of an inch.

The inequality can also be written

   (S/6)^(3/2) >= V


again with equality if and only if the cuboid is a cube.


The two forms again correspond to two optimal properties of the cube:  Of all cuboids with a given volume, the cube has the least surface area; and of all cuboids with a given surface area, the cube has greatest volume.

The last two inequalities imply a third:

   ES >= 18V.

This can also be found by applying the inequality of arithmetic and geometric means, taking the c_i to be the nine expressions xyzxyzxyzx^2yxy^2, x^2zxz^2, y^2z, and yz^2.

For a cuboid with measures V, S, and E to exist, it is necessary but not sufficient that V, S, and E satisfy these simpler inequalities. For example, the numbers E = 8, S = 78, and V = 9 satisfy all of the "only-if" inequalities, although in fact there is no cuboid with these measures.

Another "only-if" inequality follows from applying the Cauchy-Schwarz inequality to the vectors (x, y, z) and (z, x, y). The result is (1/2)S <= x^2 + y^2 + z^2. But x^2 + y^2 + z^2 = E^2 - S, so we have

   S <= (2/3)E^2


again with equality if and only if the cuboid is a cube.


This inequality can be used to show two more properties of the cube:  Of all cuboids with a given surface area, the cube has the least edge sum; and of all cuboids with a given edge sum, the cube has greatest surface area.

***

By the way, we still need the if-and-only-if VSE inequality. None of the "only-if" inequalities is strong enough to rule out the existence of a cuboid with a volume of 80 cubic inches, a surface area of 122 square inches, and an edge sum of 16 inches (though in fact no such cuboid exists).

***

Proof sketch:

(1) Given that a cuboid exists with measures V, S, and E, to show that the polynomial p^3 - E p^2  + (S/2) p -has three positive roots. Idea: the positive roots are none other than the edge lengths.

Denote the cuboid's edge lengths by (positive) x, y, and z. Then since x + y + z = E, 2(xy + yz + zx = S, and xyz = V, the polynomial is p^3 - (x + y + z)p^2 + (xy + yz + zx)p - xyz. This however factors as (p-x)(p-y)(p-z), hence the polynomial has three positive roots.

(2) Given that the polynomial p^3 - E p^2  + (S/2) p -V has three positive roots, to show that a cuboid with measures V, S, and E exists. Idea: the edge lengths are none other than the positive roots.

Denote the positive roots by r1, r2, and r3. Since the polynomial is a monic cubic, the coefficients can be expressed in terms of the roots as symmetric functions, specifically as E = r1+r2+r3, S/2 = r1r2+r1r3+r2r3, and V = r1r2r3. But these functions are also the formulas for the measures of a cuboid. So create a cuboid with edge lengths r1, r2, and r3. The cuboid then has the desired measures.

(3) To arrive finally at the desired inequality.

It is obvious by inspection that every real root of  p^3 - E p^2  + (S/2) p -V  is positive. (Try substituting a negative number or zero for p.) Hence by (1) and (2), a cuboid exists having the specified measures if and only if the polynomial has three real roots. It now follows that the discriminant of the polynomial provides a necessary and sufficient condition for the existence of a cuboid with measures V, S, and E.

***

I would guess that some of this generalizes to higher dimensions. The kth coefficient of an nth-degree monic polynomial is going to be an elementary symmetric polynomial function of the roots...and meanwhile, the k-dimensional measure M_k of an n-dimensional cuboid is going to be the same elementary symmetric polynomial function of the edge lengths, multiplied by an overall combinatorial factor C_nk that depends on the dimension of the measure and the dimension of the space. So if we define the reduced measures of a cuboid by m_k = M_k/C_nk, then there will exist an n-dimensional cuboid with measures M_1, ..., M_n if and only if the polynomial


p^n - m_1 p^(n-1) + m_2 p^(n-2) - ... + m_n 

has n real roots.

Even supposing this principle does generalize, however, the discriminant for higher polynomials doesn't tell the real/complex nature of the roots in the simple way that it does for n = 2 and n = 3. So for n >= 4, I don't think the discriminant will give an immediately usable condition on the coefficients m_i.

***

Usual disclaimers...I assume everything here that is correct is well-known. There may be some interesting related readings out there - if anybody knows of good ones, please put them in the comments!

Friday, December 14, 2012

Curious Cuboids


A few more diversions from Insomnia's frozen shore

Recently I was thinking about rectangular parallelepipeds, also known as cuboids. A cuboid is a simple box shape. Think of a shoebox, a cube, or the black monolith in the film 2001: A Space Odyssey.

A cuboid has 12 edges with lengths x, x, x, x, y, y, y, y, z, z, z, z. By analogy to triangles, I call a cuboid scalene if x, y, and z are all distinct, isosceles otherwise. I further classify isosceles cuboids as being rod-shaped (x = y ≤ z), tile-shaped (x = ≥ z), or both (x = y = z; a cube).

Isosceles cuboid, rod-shaped
Isosceles cuboid, tile-shaped

To find the volume, multiply length times height times width. To find the surface area, compute the area of each of the six faces, then add them all up. For a linear measure, let's define the edge sum: length plus width plus height.

Below are some hopefully amusing questions about all of this. Also, I made a grainy animation that relates to all this. (It will make more sense after having thought about the questions below.)

Some of these questions can be settled with visualization, and some by simple arithmetic; others are less simple. One day I'll post some further observations on these matters...in the meantime, enjoy! And feel free to put any answers or thoughts in the comments.





Volume and Surface Area. The (6, 6, 6) cuboid is notable in that its volume is 6 × 6 × 6 = 216, and its surface area is (6 × 6) × 6 = 216.

1) Can you find another example of a cuboid with volume and surface area numerically equal when expressed in the same system of units? Is your example scalene, rod-shaped, or tile-shaped? Can you find an example of each?

Surface Area and Edge Sum. The (½, ½, ½) cuboid is notable in that its surface area is (½ × ½) × 6 = 3/2, and its edge sum is ½ + ½ + ½ =  3/2. 

2) Can you find another example of a cuboid with surface area and edge sum numerically equal when expressed in the same system of units? Is your example scalene, rod-shaped, or tile-shaped? Can you find an example of each?

Edge Sum and Volume. The (Sqrt[3], Sqrt[3], Sqrt[3]) cuboid is notable in that its edge sum is 3Sqrt[3], and its volume is 3Sqrt[3].

3) Can you find another example of a cuboid with edge sum and volume numerically equal when expressed in the same system of units? Is your example scalene, rod-shaped, or tile-shaped? Can you find an example of each?

In each case above, two measures were equal.

4) Are there any cuboids for which all three measures are numerically equal when expressed in the same system of units?


A few more existential questions...

5) Is there a cuboid with a volume of 1 cubic inch and a surface area of a million square inches?

6) How about a cuboid with a volume of 1 cubic inch and a surface area of a millionth of a square inch?

7) Is there a cuboid with a volume of a million cubic inches and an edge sum of 1 inch?

8) Is there a cuboid with volume 80 cubic inches, surface area 122 square inches, and edge sum 16 inches? 

Finally, some optimization problems. In each case, the desired maximizing/minimizing cuboids exist and have whole-number edge lengths.

9) Of all cuboids with surface area 48 square inches and edge sum 9 inches, which has greatest volume? Which has least volume?

10) Of all cuboids with volume 72 cubic inches and edge sum 14 inches, which has greatest surface area? Which has least surface area?

11) Of all cuboids with volume 162 cubic inches and surface area 234 inches, which has greatest edge sum? Which has least edge sum?


Sunday, August 5, 2012

Cents on the Dollar, Some Attempts

How much of a dollar bill can you cover up using change for a dollar? The coins must not overlap one another.

(See previous post and the one before that.)

I made a few attempts at this, see pictures below.

Version 1, wide-open. Here I covered the dollar bill with 45 pennies, going for a hexagonal lattice. I'm guessing this covered a percentage of the dollar in the mid- to high-80's. (One easily shows that an infinite hexagonal lattice covers a fraction Pi*Sqrt[3]/6, or a little less than 91%, so I'm assuming the below is pushing up against that limit.)




Version 2, intermediate. I nudged the configuration above in order to make room for the additional coins to touch the dollar bill - that seemed to force a decision to remove five of the pennies and replace the nickel with a dime.


I did some quickie image analysis on the above awful picture to give me some inputs for a Monte Carlo calculation of the covered area:



The result was just under 85% coverage. I didn't do a sensitivity analysis. I'm guessing this configuration is low- to mid-80's.

Version 3, tight. Here, my attempt uses 8 dimes, 15 pennies and a nickel. According to the spreadsheet, this configuration covers just over 64% of the dollar.



It would be nice to be able to replace that nickel with 5 pennies - according to the spreadsheet, that would bump the area up to 74.6%. But I wasn't seeing quite enough room to do that, and truth be told I have put a lot more time into blogging this puzzle than I've spent trying to solve it. Feel free to blow these attempts out of the water!

***

I thought of this puzzle after daydreaming the following exchange between a bank teller and an eccentric customer:

"May I help you?"
"I'd like change for a dollar."
"Here you go!" (Hands the customer four quarters.)
"Why, you cheat! I had 16 square inches' worth of currency and you gave me back only 3 square inches' worth!"
"I'm sorry, sir. Here are 7 dimes and 30 pennies instead."
"OK, close enough...."

I thought it was amusing, this image of a person valuing an exchange along a totally irrelevant dimension. As if one were to share a long kiss with somebody, and then become upset because the other person took a different number of breaths than you did.

***

The above puzzle takes the form, "How many X can you cover with Y?" I'm sure there a lot of problems and solutions of this nature to be found in the literature on circle-packing. I don't know that literature, but a quick search just now turned up some neat pictures here.

Thursday, August 2, 2012

Cents on the Dollar, Ctd


How much of a dollar bill can you cover up using change for a dollar? The coins must not overlap one another.

Yesterday I played the game three times, under three different conditions:
Version 1: Wide-open. In this version, you don't have to use all the coins. Equivalently, we might characterize things by saying that while you do have to place all of the coins adding to $1.00 on the table, not all of the coins on the table have to touch the dollar bill. Also, those coins that do touch the bill are allowed to protrude beyond its edges.
Version 2: Intermediate. All of the coins adding to $1.00 have to touch the bill. Coins are allowed to protrude beyond the edges.
Version 3: Tight. All of the coins adding to $1.00 have to lie within the boundary of the bill. 
(The spreadsheet is appropriate for scoring attempts that meet the constraint in Version 3.)

On Monday I'll post a picture of my attempt at each version.

Tuesday, July 31, 2012

Cents on the Dollar


How much of a dollar bill can you cover up using change for a dollar? The coins must not overlap one another.

A not-very-good effort is pictured below. The four quarters only cover about 18% of the dollar bill's area.


Send me a picture of your best effort!


N.B., I made a spreadsheet that you can use to score your attempts. Edit the blue values in the spreadsheet to reflect how many coins of each type you used. Please don't edit the formulas, or others won't be able to use the spreadsheet. (Let me know if there are errors.)

J


Tuesday, June 5, 2012

Incurable Romantic

With my wedding anniversary coming up, I consulted some of those lists of traditional gifts. We're not at the gold or silver level yet, so I see there's the bronze anniversary, the paper anniversary, the leather anniversary (sounds spicy!), even the salt anniversary. (Sort of spicy, too, I suppose.) Today I was doodling on the computer, so apparently this year is the computer graphics anniversary.


video

Higher-resolution file here (.wmv file, 13.5MB).

To make this shape, I took forty-one circles of latitude on a sphere and replaced each one with a heart. The scale factors of the hearts are the same as the scale factors of the corresponding circles of latitude. In that sense, the shape is an example of a generalization of the sphere, in which a stack of similar circles is replaced by a stack of other similar shapes. (My wife and I were talking about this subject the other day.)

The parametric equation of a heart is from this page. Some other nice heart ideas are here.

(Don't worry, honey, I also bought you a non-mathematical present!)

Saturday, April 21, 2012

Triple Double Revisited

I haven't had many solutions to the Triple Double, so I'll put a more fun(?) version of the puzzle here.

In this form, it's the kind of thing where you can do some of them during a quick coffee break.


In each of the following cases, rearrange the letters to form a word.

(Note, a number of these words are hyphenated.)


AACCHH

AACCNN

AAEEYY

AALLPP

AARRTT

BBNNOO

CCHHII

DDDEEE

DDEERR

EEHHSS

EESSTT

EESSTT

EESSTT

KKTTUU

MMRRUU

AAEEPPRR

AAEEPPSS

AAEEMMTT

BBEEIIRR

CCOOSSUU

GGIINNSS

AAAHHHCCC

AAGGIINNRR

EEIINNSSTT