43

A grocery store has a long, skinny box, with no top, that it uses to display soda. The box is two soda cans wide and 200 soda cans long. You can neatly fit 400 cans in this box, using two rows of 200, as shown below.

enter image description here

Show how to fit $401$ soda cans into this box (with their bases resting flat on the floor of the box).

There is no lateral thinking involved in this solution. You can think of this as a purely geometric, two dimensional problem, where you are trying to fit $401$ circles of diameter $1$ into a $2\times200$ rectangle.

mmking
  • 3,136
  • 2
  • 18
  • 43
Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • 4
    This tool http://www.engineeringtoolbox.com/circles-within-rectangle-d_1905.html says that for (200,2,1) the maximum is 400. I don't trust it, though! – leoll2 May 19 '15 at 20:12
  • 2
    @leoll2 I was looking at that same link. Did you read the note at the bottom? It says that it can't always give the optimal packing. – Rob Watts May 19 '15 at 20:20
  • 1
    I assume we aren't allowed to dive into the third dimension for this question, eh? – Bailey M May 19 '15 at 20:43
  • @BaileyM Why restrict yourself to only 3. Why not 4 or 5? :p – Mark N May 19 '15 at 20:48
  • soda can width: 2.6", so 2.6 x 200 = 520". School buses measure up to 45' = 540". Anyone wanna help me load it? – JLee May 20 '15 at 02:20
  • 1
    Two answers. 1. Empty all 401 soda cans and crush them. 2. Since the box has no top, define "in the box" to mean "anywhere vertically above the bottom of the box" and then place the 401 can on top of the other 400. – Ian MacDonald May 20 '15 at 04:52
  • open the extra can and just pour it in :) – Ewan May 20 '15 at 11:16
  • 20
    Really tempted to post an answer of the pic in the OP, with the text altered to say "395 more cans". – rybo111 May 20 '15 at 13:04
  • 1
    Soda cans are malleable aluminum. I'm certain that Chuck Norris could fit 401 cans in that box without resorting to clever geometrical trickery. – dotancohen May 21 '15 at 07:40
  • @Mike, Why not ask how one can fit 335 cans in a box of 167x2 can-diameters? There's an optimal packing for that. – user4651 May 23 '15 at 09:40

7 Answers7

43

EDIT: The description is not very intuitive, so I took the liberty of creating an image to make clear what this solution intents.

enter image description here

We're going to make a repeating pattern of six cans. The pattern will have three cans in the top row and three cans in the bottom row. They will be "offset" by .5 units, and each row will have width a little bit less than 3 units.

The details:

I'm going to give the coordinates of the centers of the cans... the centers have to be in a 1-by-199 box, since they can't be within one unit of the edge, and no two centers can be within one unit of each other.

And:

Here's the repeating pattern: The coordinates of the three points in the bottom row will be (0, 0), (1, 0), (1.992 , .13). It will repeat again, offset by 2.984 units, so: (2.984, 0), (3.984, 0), (4.976, .13). And so forth.

And:

In the top row the first three points will have coordinates (.5, .87), (1.492, 1), (2.492, 1). Then the next three it repeats: (3.484, .87), (4.476, 1), (5.476, 1), etc.

Now before I check that my solution works let me give some intuition:

There are two rows of cans. I "offset" the cans by half a unit: so if the bottom cans (center points) have x-coordinates 1, 2, 3, then the top cans are centered at 1.5, 2.5, 3.5. Now that gives me some "wiggle room" which I can use to move some of the cans up and down a little bit. Moving some cans up and down means I can make them take up ever-so-slightly less horizontal space -- I can compress a row horizontally. Now if I only compress one row but not the other I can't maintain the .5-unit offset. So I compress the two rows in turns. That's how the pattern works.

It turns out it's just enough to get the compression we need:

First you can check that the points I put are all 1 unit apart. In the bottom row you just check that .992^2 + .13^2 > 1, which it is. The top row is the same by symmetry. Between the bottom row and the top row, the key calculation is .5^2 + .87^2 > 1, which is also true.

