20080528, 18:37  #1 
May 2004
New York City
4233_{10} Posts 
Cube Mountains
Call an "Nmountain" an arrangement of unit cubes in layers,
such that the bottom layer is an NxN square (of cubes  I hope that's clear enough), each layer has fewer cubes than any layer below it, and cubes are stacked evenly over cubes (so that vertices of neighboring cubes correspond) and with no vertical gaps. For instance, the "height" of an Nmountain (number of layers) can range from 1 to N^2. How many Nmountains are there, for N=1,2,3,4,5 ? (Don't count rotationally congruent mountains as distinct.) ((That's rotation around the center of the bottom layer.)) 
20080529, 14:13  #2 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
This looks like a messy problem.
Looking at the N=2 case in my head my first query starts at height 2: Can we place a total of two cubes in opposite corners or does this violate your "vertical gaps" rule? Why exclude rotational symmetry and not reflectional? 
20080529, 18:33  #3 
May 2004
New York City
3×17×83 Posts 
I intended the simplest form of this problem,
and must have muddled my intent. In regard to the issue of rotational symmetry, I just meant that if you can rotate a "mountain" thru a quarter or half turn and get the same result, it should only be counted once. I should probably have left the condition out. As to vertical gaps, except for the bottom layer, which must be full of cubes, every cube must be situated over a column of cubes (no gaps vertically) but within a layer any configuration is allowed (so placing cubes in opposite corners, creating "horizontal" gaps, is fine.) Sorry about any confusion. 
20080529, 22:17  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2^{2}·3·17·47 Posts 
For n=2 I get a quick count of 15.

20080529, 22:33  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
13777_{8} Posts 
Isn't this the partition problem in disguise? Or at least a variant of it?

20080529, 23:50  #6 
"William"
May 2003
New Haven
939_{16} Posts 
If we ignore the rotation condition,
Then the square shape of the base is irrelevant, and we can ask about Mountains with "n" blocks in the base. These can be defined recursively. For n blocks, you can chose k = 0 to (n1) blocks for the next level. You can place those k blocks in C(n,k) ways. You can continue building higher in M(k) ways. So M(0)=1 and M(n) = Sum {k=0 to n1} (C(n,k)*M(k)) which has first few values 0 1 1 1 2 3 3 13 4 75  this is the 2x2 base counting rotations as distinct 5 541 6 4683 7 47293 8 545835 9 7087261  this is the 3x3 base Which matches two integer sequences. To answer the actual puzzle, I would need to also need to count the 90 degree and 180 degree rotations to subtract the duplicates. 
20080530, 04:09  #7 
"William"
May 2003
New Haven
3·787 Posts 
For n even
The rotations are easy to calculate from the nonrotation numbers. For 180 degrees, you build any mountain on the front half, then duplicate it on the back half. For 90 degrees, you build any mountain in a quadrant and triplicate it to the other quadrants. For the 2x2 square we have M(4)=75 unrotated mountains, of which M(2)=3 have 180 degree symmetry and M(1)=1 have 90 degree symmetry. Undoing rotations, we have counted the 753=72 unsymmetric mountains 4 times, the 32=2 mountains with only 180 degree symmetry twice, and the 1 90 degree symmetric mountain once, so the answer for 2x2 is 72/4 + 2/2 + 1 = 20. Comparing this to unwilly's count of 15  I think unwilly counted mirror symmetry as identical, too. I sketched out the 20 unique mountains; there are five pairs that are mirror images but cannot be rotated to each other. Continuing the calculation of M(n) through 16, it continues to match the two series. (At M(17), where the series diverge, M(n) matches A000670.) For the 4x4 square, the answer is (M(16)M(8))/4 +(M(8)M(4))/2 +M(2) = 1328913670631835 For odd n you must keep track of the base's central square separately from the other squares. I'm not sufficiently interested to work this out tonight. Perhaps someone else will work out the odd bases. 
20080530, 10:09  #8  
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Quote:
then lift the top one 1 mm I would describe the resulting 1 mm thick gap as "horizontal". Hence my initial confusion. 

20080530, 15:05  #9 
"William"
May 2003
New Haven
3·787 Posts 
For odd n
It's easier to count the symmetric mountains than I has thought. For 180 degrees, you build a mountain on half of the noncentral squares plus the central square. When you rotate that to get a symmetric mountain on the full base, the central square rotates onto itself, but that's OK. The same process works for counting 90 degree symmetric mountains. Hence the number of unique mountains on the 3x3 base is (M(9)M(5))/4 + (M(5)M(3))/2 + M(3) = 1771957 And the 5x5 base has (M(25)M(13))/4 + (M(13)M(7))/2 + M(7) = 26674341359618944088110485277 There's a substantial chance I made an error in calculating M(25). Here are my calculations to check against: 0 1 1 1 2 3 3 13 4 75 5 541 6 4683 7 47293 8 545835 9 7087261 10 102247563 11 1622632573 12 28091567595 13 526858348381 14 10641342970443 15 230283190977853 16 5315654681981355 17 130370767029135901 18 3385534663256845323 19 92801587319328411133 20 2677687796244384203115 21 81124824998504073881821 22 2574844419803190384544203 23 85438451336745709294580413 24 2958279121074145472650648875 25 106697365438475775825583498141 Last fiddled with by wblipp on 20080530 at 15:16 Reason: Fixed a calculation error 
20080603, 22:36  #10 
Nov 2005
182_{10} Posts 
When I was reading this problem, I was initially thinking you meant something like this for c=number of cubes and n=number of layers:
c=n^2+(n1)^2+(n2)^2+...+3^2+2^2+1 In other words the number of cubes is the sum of the squares. Sorry for the pun. It turns out that you seem to be wanting to know the number of combinations to something like this: Code:
n=2 3x3 for bottom 2x2 for top no 1x1 Code:
n=2 3x3 for bottom 1x1 for top Code:
n=3 4x4 for bottom 2x2 for middle 1x1 for top Or did you mean the same cases I provided, but n=3,3, and 4, respectively? It seems that you could also mean that if I had a 2x2 square on top of a 5x5, that there's (1+52)^2=4^2=16 possible positions assuming they're aligned to a grid and always within the area of the layer directly below. Removing rotations and reflections is going to reduce that from 16 to just 3 positions. Removing translations of course reduces it to just one position. Note that these other possible interpretations are interesting problems in their own rights. They're all fun to work on. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Rubik's cube and variations  henryzz  Lounge  110  20180522 03:42 
Perfect Cube Repunits  NBtarheel_33  Puzzles  32  20130910 17:37 
Devil's Number for 2x2x2 Rubik's Cube  henryzz  Puzzles  12  20120814 19:09 
Computing the cube root modulo p  Yamato  Math  6  20080225 15:08 
Cube root  mfgoode  Homework Help  10  20071005 04:12 