mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)

- Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

- - a puzzle (https://www.mersenneforum.org/showthread.php?t=16558)

You have 680 glasses and need to build a tower 15 levels high with 1 on top. Is there an equation that can be used to solve for glasses per level?

[QUOTE=bcp19;290153]You have 680 glasses and need to build a tower 15 levels high with 1 on top. Is there an equation that can be used to solve for glasses per level?[/QUOTE]

only thing that comes to mind is (680-1)/14 =48.5 / level on average.

[QUOTE=science_man_88;290154]only thing that comes to mind is (680-1)/14 =48.5 / level on average.[/QUOTE]

it's more like a pyramid, your design would not be stable.

[QUOTE=bcp19;290159]it's more like a pyramid, your design would not be stable.[/QUOTE]

You didn't define stability as being a requirement.

[QUOTE=chalsall;290160]You didn't define stability as being a requirement.[/QUOTE]

True, but that equation would be simple to figure out, plus how would you have 1 on top and have that .5 per level?

Well the sum over the integers up to n := the nth triangular number would describe perfect triangles. So find the highest triangular number <= 680, then distribute the remainder evenly over each layer. In C:

[code]
int * pyramid(int x) {
int i,j,diff;
int sum=0;
int * layer;
printf("Input is %d\n", x);
for( i=1; sum <= x; i++)
sum += i;
sum -= (--i); i--; // The loop goes one too far, so fix it
layer = (int *)malloc(i*sizeof(int)); // Declares an array of size i
for( j=0; j<i; j++)
layer[j] = j+1; // The basic shape is a triangle
diff = x - sum;
if( diff > 0 ) {
for( j=i-1; diff>0; diff-- /* Decrement diff until diff==0 */ ) { // Distribute the difference over each layer
if( j<1 ) j = i - 1; // Keep cycling over the pyramid
layer[j]++; // Add one to the current layer
j--; // Move to the next higher layer
}
printf("There will be %d layers, as follows:\n", i);
for( j=0; j<i; j++) printf("%d\n", layer[j]);
printf("\n");
return layer;
}
else if( diff==0 ) {printf("A perfect triangle of glasses!\n\n"); return NULL;}
else {printf("You need %d more debugging printfs!\n", x); return (int *)"YOU SUCK";}
}
[/code]
Will post results for 680 in a moment (if other inputs give the right outputs). Edit: For pyramid(6), it gave me 1,2,3,4,5 so something's not right. Hang on. Edit: Found one bug. The sum goes too far. (Not done yet though.) Edit: Got em all. Also realized that this isn't exactly optimal, but it's a solution.
[code]What number of glasses should I use?
1
Input is 1
A perfect triangle of glasses!

What number of glasses should I use?
2
Input is 2
There will be 1 layers, as follows:
2

What number of glasses should I use?
3
Input is 3
A perfect triangle of glasses!

What number of glasses should I use?
4
Input is 4
There will be 2 layers, as follows:
1
3

What number of glasses should I use?
5
Input is 5
There will be 2 layers, as follows:
1
4

What number of glasses should I use?
6
Input is 6
A perfect triangle of glasses!

What number of glasses should I use?
7
Input is 7
There will be 3 layers, as follows:
1
2
4

What number of glasses should I use?
8
Input is 8
There will be 3 layers, as follows:
1
3
4

What number of glasses should I use?
680
Input is 680
There will be 36 layers, as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
24
25
26
27
28
29
30
31
32
33
34
35
36
37[/code]
When I say not optimal, I mean it seems to me that a stack of 5 glasses should be 1-2-2, not 1-4 as this code suggests, and 2 should be 1-1, not just 2. Will have to come back to this later though, I have to go code for my CS HW due in 2.5 hrs :smile: (Somebody else want to optimize the algo?)

EDIT: WHOOPS 15 per layer. There's a HUGE piece of missing information. Well, at least I had fun solving my own problem :/ (Another edit: This is a 2-D solution, as opposed to eh 3-D ones below :P:P:P)

[QUOTE=bcp19;290162]True, but that equation would be simple to figure out, plus how would you have 1 on top and have that .5 per level?[/QUOTE]

As I have learnt the hard way... Be very careful what you ask for -- you might just get it....

[CODE][/CODE][QUOTE=Dubslow;290163]Well the sum over the integers up to n := the nth triangular number would describe perfect triangles. So find the highest triangular number <= 680, then distribute the remainder evenly over each layer. In C:

[code]
int * pyramid(int x) {
int i,j,diff;
int sum=0;
int * layer;
for( i=0; sum <= x; i++)
sum += i;
layer = (int *)malloc(i*sizeof(int)); // Declares an array of size i
for( j=0; j<i; j++)
layer[j] = j+1; // The basic shape is a triangle
diff = x - sum;
if( diff != 0) {
for( j=i-1; diff>0; diff-- /* Decrement diff until diff==0 */ ) { // Distribute the difference over each layer
if( j<1 ) j = i - 1; // Keep cycling over the pyramid
layer[j]++; // Add one to the current layer
j--; // Move to the next higher layer
}
printf("There will be %d layers, as follows:\n", i);
for( j=0; j<i; j++) printf("%d\n", layer[j]);
printf("\n");
return layer;
else if( diff==0 ) {printf("A perfect triangle of glasses!\n"); return null;}
else printf("You need %d more debugging printfs!\n", x);
}[/code]
Will post results for 680 in a moment (if other inputs give the right outputs).[/QUOTE]

[QUOTE="PARI"][CODE](18:20)>sum(X=1,15,X)
%37 = 120[/CODE][/QUOTE]

so it's definitely not a perfect triangle.

[QUOTE=science_man_88;290166] so it's definitely not a perfect triangle.[/QUOTE]

Actually, that may work...
1+3+6+10+15+21+28+36+45+55+66+78+91+105+120=680

yep, that works... I was thinking 15x15,14x14, etc but it went well over 1k.

With the levels now known, without using trial and error, is there an actual equation that would solve this?

[QUOTE=bcp19;290153]You have 680 glasses and need to build a tower 15 levels high with 1 on top. Is there an equation that can be used to solve for glasses per level?[/QUOTE]
It's a pyramid with triangles at each level, each triangle packed regularly with glasses in the (2-dimensional) densest possible way, one glass at the top, and each non-top level having its side length one glass longer than the previous (higher) level.

Numbering the levels beginning with 1 at the top, the glass count for level i is the triangular number T(i) = i*(i+1)/2.
The total glass count V(n) for n levels is then
[tex]V(n) = \sum_{i=1}^n \frac{i\,(i+1)}{2} = \frac{1}{2}\left(\left(\sum_{i=1}^n i^2\right)+\left(\sum_{i=1}^n i\right)\right) = \frac{1}{2}\left(\frac{n\,(n+1)\,(2n+1)}{6}+\frac{n\,(n+1)}{2}\right) = \frac{n\,(n+1)(n+2)}{6}[/tex].
And indeed V(15) = 680.

Edit: OK, folks, you have been faster.

[QUOTE=bcp19;290167]With the levels now known, without using trial and error, is there an actual equation that would solve this?[/QUOTE]

Every level [i]n[/i] is the sum of all numbers from 1 to [i]n[/i].

So:

FOR [i]level[/i] = 1 to 15[indent]number of glasses = [tex]\sum_{i=1}^{level}i[/tex][/indent]

[QUOTE=bcp19;290167]yep, that works... I was thinking 15x15,14x14, etc but it went well over 1k.

With the levels now known, without using trial and error, is there an actual equation that would solve this?[/QUOTE]
Assuming a [URL="https://en.wikipedia.org/wiki/Polygonal_number"]polygonal number[/URL] [tex]P(s,i)=\frac{1}{2}\left((s-2)i^2 - (s-4)i\right)[/tex] of glasses at level i, with s the same constant for all levels, you would have as total number of glasses up to level n
[tex]V(n) = \sum_{i=1}^n P(s,i) = \frac{1}{2}\sum_{i=1}^n \left((s-2)i^2 - (s-4)i\right) = \frac{1}{2} \left((s-2)\left(\sum_{i=1}^n i^2\right) - (s-4)\left(\sum_{i=1}^n i\right)\right)[/tex]
[tex]= \frac{1}{12} \left((s-2)\,n\,(n+1)(2n+1) - 3\,(s-4)\,n\,(n+1)\right) = \frac{n\,(n+1)}{6} \left((n-1)s - (2n-5)\right)[/tex]
Given n and V(n), solving for s yields
[tex]s = \frac{1}{n-1}\left(\frac{6V(n)}{n\,(n+1)} + 2n-5\right)[/tex].
Indeed, substituting V(n)=680 and n=15 yields s=3.
Of course, if you would get a value for s that is not an integer greater than or equal to 2, the stack levels could not be filled with an s-gonal number of glasses.

[QUOTE=ccorn;290175]Of course, if you would get a value for s that is not an integer greater than or equal to 2, the stack levels could not be filled with an s-gonal number of glasses.[/QUOTE]

Impressive.

Could you give me that in Perl?

If not, C or C++ (or Java) would be fine.

Thanks.

[QUOTE=chalsall;290177]Impressive.

Could you give me that in Perl?

If not, C or C++ (or Java) would be fine.

Thanks.[/QUOTE]
I can, but it's just a rational function s(V,n) where V is a given total number of glasses and n is the number of levels. You can do that yourself.

Edit: Compute numerator s.num and denominator s.denom, then test s.num % s.denom == 0 && s.num >= 2*s.denom.

Edit: Even better, compute s_minus_2.num (it simplifies a bit), check that it is nonnegative, then compute denominator s_minus_2.denom and check s_minus_2.num % s_minus_2.denom == 0.

[QUOTE=ccorn;290168]It's a pyramid with triangles at each level, each triangle packed regularly with glasses in the (2-dimensional) densest possible way, one glass at the top, and each non-top level having its side length one glass longer than the previous (higher) level.

Numbering the levels beginning with 1 at the top, the glass count for level i is the triangular number T(i) = i*(i+1)/2.
The total glass count V(n) for n levels is then
[tex]V(n) = \sum_{i=1}^n \frac{i\,(i+1)}{2} = \frac{1}{2}\left(\left(\sum_{i=1}^n i^2\right)+\left(\sum_{i=1}^n i\right)\right) = \frac{1}{2}\left(\frac{n\,(n+1)\,(2n+1)}{6}+\frac{n\,(n+1)}{2}\right) = \frac{n\,(n+1)(n+2)}{6}[/tex].
And indeed V(15) = 680.

Edit: OK, folks, you have been faster.[/QUOTE]

That is what I was looking for, tyvm.

[QUOTE=bcp19;290167]Actually, that may work...
1+3+6+10+15+21+28+36+45+55+66+78+91+105+120=680

yep, that works... I was thinking 15x15,14x14, etc but it went well over 1k.

With the levels now known, without using trial and error, is there an actual equation that would solve this?[/QUOTE]The term you need is [I]tetrahedral number[/I]. That's the three-dimensional extension of [I]triangular number[/I].

MathWorld is your friend for such things.

[URL]http://mathworld.wolfram.com/TetrahedralNumber.html[/URL]

But pyramids can be constructed with bases of more than three sides. The general term is [I]pyramidal number[/I], and some particular cases are:

[I]tetrahedral number[/I] (3-sided base)
[I]square pyramidal number[/I] (4-sided base)
[I]pentagonal pyramidal number[/I] (5-sided base)
[I]hexagonal pyramidal number[/I] (6-sided base)
[I]heptagonal pyramidal number[/I] (7-sided base)

[URL]http://mathworld.wolfram.com/PyramidalNumber.html[/URL]

[URL]http://mathworld.wolfram.com/TetrahedralNumber.html[/URL]
[URL]http://mathworld.wolfram.com/SquarePyramidalNumber.html[/URL]
[URL]http://mathworld.wolfram.com/PentagonalPyramidalNumber.html[/URL]
[URL]http://mathworld.wolfram.com/HexagonalPyramidalNumber.html[/URL]
[URL]http://mathworld.wolfram.com/HeptagonalPyramidalNumber.html[/URL]

Do we also have "conical numbers"?

[QUOTE=Christenson;291242]Do we also have "conical numbers"?[/QUOTE]Maybe: [url]http://www.physorg.com/news97227410.html[/url]