And then you count the total space:

Let's say there are 201 cans in the bottom row, so you have to have 200 intervals. How much space will those take up? Well, every 3 cans take 2.984 units, so you save .016 units every three cans, or a total of 1.072, which is just good enough!

mathlander
  • 1,231
  • 1
  • 8
  • 31
Brian
  • 861
  • 6
  • 10
  • 5
    Welcome to Puzzling SE! It's refreshing to see a new user who understands how to use the system on their first go (a sign you actually read the rules). Good on you and keep it up. – Elias Benevedes May 20 '15 at 13:26
  • Well done! For those who want an illustration, see user4651's answer. – Mike Earnest May 20 '15 at 17:42
  • I wonder what would be the smallest even number of circles for which 2N circles could fit in a width less than N by any amount? – supercat May 20 '15 at 22:11
  • 2
    I added an edit with a clearer (imo) visualization to this solution. – M.Herzkamp May 21 '15 at 09:03
  • @M.Herzkamp, so did I. But thanks for putting one here. :) – user4651 May 22 '15 at 08:59
  • @supercat, 170x2 diameters would fit 341 circles. 169x2 would fit 339. 87x2 would only fit 174 using this packing that Brian, Mike, and I figured out (independently), and 174 using a normal rectangular packing. So the answer is 169, for any box of width 2 diameters and arbitrary length, unless there is a tighter packing. – user4651 May 22 '15 at 09:33
  • 1
    @supercat: math mistake. 168x2 would fit 337. – user4651 May 22 '15 at 10:07
  • 1
    @supercat: 251x2 will fit 504 - the smallest one where 2n fit in '2 by n-1'. You were looking for any amount, so 168x2 will do. Also 2x86 will fit 172, and 2x85 will fit 170, so the 'extra space' saved using this packing needs to be at least 1 diameter for this packing to fit more. 1-4 circles can be removed from triangles on the right or left side, just remove half as many diameters from the box length. You still get the added bonus. – user4651 May 22 '15 at 11:17
  • Here's an algorithm. Pick an integer greater than 1, call it P. Divide half of P by this: $1-\sqrt{1-\sqrt{\frac{3}{4}}^2}. Round down to an integer, and add 2. Multiply by 3 and call it D. If D is odd, add 1. Divide by 2. The result is G. Your box is G by 2 Can-diameters. You can fit P + (G)(2) cans in the box. If the math is wrong, that's what I get for doing math this late in the morning. -- aand apparently I can't LaTeX. – user4651 May 22 '15 at 12:11
  • @user4651: I think 168 balls in a space 83.996x2 using whole groups of six circles, and it should be possible to eliminate four balls from that group so as to fit 160 in 79.996x2, but 158 using any variant on this packing other than straight rectangular would require more than 79x2? I wonder if any other packing could fit 158 in a space strictly smaller than 79x2 [smaller per-repetition bonus, but smaller fixed cost]? – supercat May 22 '15 at 15:52
  • @supercat: 168 would need 2x~84.00416. 164 would need ~82.00416. let T represent number of cans, a multiple of 3. $1-\sqrt{1-\sqrt{\frac{3}{4}}^2}$ * (T/3-1) is how much space you are saving. (T+1)/2 is how much length the cans would take in a hexagonal packing, wasting space on top. edit: still can't latex. maybe a mod can help me out? – user4651 May 23 '15 at 09:16
12

Here is a CAD drawing I created to show the layout:

drawing Using trigonometry and the facts that all the magenta lines and height of the rhombus are unit length, we can find that the center of the yellow circle is at x-coordinate 1.495. We can then create a function for distance required to store n number of cans on the bottom row: F(n) = 1 + 0.995 * (n - 1) for n >= 1 so F(201) = 200 , meaning we can fit 201 cans on the bottom row, and one less on the top, for 401 total.

