mersenneforum.org Cube Mountains
 Register FAQ Search Today's Posts Mark Forums Read

 2008-05-28, 18:37 #1 davar55     May 2004 New York City 423310 Posts Cube Mountains Call an "N-mountain" 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 N-mountain (number of layers) can range from 1 to N^2. How many N-mountains 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.))
 2008-05-29, 14:13 #2 davieddy     "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?
 2008-05-29, 18:33 #3 davar55     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.
 2008-05-29, 22:17 #4 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 22·3·17·47 Posts For n=2 I get a quick count of 15.
 2008-05-29, 22:33 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 137778 Posts Isn't this the partition problem in disguise? Or at least a variant of it?
 2008-05-29, 23:50 #6 wblipp     "William" May 2003 New Haven 93916 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 (n-1) 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 n-1} (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.
 2008-05-30, 04:09 #7 wblipp     "William" May 2003 New Haven 3·787 Posts For n even The rotations are easy to calculate from the non-rotation 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 75-3=72 unsymmetric mountains 4 times, the 3-2=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.
2008-05-30, 10:09   #8
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by davar55 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.
If you put one cube on top of another
then lift the top one 1 mm I would describe
the resulting 1 mm thick gap as "horizontal".
Hence my initial confusion.

 2008-05-30, 15:05 #9 wblipp     "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 non-central 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 2008-05-30 at 15:16 Reason: Fixed a calculation error
 2008-06-03, 22:36 #10 nibble4bits     Nov 2005 18210 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+(n-1)^2+(n-2)^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 There is of course an infinite number if you don't limit the base to a finite value. 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+5-2)^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.

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Lounge 110 2018-05-22 03:42 NBtarheel_33 Puzzles 32 2013-09-10 17:37 henryzz Puzzles 12 2012-08-14 19:09 Yamato Math 6 2008-02-25 15:08 mfgoode Homework Help 10 2007-10-05 04:12

All times are UTC. The time now is 17:52.

Tue May 18 17:52:51 UTC 2021 up 40 days, 12:33, 0 users, load averages: 1.83, 1.97, 2.05