mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-05-28, 18:37   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default 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.))
davar55 is offline   Reply With Quote
Old 2008-05-29, 14:13   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

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?
davieddy is offline   Reply With Quote
Old 2008-05-29, 18:33   #3
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2008-05-29, 22:17   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23×1,109 Posts
Default

For n=2 I get a quick count of 15.
Uncwilly is offline   Reply With Quote
Old 2008-05-29, 22:33   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×653 Posts
Default

Isn't this the partition problem in disguise? Or at least a variant of it?
retina is online now   Reply With Quote
Old 2008-05-29, 23:50   #6
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

92416 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2008-05-30, 04:09   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

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.
wblipp is offline   Reply With Quote
Old 2008-05-30, 10:09   #8
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Quote:
Originally Posted by davar55 View Post
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.
davieddy is offline   Reply With Quote
Old 2008-05-30, 15:05   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001001002 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2008-06-03, 22:36   #10
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

101101012 Posts
Default

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.
nibble4bits is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Rubik's cube and variations henryzz Lounge 110 2018-05-22 03:42
Perfect Cube Repunits NBtarheel_33 Puzzles 32 2013-09-10 17:37
Devil's Number for 2x2x2 Rubik's Cube henryzz Puzzles 12 2012-08-14 19:09
Computing the cube root modulo p Yamato Math 6 2008-02-25 15:08
Cube root mfgoode Homework Help 10 2007-10-05 04:12

All times are UTC. The time now is 12:05.

Wed Nov 25 12:05:38 UTC 2020 up 76 days, 9:16, 4 users, load averages: 1.52, 1.63, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.