IQ / Programming Quiz (Cannon-Ball Stacks)

[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!

[Ronald M Martin]

Lots of effort has been spent on this problem by many people over a very long time. Look for it on Wikipedia to get an idea of how difficult a problem it is and how much computer time has been devoted to checking the conjecture over a very large range of numbers.

[AspDotNetDev]

Oh I'm sure that's true. While it would be fun to explore the problem, I suspect it is all but impossible to solve. :)

Thou mewling ill-breeding pignut!

[jsc42]

AspDotNetDev wrote:

I saw it on some nature show when I was younger

It would be more amazing if you'd been using it after seeing it when you were older. It is implicit that you were younger than you are now when you saw it. I've been using the word for years - I cannot recall if I saw it anywhere or if I made it up as a self describing word. There is a word for self describing words but I cannot recall what it is (it isn't onomatopoeia - that's words that sound like what they represent) and there is an antonym for words that describe their opposites (e.g. fat is a very thin word). Some CPian took this to another level (I forget who) with a self describing acronym in their signature block: "I have CDO - it's like OCD but arranged alphabetically" Thanks to whoever can tell me what the word for self describing words in and what its antonym is. Thanks too to AspDotNetDev for the challenge - the large no of responses shows that you hit a hot spot.

[jsc42]

I had a recent project that required a progress / status bar to be displayed but there was a restriction that there could only be zero, one or two images and the system that displayed them could only show them at their real width (no scaling). The progress bar had to work for all values from 0 to 100. The simplest solution was to create 101 icons (one for each possible value) but I wanted to minimise the pool of icons (as I had to create them and there were four different colours so 101 would instantly grow to 404). Starting with Goldbach's Conjecture, I discovered that the only numbers that I couldn't create as the sum of two primes in the range 1 to 100 were 27, 51, 57, 65, 77 and 95. (This is consistent with Goldbach's Conjecture as these are all odd numbers and any odd number can be represented as an even number + 1 and it is even numbers that his conjecture say can be the sum of only two primes). The answer was to cheat and invent a new type of number! I've called it a pseudo prime number. The following is a quote from the actual source code comments:

REM {
The relative proportions are shown as a series of adjacent icons. A column can contain a maximum
of 10 icons. As the left and right ends of the image are icons, this leaves a maximum of 8 icons for
the values to be displayed. As there are (up to) four coloured bars per icon, each colour can be
represented as either a single icon or two adjacent icons (4 * 2 = 8).

This formula uses Goldbach's conjecture (1742) (modified) that any even number can be represented 
as the sum of (up to) two prime numbers and any odd number can be represented as the sum of (up to) 
three prime numbers (this is a direct corollary as if you can create any even number from 2 primes, just 
adding 1 will produce the next odd number). Note: This treats 1 as a prime number.  
With the sneaky addition of '4' as a pseudo prime number, we can generate all of the numbers from 1 to 
102 with only single numbers or a sum of two numbers. We do not even need the prime numbers 41, 71
or 89. 

So, actual icon widths used are: (total 26)
	1, 2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 67, 73, 79, 83, 87, 91, 97
};

And the sums for 1 to 102 are:

1
2
3,	4
5,	3+3
7,	4+4,	7+2,	5+5
11,	7+5
13,	7+7,	13+2,	11+5
17,	11+7
19,	13+7,	19+2,	11+11
23,	13+11,	23+2,	13+13,	23+4,	17+11
29,	17+13
31,	19+13,	31+2,	17+17,	31+4,	19+17
37,	19+19,	37+2,	23+17
37+4,	23+19
43,	31+13, 43+2,	23+23
47

[AspDotNetDev]

jsc42 wrote:

It would be more amazing if you'd been using it after seeing it when you were older. It is implicit that you were younger than you are now when you saw it.

:laugh: Do you tell people that you are 30 years and 200 days old, or do you tell them you are 30 years old? I age in large discrete units. If I were the same age I am now, I wouldn't be younger. :rolleyes:

Thou mewling ill-breeding pignut!