stacking cans in a pyramid
zachary brown
If you have a bunch of cans and you want to stack them in a pyramid with
each can resting on the lids of two other cans, like so:
C
C C
C C C
C C C C
such that as few cans are left over as possible, and you know the total
number of cans you have, how do you calculate how many cans will be on
the bottom layer, without actually trying it?
Zack
Eric Burke
Let N = number of cans
Let n = number of rows of the pyramid = number of cans in the bottom row
Total number of cans in pyramid is n(n+1)/2.
Solve n(n+1)/2 = N for n.
n^2 + n - 2N = 0
n = floor((-1 + sqrt(1+4N)) / 2)
-E
--
---------------------------------------------------------------------
Eric Burke | W 415 933 6795
Software Development Engineer | Fax 415 390 6056
Cosmo Code | ebu...@sgi.com
Silicon Graphics, Inc. | http://reality.sgi.com/eburke
---------------------------------------------------------------------
PGP Public Key fingerprint:
D7 B0 DF 2F 1E 9D 96 5D D1 92 C4 53 A7 47 63 B1
---------------------------------------------------------------------
John Wilkinson
Eric Burke wrote:
>
> zachary brown wrote:
> >
> > If you have a bunch of cans and you want to stack them in a pyramid with
> > each can resting on the lids of two other cans, like so:
> >
> > C
> > C C
> > C C C
> > C C C C
> >
> > such that as few cans are left over as possible, and you know the total
> > number of cans you have, how do you calculate how many cans will be on
> > the bottom layer, without actually trying it?
>
> Let N = number of cans
> Let n = number of rows of the pyramid = number of cans in the bottom row
> Total number of cans in pyramid is n(n+1)/2.
>
> Solve n(n+1)/2 = N for n.
>
> n^2 + n - 2N = 0
>
> n = floor((-1 + sqrt(1+4N)) / 2)
The expression inside the sqrt should be 1+8N.
--
John Wilkinson
zachary brown
In article <327FB1...@sgi.com>, Eric Burke <ebu...@sgi.com> wrote:
|zachary brown wrote:
|>
|> If you have a bunch of cans and you want to stack them in a pyramid with
|> each can resting on the lids of two other cans, like so:
|>
|> C
|> C C
|> C C C
|> C C C C
|>
|> such that as few cans are left over as possible, and you know the total
|> number of cans you have, how do you calculate how many cans will be on
|> the bottom layer, without actually trying it?
|
|Let N = number of cans
|Let n = number of rows of the pyramid = number of cans in the bottom row
|Total number of cans in pyramid is n(n+1)/2.
|
|Solve n(n+1)/2 = N for n.
|
|n^2 + n - 2N = 0
|
|n = floor((-1 + sqrt(1+4N)) / 2)
What is floor()? Some kind of function?
Zack
Rouben Rostamian
In article <55nl6u$c...@lynx.dac.neu.edu>,
zachary brown <zbr...@lynx.dac.neu.edu> wrote:
:If you have a bunch of cans and you want to stack them in a pyramid with
:each can resting on the lids of two other cans, like so:
:
: C
: C C
: C C C
:C C C C
:
:such that as few cans are left over as possible, and you know the total
:number of cans you have, how do you calculate how many cans will be on
:the bottom layer, without actually trying it?
If you begin building the pyramid from the top, you won't need to
calculate anything :-)
--
Rouben Rostamian <rou...@math.umbc.edu>
Eric Burke
> |>
> |> If you have a bunch of cans and you want to stack them in a pyramid with
> |> each can resting on the lids of two other cans, like so:
> |>
> |> C
> |> C C
> |> C C C
> |> C C C C
> |>
> |> such that as few cans are left over as possible, and you know the total
> |> number of cans you have, how do you calculate how many cans will be on
> |> the bottom layer, without actually trying it?
> |
> |Let n = number of rows of the pyramid = number of cans in the bottom row
> |Total number of cans in pyramid is n(n+1)/2.
> |
> |Solve n(n+1)/2 = N for n.
> |
> |n^2 + n - 2N = 0
> |
> |n = floor((-1 + sqrt(1+4N)) / 2)
>
> What is floor()? Some kind of function?
Oops. We damn software guys are always programming. Yes, floor() is a
function that says:
floor(x) = the greatest integer less than or equal to x.
Thus,
floor(3.4) = 3.
floor(3) = 3.
floor(-2.78) = -3.
David Karr
In article <327FB4...@sgi.com> John Wilkinson <j...@sgi.com> writes:
>Eric Burke wrote:
>> Solve n(n+1)/2 = N for n.
In fact you really need the least integer n such that n(n+1)/2 >= N.
>>
>> n^2 + n - 2N = 0
>>
>> n = floor((-1 + sqrt(1+4N)) / 2)
>> ^^^^
>
>
>The expression inside the sqrt should be 1+8N.
Right, and the "floor" should be a "ceil". You need to round *up*
whenever 1+8N is not a perfect square.
ObPuzzle: Suppose you don't want to do all this math. What's a
sure-fire algorithm that will allow you to stack the cans correctly
without any extra calculation, and without any risk that you'll have
to move a can that you've already placed because you were wrong about
needing it there? (That is, ensure that if you have, say, only 55
cans, you don't foolishly put 11 cans in the bottom row.)
-- David A. Karr (dk...@bbn.com)
(Not necessarily representing the views of my employer)
Michael treacy
zbr...@lynx.dac.neu.edu (zachary brown) wrote:
>If you have a bunch of cans and you want to stack them in a pyramid with
>each can resting on the lids of two other cans, like so:
> C
> C C
> C C C
>C C C C
>such that as few cans are left over as possible, and you know the total
>number of cans you have, how do you calculate how many cans will be on
>the bottom layer, without actually trying it?
>Zack
Ok, well, I played around with it and came up with the following:
Basically, when you add up the total number of cans in the pyramid,
you are summing an arithmetic series. The formula for the sum is
S = (n/2)[2a + (n-1)d]
where n = number of terms
a = first term
d = difference between successive terms
In the problem stated, the sum looks like: 1 + 2 + 3 + 4 + 5 + 6 + ...
giving a = 1 and d = 1.
Now, suppose that you have x cans to stack up, then the sum has to be
equal to x. This gives
(n/2)[2 + (n-1)1] = x using a = 1 and d = 1
Simplification of this gives
2n + n^2 - n = 2x
i.e n^2 + n = 2x
or n^2 + n - 2x = 0
Now since x (the number of cans to be stacked) is known, this
quadratic equation can be solved.
One of the roots will be negative - discard - and the other will be
the number of terms in the series. Careful examination will show that
this also corresponds to the number of cans on the bottom layer.
I haven't examined what happens when the sum does not add up to
exactly the number of cans to be stacked giving a number of cans left
over.
Hope this helps.
Mike
Dave Rusin
In article <55nl6u$c...@lynx.dac.neu.edu>,
zachary brown <zbr...@lynx.dac.neu.edu> wrote:
:If you have a bunch of cans and you want to stack them in a pyramid with
:each can resting on the lids of two other cans, like so:
:such that as few cans are left over as possible, and you know the total
:the bottom layer, without actually trying it?
In article <55osmp$g...@sun2.math.umbc.edu>,
Rouben Rostamian <rou...@sun2.math.umbc.edu> wrote:
>If you begin building the pyramid from the top, you won't need to
>calculate anything :-)
Indeed, one need only start at the lower left and build triangles using
the first 1, 3, 6, 10, ... cans until one runs out. Surely those who stock
market shelves are not solving quadratic equations.
dave
Jonathan Haas
In article <55p2a3$c...@info-server.bbn.com>, David Karr <dk...@bbn.com> wrote:
>
>ObPuzzle: Suppose you don't want to do all this math. What's a
>sure-fire algorithm that will allow you to stack the cans correctly
>without any extra calculation, and without any risk that you'll have
>to move a can that you've already placed because you were wrong about
>needing it there? (That is, ensure that if you have, say, only 55
>cans, you don't foolishly put 11 cans in the bottom row.)
Stack the cans in a triangle, then start building up the sides of
the triangle one row at a time. This is the order you put down the
first ten cans in:
10
6 9
3 5 8
1 2 4 7
Can 11 will go to the right of can 7, can 12 will rest on cans
7 and 11, and so on.
ObFollowup: What if the cans were to be arranged in a tetrahedron?
--
__/\__ Jonathan S. Haas | Jake liked his women the way he liked
\ / jh...@microsoft.com | his kiwi fruit: sweet yet tart, firm-
/_ _\ Microsoft Corporation | fleshed yet yielding to the touch, and
\/ Don't Tread On Me | covered with short brown fuzzy hair.
Tom Magliery
In article <56e74c$e...@Starbase.NeoSoft.COM>,
posi...@Starbase.NeoSoft.COM (Jonathan Haas) wrote:
> ObFollowup: What if the cans were to be arranged in a tetrahedron?
A concise algorithm I sent David for the triangular version is:
while there are cans left to stack
place a can as high as possible
end-while
Conveniently enough, this also solves the tetrahedral version.
mag
p.s. I only answered because I wanted to use "tetrahedral" in a sentence. :-)
--
.---o Tom Maglierygry, Research Programmer .---o
`-O-. NCSA, 605 E. Springfield (217) 333-3198 `-O-.
o---' Champaign, IL 61820 O- m...@ncsa.uiuc.edu o---'
Juan Carlos Gil Montoro
Tom Magliery wrote:
>
> In article <56e74c$e...@Starbase.NeoSoft.COM>,
> posi...@Starbase.NeoSoft.COM (Jonathan Haas) wrote:
>
> > ObFollowup: What if the cans were to be arranged in a tetrahedron?
>
> A concise algorithm I sent David for the triangular version is:
>
> while there are cans left to stack
> place a can as high as possible
> end-while
>
> Conveniently enough, this also solves the tetrahedral version.
>
> mag
>
> p.s. I only answered because I wanted to use "tetrahedral" in a sentence. :-)
>
And you ended up using it twice !
--
_
(_) _ _ _ _ ___ ___ _ _ _ __
| |( ) ( ) /'_` )/' _ `\ /'___) /'_` )( '__)
| || (_) |( (_| || ( ) | ( (___ ( (_| || | Lo bueno, si breve,
_ | |`\___/'`\__,_)(_) (_) `\____)`\__,_)(_) dos veces bueno
( )_| | Juan Carlos Gil Montoro
`\___/' j...@juguete.quim.ucm.es ------> .es from SPAIN, actually
http://cacharro.quim.ucm.es/users/jc.html
Seth Breidbart
In article <328BB4...@juguete.quim.ucm.es>,
Juan Carlos Gil Montoro <j...@juguete.quim.ucm.es> wrote:
>Tom Magliery wrote:
>> Conveniently enough, this also solves the tetrahedral version.
>> p.s. I only answered because I wanted to use "tetrahedral" in a sentence. :-)
>
>And you ended up using it twice !
No, he used it once and mentioned it once.
Patrick Hamlyn
se...@panix.com (Seth Breidbart) wrote:
Actually, I would argue that he mentioned it twice, and one of the
mentions also qualified as a usage.
Nitnitpickers anon
>Se...@nitpickers.r.us
+=======================================+
| Name: Patrick Hamlyn |
| Company: Multiprogramming Pty Ltd |
| Email: pa...@multipro.com.au |
+=======================================+
Alasdair Stewart
Patrick Hamlyn wrote:
>
> >>Tom Magliery wrote:
> >>> Conveniently enough, this also solves the tetrahedral version.
> >>> p.s. I only answered because I wanted to use "tetrahedral" in a sentence. :-)
> >>
> >>And you ended up using it twice !
>
> >No, he used it once and mentioned it once.
>
> Actually, I would argue that he mentioned it twice, and one of the
> mentions also qualified as a usage.
>
> Nitnitpickers anon
> >Se...@nitpickers.r.us
>
What is the most famous place of worship in Hampshire, England?
Winchestetrahedral. (Winchester Cathedral?!?!?!?!)
I only answered because I wanted to use "tetrahedral" in a sentence.
;-)
--
E-mail ads...@globalnet.co.uk
_ _ __ ___ __ _ __ ___
/_\ | \ |__ | |__ \ _ / /_\ |__| |
/ \ .|_/ . __| | |__ \/ \/ / \| \ |
Tom Maciukenas
Scott Sauyet <ssa...@claude.math.wesleyan.edu> wrote:
> [...] But really
>the only reason I replied was to include my .sig in the thread:
> __ ___
>(_ c o t | Are the last three words of ssauyet@math
>__) a u y e | this sentence "used or mentioned?" .wesleyan.edu
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The answer is "yes", whatever interpretation you choose. :^)
-TOMM
Tom Magliery
In article
<Pine.SUN.3.93.961122...@claude.math.wesleyan.edu>, Scott
Sauyet <ssa...@claude.math.wesleyan.edu> wrote:
> __ ___
>(_ c o t | Are the last three words of ssauyet@math
>__) a u y e | this sentence "used or mentioned?" .wesleyan.edu
What bothers me about your .signature is that you forgot the ending
punctuation. Ending punctuation is particularly important on
interrogative sentences. I'm also not sure why there is a question mark
in your quoted phrase.
mag
P.S. Followups set to rec.puzzles, Kingdom of Pedantry
--
--
.---o Tom Magliery, Research Programmer .---o
Scott Sauyet
> = Patrick Hamlyn <pa...@multipro.com.au>
>> = Seth Breidbart <se...@panix.com>
>>> = Juan Carlos Gil Montoro <j...@juguete.quim.ucm.es>
>>>> = Tom Magliery <m...@ncsa.uiuc.edu>
>>>> Conveniently enough, this also solves the tetrahedral version.
>>>> p.s. I only answered because I wanted to use "tetrahedral" in a sentence.
>>> And you ended up using it twice !
>> No, he used it once and mentioned it once.
> Actually, I would argue that he mentioned it twice, and one of the
> mentions also qualified as a usage.
I'm not sure what you mean by mentioned in that case. I distinguish
mention from usage by whether the focus is upon the word in question
or its meaning. The former is mention, the latter usage. But really
the only reason I replied was to include my .sig in the thread:
Tom Maciukenas
Tom Magliery <m...@ncsa.uiuc.edu> wrote:
: Scott Sauyet <ssa...@claude.math.wesleyan.edu> wrote:
:
: > __ ___
: >__) a u y e | this sentence "used or mentioned?" .wesleyan.edu
: What bothers me about your .signature is that you forgot the ending
: punctuation. Ending punctuation is particularly important on
: interrogative sentences. I'm also not sure why there is a question mark
: in your quoted phrase.
But my high school grammar teachers were quite adamant that the
puncuation ALWAYS goes within the quotes. No matter how confusing
that might be. I think it's time that rule was changed, myself, but
there it is.
: P.S. Followups set to rec.puzzles, Kingdom of Pedantry
Or should that be "Pedantgry"?
-tOMM