mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2006-11-28, 21:11   #1
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default How many balls in a box?

This may be quite easy for you:

How many balls of uniform size can fit in a box?

You can assume the box is transparent and you can see through the perspex sides.

Can you determine an upper bound for the number of balls in the box?

Clearly three balls could be arranged in a triangle, then a fourth ball can be added to that giving a pyramid shape. Adding more balls packed as closely as possible will result in a honeycomb like 3D matrix (does this have a name?)

Anyway assuming this maximum packing density, can you express the maximum number of balls in terms of the dimensions of the box in multiples of ball diameter?

You can assume the box has rightangled corners, so is a cube or can have rectangular sides, and/or rectangular base.

If a box dimension is a relatively small multiple of ball diameter, there will be edge effects reducing the optimum ball packing, but I'm after an expression for fairly large (limit as dimension tends to infinity balls) in terms of packing efficiency, because the number in a real box must be less that that upper bound.

If you wish to visualise this, think tennis balls (but you can't deform them by compression).

So how many balls can fit in the box?

I want to be able to look at a box, estimate it's dimensions in multiples of ball radius, and from that calculate the maximum balls that could be in the box.

If you are good you could further add in a term for what happens when the box dimensions are not precise multiple dimensions of the diameter.

I think a minimum number of balls (in a so-called "full" box, or filled to a given height z which may be treated as a z height box) could be the non-hexagonal arrangement of simply stacking balls adjacent upwards and downwards ie balls = x*y*z. But the optimum packing with offsets (2D and 3D) should allow more?

I could not find treatment of this problem using google but it is likely fairly common in application like fruit packing.

Last fiddled with by Peter Nelson on 2006-11-28 at 21:30
Peter Nelson is offline   Reply With Quote
Old 2006-11-28, 21:21   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

32×1,303 Posts
Default

Google "Kepler sphere packing problem".
ewmayer is offline   Reply With Quote
Old 2006-11-28, 21:33   #3
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

Thankyou Ernst I'm finding some good info now, including the correct terminology for my arrangement "face-centered cubic packing" ;-)

This longstanding conjecture appears solved in 1998. Very interesting that this problem is nontrivial and took such a long time, but the proof is long!

Spoiler:

http://en.wikipedia.org/wiki/Sphere_packing

contains a formula I was looking for in terms of optimum density achieved ;-)

It also develops the problem further for n-dimensional scenarios using hyperspheres.

But I'm still working on the "how many balls"

The density can apparently vary from min 52.4% for a regular square matrix, up to maximum 74.048% achieved by the optimal arrangement.

So I can calculate the volume of my box, take 75% of that as the filled space, then divide by the volume of each sphere to obtain how many spheres are making up that volume!

But that takes a division.

I'd really like an expression for ball quantity in terms of ball diameter units ;-)

Last fiddled with by Peter Nelson on 2006-11-28 at 22:30
Peter Nelson is offline   Reply With Quote
Old 2006-11-28, 22:39   #4
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

10000100012 Posts
Default

Interesting Trivia for ellipsoids (non spherical):

"Donev et al. (2004) showed that a maximally random jammed state of M&Ms chocolate candies has a packing density of about 68%, or 4% greater than spheres. Furthermore, Donev et al. (2004) also showed by computer simulations other ellipsoid packings resulted in random packing densities approaching that of the densest sphere packings, i.e., filling nearly 74% of space. "

from Wolfram Mathworld

Can it be implied from this that if my spherical balls were put into my box randomly (not arranged in a uniform lattice), they would achieve a typical density of 64%? (apparently sourced from Jaeger and Nagel (1992)) And how many balls will THAT be?

I was wondering if there is a difference between "random" as in balls modelled together in free space and my scenario, where the constraining sides of the box will help arrange the balls as it is gradually filled eg the first layer will have to be flat because the box base is, and the balls in next will only tend to rest in the gaps of the first layer. So maybe the randomly filled box is not as low as a random clump of balls in a model?

Well argued here:

http://news.bbc.co.uk/1/hi/sci/tech/670429.stm

Last fiddled with by Peter Nelson on 2006-11-28 at 23:16
Peter Nelson is offline   Reply With Quote
Old 2006-11-28, 22:57   #5
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

On my original question about the number of balls in terms of diameter, I am thinking this may be a good estimate:

Calculate volume of box in terms of diameter units.

For max balls achievable in optimal lattice configuration,

divide by 52.4% (sphere proportion of unit cube) and multiply by 74.048%, ie multiply by about 1.5 (or simply add 50%)

for random arrangement it's add 22% to the box volume.
Peter Nelson is offline   Reply With Quote
Old 2006-11-29, 00:22   #6
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

This thread is the most relevant to my particular question.

http://mathforum.org/library/drmath/view/55181.html

Eventually they get the same results as me (allowing for rounding), just using a different method.

(I go back to box side dimensions and thus box volume in terms of ball diameter units)

However my method is quite quick to calculate and gives me the figures I was after for both an upper bound and "randomly packed" average of balls in the box. Where a box dimension is not a large multiple of diameter, I will take a bit off the result to compensate for edge effects.