clcto
  • 229
  • 1
  • 4
  • 3
    In your $F(n)$ expression, the $0.995$ number should actually be $\approx$ 0.99578, so that $F(201)>200$. – Mike Earnest May 20 '15 at 04:10
  • Maybe try to take it one step further. Instead of repeating 4, try to attach a fifth one, and then repeat that, except each time you must flip-flop it. I love puzzles like this, but it's nearly impossible to play around with configurations in a hands-on way. If that were easier, then it would be even better. – JLee May 20 '15 at 13:13
8

Here's the MSPaint to the rescue answer. The math logic works in my head as well. The top packing is tighter.

each triangle after the 1st one saves (edit: $1-\sqrt{{{1-(1-\sqrt{\frac{3}{4}}}}})^2$ ) ~0.00901523343248242768377221117738 diameters. Multiply by 132 and get 1.190010813087680454257931875414. The first triangle is on the bottom left. The 133rd is also on the bottom, leaving space for 1 on top of another packed into the right edge. QED

edit fixed picture link image

the math:

looks like i failed, unless my math is off my a factor of 2, it fits 402.enter image description here 1.0+2.0*pow(1.0*1.0*pow((1.0-pow(1.0*1.0-0.5*0.5,0.5)),2.0),0.5)/6.0 simplified math: sqrt( 1 - ( sqr( 1 - sqrt( .75 ) ) ) / 3.0 is the ratio.

< correct math below

strikethrough the previous text. 1st commenter clarified the math, it's 1 - sqrt( 1 - ( sqr( 1 - sqrt( .75 ) ) ) saved for each triangle after the first one. 133 triangles leaves 132 * ( 1 - sqrt( 1 - ( sqr( 1 - sqrt( .75 ) ) ) ) extra space on the end.

user4651
  • 81
  • 4
  • 3
    I was literally just about to post basically the same solution. Mathematically, you can show that each triangle starts $x=\frac{1+\sqrt{4\sqrt{3}-3}}2\approx 1.490985$ to the right of the previous triangle, and obviously each triangle is length 2 along the box and contains three cans. With 133 such triangles, we would have 399 cans. The rightmost edge of the 399th can is at $132x+2 \approx 198.81$, and thus there is enough room for one can directly next to it on the same edge, and then you can place the 401st can in the remaining space on the other edge. – Glen O May 20 '15 at 07:45
  • Good math. I don't know latex or whatever you used to do that math, but I'm confident that the Pythagoras I used is correct. Also I was rushing to get it typed up because I knew someone was working on it as I typed and MSPainted. – user4651 May 20 '15 at 07:52
  • You can't quite fit 402, by the way - to do so, you'd need one more triangle on the end, so basically you'd need the right edge to match the left edge and to have 134 triangles. But 134 triangles will require about 200.3 can-widths (that is, $133x+2$), just a little too much. – Glen O May 20 '15 at 08:07
  • @GlenO, Alternatively, each triangle after the 1st one saves ~0.00901523343248242768377221117738 diameters. Multiply by 132 and get 1.190010813087680454257931875414. The first triangle is on the bottom left. The 133rd is also on the bottom, leaving space for 1 on top of another packed into the right edge. – user4651 May 20 '15 at 08:12
  • 402 would work if space repeated itself at the end of the box, but you're right. If space repeated, one of the triangles would have to be replaced by a 3-on-the-bottom, 2-on-the-top group. – user4651 May 20 '15 at 08:22
  • This solution is identical to the accepted answer, so also correct! I arbitrarily chose Brian's because he answered first. – Mike Earnest May 20 '15 at 17:40
  • Thanks for the drawing! Much clearer. And yes this is exactly what I had in mind. – Brian May 21 '15 at 06:10
  • @Brian, You got it first, and thanks. – user4651 May 22 '15 at 08:58
5

Okay, here's a badly-drawn way to do it:

Start by taking four cans and lining them up in a diamond. Then, tilt that diamond until it touches the top of the box:
Badlydrawn
Now repeat with four cans at a time, each making a diamond, and push that diamond as far to the left as it will go. The first diamond uses $1 +\sqrt{2}$, or about $2.414$, diameters, but each additional diamond only adds about $1.99156$ diameters. So after $100$ diamonds of $4$ cans each, you end up with enough extra space at the bottom right to fit an extra can.

Dan Staley
  • 223
  • 1
  • 5
  • 1
    Perhaps I'm mistaken, but doesn't your arrangement of $401$ cans take up $0.5+100\cdot 1.99156+0.5$ diameters horizontally, which is more than 200? The $1.99156$ is the distance between two cans which touch the south wall, of which there are $100$ such gaps, and the $0.5$ at either end accounts for the halves of the cans on the end which touch the east and west walls. – Mike Earnest May 20 '15 at 00:55
  • ^I mean $1.99156$ is the distance between the centers of two cans which touch the south wall – Mike Earnest May 20 '15 at 02:37
  • What if you use a "diamond" of six cans? Eight? 400? – Random832 May 20 '15 at 03:32
  • 1
    @Random832: Less "tilt" = "less horizontal gain" – BmyGuest May 20 '15 at 07:36
4

Playing around in paint (400 height, 100 radii circles), I made a slight stagger.

enter image description here

The width of the three circles on top is less than if they were directly side by side, so this trapezoid can be flipped and repeated.

Quark
  • 6,077
  • 1
  • 20
  • 46
  • The point when you have staggered enough to add another circle is when you have moved over to the left by 1 diameter. In other words, when you get back to where you started. – user3294068 May 19 '15 at 20:07
  • I'm not sure what I was thinking, I think I just looped back on my original thoughts. Going to edit the picture. – Quark May 19 '15 at 20:08
  • @leoll2 I edited the picture and specified the difference between this answer and Mark's. – Quark May 19 '15 at 20:17
  • This looks promising, but I 'm not convinced that this will actually save enough space to fit in an extra two cans (Mark's configuration will only fit 399 cans). – Rob Watts May 19 '15 at 20:30
  • If you press in on the rightmost one, the two at the bottom spread out, the middle one goes down an the one you are pressing on moves in. Eventually, you get to leoll2's answer. – user3294068 May 19 '15 at 20:32
  • This method needs to calculate to saving 1/20th of a can (or 5%) for each 5 cans used in order to be able to add 2 cans. – Mark N May 19 '15 at 20:34
