36
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This tool engineeringtoolbox.com/circles-within-rectangle-d_1905.html says that for (200,2,1) the maximum is 400. I don't trust it, though! $\endgroup$ – leoll2 May 19 '15 at 20:12
  • 2
    $\begingroup$ @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. $\endgroup$ – Rob Watts May 19 '15 at 20:20
  • $\begingroup$ I assume we aren't allowed to dive into the third dimension for this question, eh? $\endgroup$ – Bailey M May 19 '15 at 20:43
  • $\begingroup$ @BaileyM Why restrict yourself to only 3. Why not 4 or 5? :p $\endgroup$ – Mark N May 19 '15 at 20:48
  • 11
    $\begingroup$ Really tempted to post an answer of the pic in the OP, with the text altered to say "395 more cans". $\endgroup$ – rybo111 May 20 '15 at 13:04
34
$\begingroup$

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

Sorry I'm new to this forum... I'm going to try to post an answer. Unfortunately I'm bad with computers so I can't draw a picture... Please get out a pencil and paper! The summary is:

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!

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Elias Benevedes May 20 '15 at 13:26
  • $\begingroup$ Well done! For those who want an illustration, see user4651's answer. $\endgroup$ – Mike Earnest May 20 '15 at 17:42
  • $\begingroup$ 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? $\endgroup$ – supercat May 20 '15 at 22:11
  • 2
    $\begingroup$ I added an edit with a clearer (imo) visualization to this solution. $\endgroup$ – M.Herzkamp May 21 '15 at 9:03
  • $\begingroup$ @M.Herzkamp, so did I. But thanks for putting one here. :) $\endgroup$ – user4651 May 22 '15 at 8:59
11
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ In your $F(n)$ expression, the $0.995$ number should actually be $\approx$ 0.99578, so that $F(201)>200$. $\endgroup$ – Mike Earnest May 20 '15 at 4:10
  • $\begingroup$ 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. $\endgroup$ – JLee May 20 '15 at 13:13
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Glen O May 20 '15 at 7:45
  • $\begingroup$ 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. $\endgroup$ – user4651 May 20 '15 at 7:52
  • $\begingroup$ 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. $\endgroup$ – Glen O May 20 '15 at 8:07
  • $\begingroup$ @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. $\endgroup$ – user4651 May 20 '15 at 8:12
  • $\begingroup$ 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. $\endgroup$ – user4651 May 20 '15 at 8:22
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mike Earnest May 20 '15 at 0:55
  • $\begingroup$ ^I mean $1.99156$ is the distance between the centers of two cans which touch the south wall $\endgroup$ – Mike Earnest May 20 '15 at 2:37
  • $\begingroup$ What if you use a "diamond" of six cans? Eight? 400? $\endgroup$ – Random832 May 20 '15 at 3:32
  • 1
    $\begingroup$ @Random832: Less "tilt" = "less horizontal gain" $\endgroup$ – BmyGuest May 20 '15 at 7:36
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user3294068 May 19 '15 at 20:07
  • $\begingroup$ I'm not sure what I was thinking, I think I just looped back on my original thoughts. Going to edit the picture. $\endgroup$ – Quark May 19 '15 at 20:08
  • $\begingroup$ @leoll2 I edited the picture and specified the difference between this answer and Mark's. $\endgroup$ – Quark May 19 '15 at 20:17
  • $\begingroup$ 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). $\endgroup$ – Rob Watts May 19 '15 at 20:30
  • $\begingroup$ 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. $\endgroup$ – user3294068 May 19 '15 at 20:32
1
$\begingroup$

Perhaps a configuration like this?

enter image description here

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rob Watts May 19 '15 at 19:59
  • 2
    $\begingroup$ 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. $\endgroup$ – Rob Watts May 19 '15 at 20:00
  • $\begingroup$ @RobWatts That's what I'm doing at this moment. I'm just trying to realize how many cans I have $\endgroup$ – leoll2 May 19 '15 at 20:00
  • 2
    $\begingroup$ @Kevin If that's true, I've a new job at CocaCola packaging industry. $\endgroup$ – leoll2 May 19 '15 at 20:06
  • 1
    $\begingroup$ Oops, got the can radii wrong. My second envelope says floor(400*3/(4*cos(30))) = 346. $\endgroup$ – Kevin May 19 '15 at 20:14
1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ I don't think this could work. The bottom amount is unchanged, while the top cans are for sure less than before. $\endgroup$ – leoll2 May 19 '15 at 19:59
  • $\begingroup$ @leoll2 Maybe you can try cramming 1 on both sides in ;) $\endgroup$ – Mark N May 19 '15 at 20:00
  • $\begingroup$ Or split the can as I previously did with traffic cones! $\endgroup$ – leoll2 May 19 '15 at 20:01
  • $\begingroup$ I think you'd only be allowed to "cram" cans if lateral thinking were allowed. $\endgroup$ – Kevin May 19 '15 at 20:07
  • 3
    $\begingroup$ @Kevin If lateral thinking were allowed, I would grind up the cans so that I could fit thousands in there! $\endgroup$ – Mark N May 19 '15 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.