IQ / Programming Quiz (Cannon-Ball Stacks)

[AspDotNetDev]

Stephen Dycus wrote:

the answer is 20. Otherwise, it's 4

Nope and nope. :)

Rafiki said:

Look harder.

Thou mewling ill-breeding pignut!

[Stephen Dycus]

"I will post tomorrow how I arrived at my solution (which may be incorrect, as the book doesn't list what the correct answer is)" You can't say "nope" when you don't even know if you are correct XD

[AspDotNetDev]

My not know if I'm correct does not preclude my knowing you are incorrect. :)

Thou mewling ill-breeding pignut!

[YvesDaoust]

Not-so-brute brute-force: This version is based on a simple test for tetrahedrality: if N = n.(n+1).(n+2), n is the integer cube root of N, so that N gives n gives back the same N. (As one can check, n^3 <= N < (n+1)^3 so that n <= N^1/3 < n+1.) Now all tetrahedral number pairs are tried and their sum tested for tetrahedrality.

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

def IsT(N):
return N == T(int(pow(N, 1. / 3.)))

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

[Stephen Dycus]

Yes it does, if you are incorrect then you do not know the correct answer. With 20 cannonballs there are only 3 possible answers: 3+1 = 4 aka MIN 6+3+1 = 10 10+6+3+1 = 20 aka MAX Since my solution IS a tetrahedral pyramid you cannot deduce that my answer is incorrect without knowing the correct answer.

[YvesDaoust]

;)

[YvesDaoust]

Thanks. I just released a more efficient compact one.

[AspDotNetDev]

RolfReden wrote:

still thinking of an smart search or algebraic solution tho

You could start with this equation:

a(a^2 + 3a + 2) + (a + b)((a + b)^2 + 3(a + b) + 2) = (a + b + c)((a + b + c)^2 + 3(a + b + c) + 2)

The variable (a) is the Nth pyramid for the smallest pyramid. (a + b) is the Nth pyramid for the medium pyramid. (a + b + c) is the Nth pyramid for the large pyramid. Once you have solved for those values, you can plug them into this equation:

n(n + 1)(n + 2)/6

That converts the Nth pyramid into the number of cannon-balls in that pyramid. The first equation will have multiple solutions (infinite solutions?), and some values may be negative. Find the solution where a, b, and c are all positive with the smallest value of (a + b + c), and you have found the solution. :)

Thou mewling ill-breeding pignut!

[AspDotNetDev]

Stephen Dycus wrote:

you cannot deduce that my answer is incorrect without knowing the correct answer

I can, actually. :) Take this equation, for example:

a^2 + b^2 = c^2

Find a solution to this equation where a, b, and c are all positive integers. You might give the solution: a = 1, b = 2, c = 3. Though I may not know a correct answer, I can show that 5 does not equal 9, and so I can show that you are incorrect. Just because I don't know the solution does not mean I can't spot an incorrect solution. :)

Thou mewling ill-breeding pignut!

[Thor Sigurdsson]

You are quite correct. My brainfarts are legendary. When I said 20 and 54, I did of course mean 20 levels and 54 levels...... 20 levels are 1540 balls and 54 levels are 27720 balls. 55 levels are 29260 balls. Simplified, it can be done:

def onelev(x):
'''The x defines number of balls in a single level given the formula f(x)=(x^2)/2+(x/2)'''
return int((float(x)*float(x))/2.0)+(float(x)/2.0))

def tetra(x):
'''The x defines number of levels of balls in the tetrahedron'''
return sum([onelev(y) for y in range(1,x+1)])

tetra(20)
1540
tetra(54)
27720
tetra(55)-tetra(20)
27720

So I guess my answer was in part correct although not very accurate :) But, looking above, there is a smaller answer ( which I haphazardly ignored since I started to work up from 10 :p ) >>> searchtetra(2,18) 560 120 680 14 8 15 My bad there (yeah, don't solve puzzles while working - you don't have time to verify your mess haha :) )

I=I.am()?Code(I):0/0;

[Stephen Dycus]

But you are still under the *assumption* that you HAVE to use all the cannonballs in the two pyramids. You are also *assuming* that the two new pyramids can exceed the original 20 cannonball count from the beginning of the problem, otherwise there would be no solution. (You can only make a 3+1 and 6+3+1 out of 20 balls, to use them all would require a 4+6+3+1 pyramid... which isn't a pyramid. If you use the spares you can make a 10+6+3+1 pyramid though) To read the problem *your* way would require an equation for the expansion of the pyramid: 1(not a pyramid of course) 3+1 height = 2 6+3+1 height = 3 10+6+3+1 height = 4 15+10+6+3+1 height = 5 ... aka new base = old base + n, where n = the new height Then you would compose three equations for the pyramids and differentiate to optimize the problem. However, the book you are reading is a book with IQ problems. These sorts of problems typically have you analyze the question itself to find what it is REALLY asking for. In this case, the question is REALLY asking: what's the smallest pyramid you could make?

[AspDotNetDev]

1. I am not making assumptions, I am reading the entire problem, which consists of more than the final sentence that ends with a question mark. 2) It would not require an equation, though an equation does help. I could work out the problem on paper pretty fast, though using something like Excel helps speed things up (note that computers are allowed, as stated in the book).

Stephen Dycus wrote:

the question is REALLY asking: what's the smallest pyramid you could make?

I thought it was asking for the smallest tetrahedral pyramid. ;)

Stephen Dycus wrote:

1(not a pyramid of course)

Interesting assumption. :)

Thou mewling ill-breeding pignut!

[Stephen Dycus]

