If you paint the six sides of a 3x3x3 cube and then slice it into 27 unit cubes, how many will have paint on 0, 1, 2, 3 of their square sides?
Generalize to any dimension:
If you paint the sides of a n dimensional cube with sides length 3 and slice it into 3n unit cubes, how many will have paint on 0, 1, 2, ..., n of their (n-1) dimensional sides?
Paint on 0 sides will of course be limited to just the one central (hyper)cube.
Those with 1 side painted will be those which are at the center of one of the n-dimensional cube's (n-1)-dimensional faces. Two sides will be painted on each of the cubes that lie along one of the (n-2)-dimensional edges (using terminology based on the 3-dimensional cube as an example). Three sides will be painted on each of the cubes that lie on the bound that has (n-3) dimensions.
So the question becomes: how many of each lower dimension bound exist for a hypercube of n dimensions. In going from one dimension to the next, each 0-dimensional point is doubled. The number of 1-dimensional sides is doubled plus each of the 0-dimensional points traces out a 1-dimensional line. This continues as each dimension n+1 has its number of k-dimensional units equal to twice that of dimension n plus dimension n's number of (k-1)-dimensional units.
dimensions elements' dimensions
of
hypercube 0 1 2 3 4 5 6 7 8
2 4 4 1
3 8 12 6 1
4 16 32 24 8 1
5 32 80 80 40 10 1
6 64 192 240 160 60 12 1
7 128 448 672 560 280 84 14 1
8 256 1024 1792 1792 1120 448 112 16 1
so for example the 8-dimensional hypercube will have 1 hypercubelet with no paint, 16 with one hyperface painted, 112 with two, 448 with three, etc.
The Wikipedia article on Hypercube gives the formula for the number of m-dimensional hypercubes on the boundary of an n-dimensional hypercube as:
2^(n-m)*C(n,m)
This checks against the table.
This needs to be translated into a formula for k = 0, 1, ..., n of their (n-1) dimensional sides being painted.
k + m = n
m=n-k
2^(k+m-m)*C(k+m,m) = 2^(k)*C(n,n-k) is then the number of k-painted-sided n-dimensional cubelets.
Take the case of 3 dimensional cubelets with two painted faces:
2^(2)*C(3,1) = 4*3 = 12.
Edited on March 5, 2015, 3:44 pm
|
|
Posted by Charlie
on 2015-03-05 15:41:41 |
solution