Last fiddled with by Peter Nelson on 2006-11-29 at 00:26
Peter Nelson is offline   Reply With Quote
Old 2006-11-29, 03:19   #7
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

21116 Posts
Default

Now I will explain my reason for asking.....

I have already entered and been sucessful in a competition where we had to estimate the total number of balls in a car, which changed each week over 4 weeks.

I am now one of 41 qualifiers who progress to the next stage of the competition. Not all 41 may turn up so my odds may be even better.

Next we have to whittle that number down to 5 of us, by a similar object counting task. I don't know what the objects will be but they could well be balls again so I thought I should at least know the mathematics behind it.

If I can be one of the 5 closest guesses I'm one of the people going forward to the final:

Then we have to putt a golf ball into a hole (none of us are professional golfers). The one who gets it in (or even closest) wins the car.

The best player also qualifies to try to putt a hole in one to win a million dollars!

Having got this far I bought a golf club and balls and have been practicing on the carpet. Assuming I can be one of the 5 of <=41 people counting objects, then I have a 1 in 5 chance of the car. There may be other prizes too ;-)
Peter Nelson is offline   Reply With Quote
Old 2006-11-29, 07:31   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

Quote:
Originally Posted by Peter Nelson View Post
If I can be one of the 5 closest guesses I'm one of the people going forward to the final.
So you are basically asking us to help you with your homework problem, right?

It seems that your knowledge of maths gives you an unfair advantage. On the other hand, your investment in golf equipment might just possibly be a smart investment. Good luck and keep practicing those putts!
philmoore is offline   Reply With Quote
Old 2006-12-08, 13:19   #9
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

232 Posts
Default

It was an achievement to be in the qualifiers because there were over 12,000 entries to the competition.

Well I became quite proficient at estimating balls in a box with the help of MersenneForum ;-)

And my golf putting improved a little with the help of our cat watching ;-)

And so it came to the night of the final.

We had a good night out, with a free meal for finalists (wine too but that would not have helped accuracy much so I stuck with orange juice), then was the object estimation task:

Unfortunately we had to guess the balls in the car rather than a cube.

This was somewhat harder as there is seating and other irregular shapes to consider.

Unfortunately my answer was a little low by about one row of balls across the car. The actual answer should have been about 3500 balls.

Of the five qualifying finalists, none of them had EVER played ANY golf at all.

At least I could then relax and watch.

They each putted, of which 3 of the five balls left the green altogether.

It was not so easy since the green carpet had plastic tubing placed underneath to create a small hill which could deflect balls.

Two balls stayed on the green and the nearest guy called Mark got within only 9 inches from the hole and he won the car!!!

Since the car was full of balls we had to unload all 3500 of them for him to take the car away. We filled bags to take them away for use with schools, kids clubs, or personal use so nobody went away empty handed.

Mark also got his chance to putt a shorter distance for the million dollars. Unfortunately, he missed the hole :-(

Anyway, although I didn't win anything except the meal and free balls, I have learnt more about maths, and you never know it may come in handy one day if there is a similar competition.

Last fiddled with by Peter Nelson on 2006-12-08 at 13:24
Peter Nelson is offline   Reply With Quote
Old 2007-01-09, 17:00   #10
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Lightbulb Keplers conjecture


Peter Nelson:
Thank you for bringing up this sphere packing problem Peter, which was formerly known as ‘piles of shot’. Also thanks to ewmayer for directing us to the appropriate URL.

It originated as a practical problem on warships when it was necessary to know the number of shot left in an incomplete square base pyramid arrangement of shot.

History documents that Sir Walter Raleigh on his warships realized the need and posed the problem to which math’cian Thomas Harriot gave the solution.

I was not aware that in this problem to determine the max. amount of balls it was convenient to consider the density of packing rather than the actual arrangement – a very remarkable solution.

It is also not well known that after 400 years of Kepler’s conjecture it was finally laid to rest, as late as 1998 by Thomas Hales of the Univ. of Michigan.

It is also very surprising that what food packers have known by intuition ages ago works out to be the best arrangement like a pile of oranges in any fruit vendor's stall.

Since you have studied the problem in depth I give below the corresponding basic formulae for the different arrangements in different configurations.

EQUILATERAL TRIANGLE.:

S = n(n+1) (n+2) /6 ……… (1)

FOR SQUARE:

S = n (n+1)(2n +1)/6…………(2)

RECTANGLE: If m and n be the number of Shot in the long and short side in the base

S = n(n+1)(3m – n +1)/6……..(3)

INCOMPLETE Rectangular base pyramid:

Let a+b be the number in the two sides of the top layer and n the number of layers

S = n/6{6ab + 3(a+b)(n-1) + (n-1)(2n-1 } …….. (4)

In numerical problems it s easier and straight forward to use formula (1) twice viz:
a) the full pyramid.
b) minus the missing pyramid rather than formula (4)

RGDS,
Mally

Last fiddled with by mfgoode on 2007-01-09 at 17:02
mfgoode is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 23:39.


Fri May 20 23:39:21 UTC 2022 up 36 days, 21:40, 0 users, load averages: 1.15, 1.35, 1.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