It's not so much an assumption as it is a visual observation XD One sphere would have no component that could be considered a corner. To make something that has four corners would require 4 spheres where each sphere represents a corner : / EDIT: It's like in 3D Modeling, you *could* place a point on the screen and call it a sphere... but it's not. The more vertices you add, the smoother the sphere appears and the more you can claim it *is* one. I didn't feel like typing out tetrahedral :P

[Member 7716127]

Answer: [120 ball pyramid] + [560 ball pyramid] = [680 ball pyramid]
def tetrahedral_number(n) return n*(n+1)*(n+2)/6 end #Build an array of tetrahedral numbers t_nums = [] for i in (1..100) t_nums << tetrahedral_number(i) end print "Tetrahedral Cannonball Stack Combinations:\n\n" str = "ball pyramid" #Find sums of tetrahedral numbers that are in the tetrahedral number set for i in (0..99) for j in (i..99) if t_nums.include?(t_nums[i] + t_nums[j]) total = t_nums[i] + t_nums[j] print "[#{t_nums[i]} #{str}] + ", "[#{t_nums[j]} #{str}] = ", "[#{total} #{str}] \n\n" end end end

[Leng Vang]

There is no specific answer without specifying a layer. The equation is simplified to be: Y = (2X - 1) + sum(2X - 5) where X is the level starting at 1 as the top and Y is the number of balls required to complete paramid.

[YvesDaoust]

And now a fast and efficient brute-force method with additions only !

N= 1000
q= 1; qq= 1; qqq= 1
while q < N:
p= 1; pp= 1; ppp= 1
r= q; rr= qq; rrr= qqq
while p < q:
if ppp + qqq >= rrr:
if ppp + qqq == rrr:
print ppp, '+', qqq, '=', rrr
r+= 1; rr+= r; rrr+= rr
p+= 1; pp+= p; ppp+= pp
q+= 1; qq+= q; qqq+= qq

A few explanations: Let iii denote the i-th tetrahedral number (and ii the i-th triangular number). 1) We try all (p, q) pairs such that 1<=p<q, for increasing q's. As we go, we maintain the smallest index r such that ppp + qqq < rrr. It is easy to see that when we increment p, the condition can be invalidated; to restore it suffices to increment r (because iii is a superlinear function of i, rrr grows faster than ppp and adding 1 is enough). 2) We evaluate the tetrahedral numbers incrementally, i.e. by accumulating triangular numbers; and similarly, we evaluate the triangular numbers incrementally, by accumulating the integers. To explore all solutions among the N first tetrahedral numbers, this algorithm takes O(N^2) operations, and O(1) space. It is straightforward to adapt it to other superlinear series, such as the k-th powers. Ever heard of X^k + Y^k = Z^k ?

[YvesDaoust]

It is also possible to precompute and store the tetrahedral numbers (need 2^1/3.N of them).

# Precompute 2^1/3.N tetrahedral numbers
T= []
q= 1; qq= 1; qqq= 1
while q < 1.26 * N:
T.append(qqq)
q+= 1; qq+= q; qqq+= qq

Find all tetrahedral triplets

for q in range(1, N):
r= q
for p in range(1, q):
if T[p] + T[q] >= T[r]:
if T[p] + T[q] == T[r]:
print T[p], '+', T[q], '=', T[r]
r+= 1

[Ronald M Martin]

Not only is this answer not the smallest possible value, but if you start with tetrahedra of order 35 and 56, you won't have anywhere near enough cannon balls to build a tetrahedon of order 84.

[Ronald M Martin]

I used a spreadsheet constructed as follows: A1 = 2 A2 = 1 B1 = =IF(B1=1,A1+1,A1) B2 = =IF(B1=1,A2-1,B1-1) Then I dragged B1 and B2 downward to create a list of all the combinations of all the base sizes I wanted to examine. In my case, I chose to stop at line 2016 with column A at 64 and column B at 1. C1 = =A1*(A1+1)*(A1+3)/6 I dragged C1 to D1. E1 = =C1+D1 I dragged C1, D1 and E1 to line 2016. I looked at the line that started with 64 and 63 to determine the maximum sum I could generate from the data I was using. Then I extended the table as follows: A2017 = 1 E2017 = =A2017*(A2017+1)*(A2017+3)/6 I dragged A2017 through E2017 down until the entry in column E was as large as possible but still less than or equal to the largest sum in the upper part of the table. I added column F with 1's in the upper portion of the table and 0's in the lower portion of the table to distinguish the two types of entries. I copied just the values from the table to a new sheet. I sorted the new table using column E as the primary key and column F as the secondary key. I added conditional formatting to column E from row 2 down to change the background color of each cell to red if its value was the same as that of the cell above it. When I realized that my red cells included both cases where there were two sets of two different-sized tetrahedra that contained the same number of cannonballs and the desired cases where the cannonballs from two different-sized tetrahedra can be combined to make a larger tetrahedron, I added another column that contained 1 on the same condition that colored the red cells and 0 when those cells would be while. I then conditionally colored this column from row 2 down so that it was green if the row above contained a zero in column F. I did it this way because I couldn't create a more complex condition with the existing conditional coloring mechanism. The answers that others have posted have already covered the three solutions that I found this way. The question answered by the red cells is interesting in and of itself. It leads to other questions such as: "Are there any numbers of cannonballs that can be stacked into two tetrahedra more than two ways?" and "Are there any cannonball tetrahedra that can be decompsed into two tetrahedra two or more ways?" Questions of this type remind me of Goldbach's Conjecture that every even number greater than 2 can be expressed as the sum of two odd primes. That was the subject of one of the first programs I wrote in 1961. The conjectu

[AspDotNetDev]

Funny, the Goldbach Conjecture is the first problem listed here. Seems like a fun problem to explore in one's free time.

Thou mewling ill-breeding pignut!