IQ / Programming Quiz (Cannon-Ball Stacks)

[YvesDaoust]

1. looked up the tetrahedral numbers in Wikipedia and found this list: 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969... (10 seconds of work) 2) opened an Excel sheet and created the table of sums 2 5 11 21 36 57... 5 8 14 24 39 60... 11 14 20 30 45 66... 21 24 30 40 55 76... 36 39 45 55 70 91... ... (just needed to recall the appropriate syntax to form the cell expression; 1 minute of work) 3) sorted all sums in increasing order 2, 5, 5, 8, 11, 11, 14, 14, 20, 21, 21, 24, 24, 30, 30, 36, 36, 39, 39, 40, 45, 45, 55, 55, 57, 57, 60, 60, 66, 66, 70, 76, 76, 85, 85, 88, 88, 91, 91, ... (moved to Word to flatten the table structure; 1 minute of work) 4) spotted by eye in the list the first tetrahedral number larger than 20: 680, the sum of 120 and 560. (Lucky the Wikipedia list was long enough :)) (2 extra minutes) 5) explained the answer in CodeProject (half an hour)

[yiangos]

Well, using a bit of python:

def pyr(l):
if l==0:
return 0
elif l==1:
return 1
else:
return pyr(l-1)+l*(l+1)/2

#then we brute-force
a=[pyr(i) for i in range(100)][1:]
b=[(i,j,k) for i in a
for j in a
for k in a
if (i!=j and i+j==k)]
if len(b)>0:
print b[0]

Running the above yields the result as

(120, 560, 680)

as others have already pointed out... (Edit: changed the type from general to Answer)

Φευ! Εδόμεθα υπό ρηννοσχήμων λύκων! (Alas! We're devoured by lamb-guised wolves!)

[YvesDaoust]

A Python script can do. Grow a list of tetrahedral numers; for every new number, try and find a number in the list such that when subtracted from the new number, it gives another number in the list. (This way you make sure that for every new number the two terms of the decomposition are already in the list.)

# Start with an empty list
List= {}
n= 1

while n > 0:
# Try the next tetrahedral number
r= n * (n + 1) * (n + 2) / 6

# Try every number in the list
for p in List:
    # Lookup the difference between the new number and the current one
    q= r - p
    if p != q and q in List:
        print p, '+', q, '=', r

        # Flag as found
        n= -1
        break

# Not found, extend the list
List\[r\]= None
n+= 1

For efficiency of the search, the list is implemented as a dictionnary. Yields:

560 + 120 = 680

[el_vez]

Haskell answer:

layers = scanl1 (+) [1..]
sizes = scanl1 (+) layers
combinedSizes = [(s1, s2, s1 + s2) | s1 <- sizes, s2 <- takeWhile (< s1) sizes]
newPyramids = filter combinesToPyramid combinedSizes
where combinesToPyramid (s1, s2, sum) = sum `elem` (takeWhile (sum >=) sizes)

answer = head newPyramids

-------- SPOILER ------------ this gives the answer as "(560, 120, 680)", (if you load it up in GHCI and type "answer"). If you want the n first solutions, just type "take n newPyramids":

take 3 newPyramids
[(560,120,680),(27720,1540,29260),(29260,4960,34220)]

[YvesDaoust]

Brute force:

def T(n):
return n * (n + 1) * (n + 2) / 6

r= 1
while True:
q= 1
while q < r:
p= 1
while T(p) + T(q) < T(r):
p+= 1
if T(p) + T(q) == T(r):
print T(p), '+', T(q), '=', T(r)
q+= 1
r+= 1

Yields:

10 + 10 = 20
560 + 120 = 680
120 + 560 = 680
27720 + 1540 = 29260
1540 + 27720 = 29260
29260 + 4960 = 34220
4960 + 29260 = 34220
59640 + 10660 = 70300
10660 + 59640 = 70300
182104 + 39711 = 221815
39711 + 182104 = 221815
...

[YvesDaoust]

Even bruter force:

def T(n):
return n * (n + 1) * (n + 2) / 6

for r in range (1, 1000):
for q in range(1, r):
for p in range(1, q):
if T(p) + T(q) == T(r):
print T(p), '+', T(q), '=', T(r)

Yields:

120 + 560 = 680
1540 + 27720 = 29260
4960 + 29260 = 34220
10660 + 59640 = 70300
39711 + 182104 = 221815
102340 + 125580 = 227920
7140 + 280840 = 287980
19600 + 447580 = 467180
...

[PhilLenoir]

Sorry, 6 on the bottom, 3 next then 1 = total 10 for a 3x3x3 pyramid!

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[AspDotNetDev]

Nope, 20 + 54 is not 55.

Thou mewling ill-breeding pignut!

[PhilLenoir]

Maybe not the most elegant solution but might possibly be the fastest way to come up with the answer!: 1 Using Excel I created 3 columns: column 1 being a linear sequence (1,2,3 ....100); column 2 representing each layer (B1=1,B2=A1+A2); the third representing the pyramid (C1=1,C2=B1+B2) 2 I pasted these into an Access table 3 I cross joined the table to itself and added the two columns 3 4 I inner joined the query to the table on sum = column 3 Answer 120 (8 layers) + 560 (14 layers) = 680 (15 layers)

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[RolfReden]

got one, just by accident :) 560 + 120 = 680, which are an 8-layered and a 14-layered pyramid combined to a 15-layered pyramid. still thinking of an smart search or algebraic solution tho [edit for some code] clear clc lines(0) n = 30 m(1) = 1 k(1) = 1 for i = 1:n m(i+1) = m(i) + 1 + (i) k(i+1) = k(i) + m(i+1) end [/edit]

[Stephen Dycus]

Wow such complicated answers.... the answer is 4. The question is If the two smaller pyramids are different sizes, however, what would be the minimum number of cannon-balls he could use to make one large tetrahedral pyramid? ... but the thing is, there are still only 20 cannonballs to use to build the pyramid and he never said you had to use all the cannonballs. It asks the MINIMUM... which is 3 on the bottom + 1 on top.

[PhilLenoir]

How do 3 cannonballs make a tetrahedral pyramid? :P

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[Stephen Dycus]

I didn't say 3 I said 4 :P

[PhilLenoir]

... but the source has to be two tetrahedral pyramids ...

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[Stephen Dycus]

but not all of them: The smallest number of cannon-balls he can have if the two pyramids are the same size is twenty (assuming he uses every cannon-ball in both pyramids). That's an assumption, not a requirement :)

[PhilLenoir]

Using that logic I think that your answer might be one :cool:

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[Stephen Dycus]

Otherwise you would have to form two different sized pyramids who could form one larger pyramid without any left overs. That would require a Calculus 1 concept called optimization, which isn't too mard but more work than I want to do.

[AspDotNetDev]

You missed this bit from the problem: "assuming he uses every cannon-ball in both pyramids". But nice try. :)

Thou mewling ill-breeding pignut!

[AspDotNetDev]

PhilLenoir wrote:

Using Excel I created 3 columns: column 1 being a linear sequence (1,2,3 ....100); column 2 representing each layer (B1=1,B2=A1+A2); the third representing the pyramid (C1=1,C2=B1+B2)

That's how I started out on paper, then converted that to C#.

PhilLenoir wrote:

I inner joined the query to the table on sum = column 3

I hadn't considered using a database. Points for innovation. :thumbsup:

PhilLenoir wrote:

680

That's the answer I got. :)

Thou mewling ill-breeding pignut!

[AspDotNetDev]

Points for compact code. :thumbsup:

Thou mewling ill-breeding pignut!