43
$\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.

Improve this question
$\endgroup$
10
  • 4
    $\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, 2015 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, 2015 at 20:20
  • 1
    $\begingroup$ I assume we aren't allowed to dive into the third dimension for this question, eh? $\endgroup$
    – Bailey M
    May 19, 2015 at 20:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ian MacDonald
    May 20, 2015 at 4:52
  • 20
    $\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, 2015 at 13:04

7 Answers 7

Reset to default
43
$\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

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!

Improve this answer
$\endgroup$
11
  • 5
    $\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, 2015 at 13:26
  • $\begingroup$ Well done! For those who want an illustration, see user4651's answer. $\endgroup$
    – Mike Earnest
    May 20, 2015 at 17:42
  • 2
    $\begingroup$ I added an edit with a clearer (imo) visualization to this solution. $\endgroup$
    – M.Herzkamp
    May 21, 2015 at 9:03
  • 1
    $\begingroup$ @supercat: math mistake. 168x2 would fit 337. $\endgroup$
    – user4651
    May 22, 2015 at 10:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – user4651
    May 22, 2015 at 11:17
12
$\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.

Improve this answer
$\endgroup$
2
  • 3
    $\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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
8
  • 3
    $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
4
  • 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, 2015 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, 2015 at 2:37
  • $\begingroup$ What if you use a "diamond" of six cans? Eight? 400? $\endgroup$
    – Random832
    May 20, 2015 at 3:32
  • 1
    $\begingroup$ @Random832: Less "tilt" = "less horizontal gain" $\endgroup$
    – BmyGuest
    May 20, 2015 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.

Improve this answer
$\endgroup$
6
  • $\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, 2015 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, 2015 at 20:08
  • $\begingroup$ @leoll2 I edited the picture and specified the difference between this answer and Mark's. $\endgroup$
    – Quark
    May 19, 2015 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, 2015 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, 2015 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.

Improve this answer
$\endgroup$
6
  • $\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, 2015 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, 2015 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, 2015 at 20:00
  • 2
    $\begingroup$ @Kevin If that's true, I've a new job at CocaCola packaging industry. $\endgroup$
    – leoll2
    May 19, 2015 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, 2015 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)

Improve this answer
$\endgroup$
5
  • 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, 2015 at 19:59
  • $\begingroup$ @leoll2 Maybe you can try cramming 1 on both sides in ;) $\endgroup$
    – Mark N
    May 19, 2015 at 20:00
  • $\begingroup$ Or split the can as I previously did with traffic cones! $\endgroup$
    – leoll2
    May 19, 2015 at 20:01
  • $\begingroup$ I think you'd only be allowed to "cram" cans if lateral thinking were allowed. $\endgroup$
    – Kevin
    May 19, 2015 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, 2015 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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