1

Perhaps a configuration like this?

enter image description here

I haven't done the math yet, so not sure if it actually works.

Community
  • 1
leoll2
  • 12,590
  • 3
  • 39
  • 83
  • Draw a triangle using the centers of the cans in the first pair and the center of one of the cans in the second pair. Calling the diameter of a can '1', we get a triangle with hypotenuse 2, height 1, and width 3^(.5)=1.73. – Rob Watts May 19 '15 at 19:59
  • 2
    That means a width of 0.73 is used up by each of the unpaired cans, which is not as good as the average of 0.5 used up by a pair. – Rob Watts May 19 '15 at 20:00
  • @RobWatts That's what I'm doing at this moment. I'm just trying to realize how many cans I have – leoll2 May 19 '15 at 20:00
  • My back-of-the-envelope math says you can fit floor(400*3/(2*cos(30))) = 692 cans this way. Hmm, can that be right? It's a lot more than 401... – Kevin May 19 '15 at 20:05
  • 2
    @Kevin If that's true, I've a new job at CocaCola packaging industry. – leoll2 May 19 '15 at 20:06
  • 1
    Oops, got the can radii wrong. My second envelope says floor(400*3/(4*cos(30))) = 346. – Kevin May 19 '15 at 20:14
1

Perhaps:

By shifting the top row of circles
enter image description here
And then cramming 1 in the top left corner, you will get a trapezoid shape. Although this could only be maintained depending on properties of the box

(I have yet to have the math to prove this)

Mark N
  • 5,868
  • 22
  • 60