IQ / Programming Quiz (Cannon-Ball Stacks)

[AspDotNetDev]

Points awarded for getting as close as possible to cheating without fully qualifying as cheating. ;P

Thou mewling ill-breeding pignut!

[AspDotNetDev]

Good call on confirming you didn't make an error. I started out on paper and indeed made an error, which I happened to spot when I made the C# program.

Thou mewling ill-breeding pignut!

[AspDotNetDev]

jsc42 wrote:

lysdexia

:laugh: I thought I was the only one who used that word. Actually, I saw it on some nature show when I was younger and have been using it ever since. :thumbsup:

Thou mewling ill-breeding pignut!

[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