Here is an interesting question for you mathematicians out there!

"What is the maximum number of one inch-diametre spheres that can be
packed into a box ten inches square and five inches deep?"

Just to clarify the spheres cannot be melted down or anything.  And
you answer MUST be proven mathematically!  Good luck!

---

Request for Question Clarification by koz-ga on 06 Dec 2002 09:05 PST

After reading the 4 comments so far, I'm curious.  If you know the
answer already (by telling darrenw that his answer is incorrect), why
are you bidding $5.00 for an answer?

I'll point any researcher that wants to take the time to construct a
full answer to

http://www.maa.org/devlin/devlin_9_98.html 

and 

http://www.math.pitt.edu/~thales/kepler98/ 

to describe Kepler's answer to Sphere Packing problem (circa 1611 A.D)
and the subsequent research that has taken place.  A proof of Kepler
was finally been done by Thomas Hales of the University of Michigan in
1988 (he's now at Pitt).  Another nice page with pictures is at

http://www.tiem.utk.edu/~gross/bioed/webmodules/spherepacking.htm

---

Request for Question Clarification by tox-ga on 07 Dec 2002 10:14 PST

Divet-ga
I recognize all your problems identical to the ones from "Test For
Exceptional Intelligence" created by the International High IQ
Society.  This contest is also known as the Smartest Person in the
World Contest where the prize is 500 US dollars and recognition.
(information found here
http://www.highiqsociety.org/common/smartest.htm)
I do have the answers to your questions but I am hesitating to answer
because I am not sure on your purpose behind these questions.  If you
are planning on submitting the answers you receive as your own to the
Society and participate in the contest, then that would be considered
cheating as the rules state that "The use of reference materials,
books, calculators, and computers is permitted" but the problems must
be solved individually without collaboration (stated by the Society
representative).
However, if you are genuinely curious then I hope you don't mind
waiting until the competition is over.  Answers must be submitted by
the deadline December 31, 2002 and so since this question expires on
January 3, 2003, I will answer them on January 1.
I will assume you are not a participant since you have already stated
that you proposed the questions to your professors.  However, this
delay is to keep the contest fair to everyone since even if you have
honest intentions, others who visit Google Answers may be tempted to
use the answers and participate in the contest.
I myself am not participating in the contest as I solved the problems
(23 out of 25) with a colleague.  However, I can assure you that they
are all correct and your wait till January 1st will be worth it.

---

Clarification of Question by divet-ga on 07 Dec 2002 11:57 PST

Hello tox-ga,

Thanks for your interest in my questions.  To respond to your remark I
would like to say my listings are for my general interest.  A colluege
of mine directed me to the site 2 weeks ago.  Since then I alone have
been able to solve 24 of the 25 questions (The 25th question is being
solved by my computer as we speak).  There is no need for me to steal
answers or cheat in order to win the competition.  I actually wasn't
even aware of that cash prize to be honest.  I have nothing to prove
by this test.  How is it advantageous to me to divulge answers to
questions that other competitors could use?

I posted these questions since they (I found) were either the most
difficult or the most interesting.  I have the solutions to all of the
questions I posted.  So it is not a matter of cheating.  I will gladly
go over any solution and show why it is incorrect.  Only someone with
the proper solution could do that.

I only wish to see the logic other people used.  I am currently
building a website that will allow people all over the world to
collaborate and work on research projects.  It is a non-profit
organization built simply out of the love of human knowledge and
discovery.  If this is interesting to anyone please leave a comment to
learn more.

tox-ga if you would like to talk further through email let me know.  I
believe we could have an interesting dicussion.

Thanks,
Divet-ga

If each sphere is one inch in diametre then the size each sphere takes
will be one inch square. I know there is some space left outside in
the corners but I'll get to that in a second.

Therefore if each sphere is 1x1x1 inch then:

10 x 10 spheres can fit on the bottom of the box = 100 spheres
and there are 5 layers of spheres = 100 x 5 = 500 spheres.

Now with the extra space between each sphere.
If the bottom layer of the box contains 100 spheres, then the layer on
top will
also hold 100 spheres but each sphere will be moved 1/2 inch across in
width and 1/2 inch in length. This will mean that although you have
saved a little bit of space in the height, you only have 9x9 spheres
on the second layer. Of course if you cut the spheres in half you can
have half a sphere on the sides on the second layer and still achieve
100 spheres per layer.

I hope the above is correct.

The first thought I had was that it looked like an fcc, bcc molecular
packing type problem. But I realized that spheres had to be whole.

So here goes:
1) Spheres can be packed between layers, and the height contribution
can be geometrically determined. An example:

Hello there, thanks for your interest in my puzzle.  I am sorry but an
answer of 500 is not the correct answer.  The question is not as
straight forward as one would believe.  You must think about
alternative ways of arranging each layer of spheres.  Like you said
there are gaps between the spheres.  There is a way to minimize this
wasted space.

Hint: Perhaps a different arrangement of spheres on the base layer
could allow more to be packed.  Sphere packing is a huge area of
research in mathematics.  Looks it up for the latest techniques.

Whoops! Accidentaly clicked on post...

Anyway:

   OO
    O
   OO

assuming the middle circle lies in between the two. A triangle
connecting the centers of three circles (the top left one, middle one,
and the bottom left one). By geometry (using the sine rule or cosine
rule - quite simple, I shall spare you the working), the height
contribution, h by the middle circle can be calculated. h = sqrt(3) -
1 = 0.73

We know that the height of the box is 5 inches.
The height, H of a full sphere is 0.5 inch.
The height, h of a middle sphere contribution is 0.73 inch.

Let the number of full spheres stacked heightwise be x.
Let the number of middle sphere contribution stacked heightwise be y.

Lagrangian constraint (the sum of the heights must be less than 5):
0.5x + 0.73y =< 5

Let n = x + y 

Using Lagrangian multipliers, a solution can be found, such that n is
maximized. However, since I needed another constraint (x = y + 1 or x
= y - 1), I skipped the whole thing and used my calculator instead. I
came up with x = 4 and y = 4.

Knowing that for a sphere grid of size g x g, or g^2, the layer on top
must be (g - 1)^2. So for a 10^2 sphere grid, the layer on top must
have 9^2 spheres, or 81 spheres.

Therefore, the total number of spheres, N = 100x + 81y = 100(4) +
81(4) = 724.

Sorry for the sloppy math... it's 12:22 a.m. here on the east coast. I
hope I didn't make any egregious errors.

zhiwenchong-ga,

I am sorry but your answer of 724 is not correct.  If the spheres are
placed uniformily into the box (5 rows of 100 spheres each) then 500
spheres can fit.  There is a way to arrange the spheres however such
that the spaces between them are minimized.  You are claiming that the
box could hold 224 more spheres than if packed uniformily. 
Mathematical intuition tells us that your solution would be
impossible.

Please try again.

not to try and take part in this open discussion (for reasons stated
by tox-ga) but to give a hint to all the honorable math fans, a very
similar question (identical except for the dimensions) is available on
a past solution (can be found on the net) of a very popular canadian
national math contest.

Researchers may want to view question ID 119400 before attempting to
answer the question.
https://answers.google.com/answers/main?cmd=threadview&id=119400

Hi, divet-ga and others on this thread:

Some "obvious" comments.

Earlier this year Prof. Thomas Hales posted his "second generation"
proof of the Kepler conjecture:

http://www.math.pitt.edu/~thales/PUBLICATIONS/spherepacking3.pdf

Since the container here is "tilable", we immediately have the upper
bound on density of pi/sqrt(18), which means the number N of spheres
satisfies:

N * (pi/6) <= (pi/sqrt(18)) * 500

because the volume of each sphere (of radius 1/2) is pi/6, and the
volume of the container is 500.  That is:

N <= sqrt(2) * 500 = 707.1...

An easy lower bound of 500 has been given by darrenw-ga, but as
divet-ga points out this is not sharp.  Considerable effort will no
doubt be required to close the gap between these upper (707) and lower
(500) bounds and find the exact optimum number of spheres.

regards, mathtalk-ga

mathtalk-ga,

Very good start mathtalk-ga.  It is a wise idea when dealing with a
problem of this magnitude to set upper and lower bounds as to what the
solution could be and then narrow it from there.

Without much knowledge of math one can determine a primitive boundry
to the solution set.  We know through simple logic that 500 spheres
can fit into the box.  This is a simple proof (see darrenw-ga's
comment).  The upper-bound can be found by allowing the spheres to be
"melted".  This eliminates all gaps between resting spheres.  Thus,
the volume of the box divided by the volume of a sphere will produce
the number of melted spheres that can fit into the box.  This
calculation yields 954 spheres.  Thus if we let S be the solution set
then

S = { x is an element of N: 500 =< x < 954}

This is a basic limitation, I know, but is one that can be constructed
by primitive mathematics.

As mentioned Kepler stated that the optimum packing strategy will
produce about a 74% packing ratio.  If we apply this to 954 we get 705
spheres.

So once again we have narrowed the solution set without any packing
strategy!

S = { x is an element of N: 500 <= x <= 705}

Obviously, since 500 spheres is packed fairly tight and the 74%
packing efficiency is based on CUBIC packings then we know that the
upperbound is significantly lower than 705.

Once again we have narrowed our search.  So now it is up to a rigorous
proof to find the correct answer.  That task I leave to you.

Good Luck and have fun!

Divet-ga

My mistake, I misread the question. H = 1, not 0.5. But my solution
was wrong anyway, because my basic premise was wrong. The packing I
chose was not the tightest. After some research into fcc and hexagonal
type packings (planar and 3D), I have some idea what the correct
solution might be, but I won't continue.

These papers deal with a similar problem. They might be useful to some
people.

Goldberg, M. "On the Densest Packing of Equal Spheres in a Cube."
Math. Mag. 44, 199-208, 1971.

Schaer, J. "On the Densest Packing of Spheres in a Cube." Can. Math.
Bul. 9, 265-270, 1966.

Friedman, E. "Spheres in Cubes."
http://www.stetson.edu/~efriedma/sphincub/.

For anyone who wants to continue...

Remember the links people are posting mostly deal with packing spheres
into cubes.  We are dealing with a rectangular box.  Your calculations
will have to be adjusted accordingly.

::Divet-ga::