Raymond Zhao

Prisms, N-Cubes, and Counting Cubies

Written April 17, 2020.

Summary

Let \(s \ge 2, 1 \le m \le n\). In this article, we prove the number of \(m\)-coloured pieces in an \(n\)-dimensional \(s^n\) Rubik’s cube is \(2^m{n \choose m}(s-2)^{n - m}\). We use a roundabout approach where we first look at prisms and \(n\)-cubes.

Prisms

Given a regular \(p\)-gonal prism, said prism is comprised of two regular \(p\)-gons, and \(p\) squares. For this polyhedron, three faces meet at a vertex, and two faces meet at an edge. Therefore, we can count up the number of edges by adding up the number of edges per face over all faces, and then dividing by two to avoid double-counting. We can repeat a similar process for the vertices, but divide by three instead.

As a result, we have \((2p + 4p)/2 = 3p\) edges, and \((2p + 4p)/3 = 2p\) vertices for this \(p\)-gonal prism. We also have \(p + 2\) faces.

We can generalize the process of forming prisms to higher dimensions. Given a \(k\)-dimensional polytope \(P\), we can form a \((k+1)\)-dimensional \(P\)-based prism.

However, we need new names to generalize the edges, vertices, and faces. Given a \(k\)-dimensional polytope \(P\), an \(m\)-facet of \(P\) is an \(m\)-dimensional element of \(P\), for \(0 \le m \le k\). For example, given a three-dimensional cube: a \(3\)-facet is the cube itself; a \(2\)-facet is a face of the cube, which is a square; a \(1\)-facet is an edge of the cube, which is a line segment; and a \(0\)-facet is a vertex of the cube, which is a point. If \(m\) is not specified, we assume that we are referring to the \((k-1)\)-facets of polytope \(P\). For example, the facets of a three-dimensional cube are squares.

We call the process of forming a prism from a \(k\)-dimensional polytope \(P\) prismatic extrusion. We call the original \(P\) polytope the original base, and the new \(P\)-shaped base the duplicated base, because one can see prismatic extrusion as duplicating the base, followed by translating the duplicated base away from the original base in a new dimension perpendicular to all current dimensional axes.

Let \(f(P)\) represent the number of facets in a \(k\)-dimensional polytope \(P\). Then, the \(P\)-based prism contains \(2 + f(P)\) facets. Two of the facets are the \(P\)-shaped bases. The rest of the \(f(P)\) facets are \(k\)-dimensional prisms built upon the facets of \(P\).

Let \(v(P)\) represent the number of vertices in a \(k\)-dimensional polytope \(P\). Then, the \(P\)-based prism contains \(2v(P)\) vertices, because other than the base being duplicated during the extrusion, which forms \(v(P)\) additional vertices, there are no new vertices that form.

N-Cubes

An \(n\)-cube is an \(n\)-dimensional cube. A \(0\)-cube is a point, a \(1\)-cube is a line segment, and a \(2\)-cube is a square. For \(n \ge 1\), we can interpret an \(n\)-cube as a regular \((n-1)\)-cube-based prism. We also note that all \(m\)-facets of an \(n\)-cube are themselves \(m\)-cubes, for \(0 \le m \le n\).

Let \(C_n\) denote an \(n\)-cube. Then by the section above, \(f(C_n) = 2 + f(C_{n-1})\), and \(f(C_0) = 0\), for a \(0\)-cube has no facets. Therefore, \(f(C_n) = 2n\), so an \(n\)-cube has \(2n\) facets. Similarly, \(v(C_n) = 2v(C_{n-1})\) and \(v(C_0) = 1\), so an \(n\)-cube has \(2^n\) vertices.

Let \(f_m(P)\) denote the number of \(m\)-facets in a \(k\)-dimensional polytope \(P\). Since \(m\)-facets of an \(n\)-cube are \(m\)-cubes, \(f_m(C_n)\) represents the number of \(m\)-cubes within \(C_n\). By the previous section, we also have \(f(P) := f_{k-1}(P)\).

Lemma 1.1: Let \(n \ge 2, 0 \le m \le n-2\). Then, within an \(n\)-cube, \(n-m\) facets meet per \(m\)-facet.

Proof: We use induction on \(n \ge 2\). For \(n = 2\), we only need to consider \(m = 0\). Facets in this case are edges, and two of these facets meet per vertex, which is a 0-facet. Since \(n - m = 2 - 0 = 2\), the base case holds.

Assume for some \(k \ge 2\) that \(k-m\) \((k-1)\)-facets meet per \(m\)-facet within a \(k\)-cube, where \(0 \le m \le k-2\). We need to show that \((k+1)-m\) \(k\)-facets meet per \(m\)-facet within a \((k+1)\)-cube, where \(0 \le m \le k-1\).

We extrude the \(k\)-cube to form a regular \(k\)-cube-based prism, which is exactly the \((k+1)\)-cube. During this process, we form \(f_{k-1}(C_k)\) new \(k\)-cubes to join the original \(k\)-cube base with its duplicate \(k\)-cube base. These new \(k\)-cubes within the \((k+1)\)-cube join with the bases at their \((k-1)\)-facets, with two \(k\)-cubes per \((k-1)\)-facet. These \(k\)-cubes are also now \(k\)-facets of the \((k+1)\)-cube. By symmetry, we thus have two \(k\)-facets meeting per \((k-1)\)-facet over the entire \((k+1)\)-cube. This result proves the \(m = k-1\) case.

For \(0 \le m \le k-2\), we consider that the \((k-1)\)-facets of the original \(k\)-cube are extruded into \(k\)-facets on the \((k+1)\)-cube. However, the original \(k\)-cube becomes yet another \(k\)-facet on the \((k+1)\)-cube. Therefore, since there were \(k-m\) \((k-1)\)-facets meeting per \(m\)-facet within a \(k\)-cube, there are now \((k-m)+1 = (k+1)-m\) \(k\)-facets meeting per same \(m\)-facet within a \((k+1)\)-cube. By symmetry, this argument applies to all \(m\)-facets within the \((k+1)\)-cube. Therefore, for all \(0 \le m \le k-1\), there are \((k+1)-m\) \(k\)-facets meeting per \(m\)-facet within the \((k+1)\)-cube, so the theorem holds by induction. \(\square\)

Theorem 1.2: For all \(n \ge 0, 0 \le m \le n\), \(f_m(C_n) = 2^{n-m}{n \choose m}\).

Proof: We use induction on \(n \ge 0\). Firstly, \(f_0(C_0) = 1 = 1(1) = 2^{0-0}{0 \choose 0}\), since there is a single 0-cube within a 0-cube, which is the 0-cube itself.

Then, assume for some \(k \ge 0\) that \(f_m(C_k) = 2^{k-m}{k \choose m}\) for all \(0 \le m \le k\). For \(m = k+1\), we have that \(f_{k+1}(C_{k+1}) = 1 = 2^{(k+1)-(k+1)}{k+1 \choose k+1}\) because there is only one \((k+1)\)-cube within a \((k+1)\)-cube, which is the \((k+1)\)-cube itself. From an earlier result, we also know for \(m=k\) that \(f_k(C_{k+1}) = f(C_{k+1}) = 2(k+1) = 2^{(k+1)-k}{k+1 \choose k}\).

Lastly, for \(0 \le m \le k-1\), we multiply the number of \(k\)-facets within the \((k+1)\)-cube by the number of \(m\)-facets within each \(k\)-facet. By Lemma 1.1, \((k+1)-m\) \(k\)-facets meet per \(m\)-facet, so we have to divide by \((k+1)-m\) to avoid counting duplicates, Therefore, for \(0 \le m \le k - 1\), we have

Therefore, for all \(0 \le m \le k+1\), \(f_m(C_{k+1}) = 2^{(k+1)-m} {k+1 \choose m}\), so the theorem holds by induction. \(\square\)

Counting Facets in Grids

Let \(s \ge 1, n \ge 0\). Then, we can partition a single \(n\)-cube into an \(s^n\) grid of \(n\)-cubes. Let \(C_n\) represent the original \(n\)-cube, and \(G_n\) represent the corresponding \(s^n\) grid. For \(n = 0\), nothing happens; \(C_0 = G_0\). For \(n = 1\), \(G_1\) is a line segment (\(C_1\)) partitioned into \(s\) line segments. When \(s=1\), \(C_n = G_n\), so we can ignore this case. We set \(s \ge 2\).

Lemma 2.1: Let \(n \ge 0, 0 \le m \le n, s \ge 2\). Then, there are \((s-2)^m\) \(n\)-cubes in \(G_n\) per \(m\)-facet in \(C_n\).

Proof: Let \(s \ge 2\). We use induction on \(n \ge 0\). For \(n = 0\), we only consider \(m = 0\). There is \(1 = (s-2)^0\) \(0\)-cube in \(G_0\) per \(0\)-facet in \(C_0\), so the base case holds.

Assume for some \(k \ge 0\) that there are \((s-2)^m\) \(k\)-cubes in \(G_k\) per \(m\)-facet in \(C_k\), where \(0 \le m \le k\). We want to show that there are \((s-2)^m\) \((k+1)\)-cubes in \(G_{k+1}\) per \(m\)-facet in \(C_{k+1}\), where \(0 \le m \le k+1\).

For any \(m\) where \(0 \le m \le k\), there are \((s-2)^m\) \(k\)-cubes in \(G_k\) corresponding to an \(m\)-facet in \(C_k\). When \(G_k\) is extruded, and partitioned along the new axis, to form \(G_{k+1}\), those \((s-2)^m\) \(k\)-cubes become \((s-2)^m\) \((k+1)\)-cubes in \(G_{k+1}\), representing an \(m\)-facet in \(C_{k+1}\). By symmetry, this applies to all \(m\)-facets in \(C_{k+1}\), so there are \((s-2)^m\) \((k+1)\)-cubes in \(G_{k+1}\) per \(m\)-facet in \(C_{k+1}\) for \(0 \le m \le k\). We still have to show the statement holds for \(m = k+1\).

By the inductive hypothesis, there are \((s-2)^k\) \(k\)-cubes in \(G_k\) corresponding to the one \(k\)-facet in \(C_k\). Let \(B_k\) represent those \((s-2)^k\) \(k\)-cubes. When \(G_k\) is extruded, and partitioned along the new axis, to form \(G_{k+1}\), the total hypervolume of the \(B_k\)-based prism within \(G_{k+1}\) is now \((s-2)^ks\) \((k+1)\)-cubes. Because both the original \(B_k\) base and the duplicated \(B_k\) base now represent \(k\)-facets of \(C_{k+1}\), we subtract 2 from the height of the \(B_k\)-based prism to obtain a final total of \((s-2)^k(s-2) = (s-2)^{k+1}\) \((k+1)\)-cubes in \(G_{k+1}\) that correspond to the one \((k+1)\)-facet in \(C_{k+1}\). \(\square\)

Counting Cubies in Rubik’s Cubes

We only consider \(n \ge 3\) in this section, because Rubik’s cubes require at least three dimensions to turn. We also force \(s \ge 2\) to eliminate \(0^n\) and \(1^n\) Rubik’s cubes from the scope of this article. For reference, pieces of Rubik’s cubes are called cubies. We assume that for these \(s^n\) Rubik’s cubes, each \((n-1)\)-facet is assigned a unique colour.

Lemma 3.1: Let \(n \ge 3, s \ge 2\). Let \(H_n\) represent a \(G_n\) with the \(n\)-cubes representing the \(n\)-facet of the \(C_n\) removed. There is a bijection between \(m\)-coloured cubies on an \(s^n\) Rubik’s cube, and \(n\)-cubes in \(H_n\) representing \((n-m)\)-facets in \(C_n\), for \(1 \le m \le n\).

Proof: Firstly, \((n-m)\)-facets in a \(C_n\) are well-defined in this case since \(1 \le m \le n\) implies \(0 \le n-m \le n-1\).

We note that the cubies of an \(s^n\) Rubik’s cube are essentially a coloured version of \(H_n\), meaning the cubies map one-to-one and onto the \(n\)-cubes within \(H_n\).

By Lemma 1.1, there are \(n-m\) facets meeting per \(m\)-facet in \(C_n\). Therefore, a cubie \(c\) that maps to an \(n\)-cube in \(H_n\) representing an \(m\)-facet in \(C_n\) has \(n-m\) colours, because each facet of the \(C_n\) meeting at that \(m\)-facet is equivalent to adding a colour onto cubie \(c\). By symmetry, a cubie on the \(s^n\) Rubik’s cube that maps to an \(n\)-cube in \(H_n\) representing an \((n-m)\)-facet in \(C_n\) has \(n-(n-m) = m\) colours. \(\square\)

Theorem 3.2: Let \(n \ge 3, 1 \le m \le n, s \ge 2\). The number of \(m\)-coloured pieces in an \(s^n\) Rubik’s cube is \(2^m{n \choose m}(s-2)^{n - m}\).

Proof: By Theorem 1.2, \(f_{n-m}(C_n) = 2^{n-(n-m)}{n \choose n-m} = 2^m{n \choose m}\). By Lemma 2.1, there are \((s-2)^{n-m}\) \(n\)-cubes in \(G_n\) per \((n-m)\)-facet in \(C_n\). Thus, there are \(f_{n-m}(C_n)(s-2)^{n-m}\) \(n\)-cubes in total in \(G_n\) that represent the \((n-m)\)-facets in \(C_n\).

Since \(1 \le m \le n\), we are only considering \(0 \le n-m \le n-1\). Thus, we can substitute \(G_n\) with \(H_n\), and not lose any \(n\)-cubes in the process. By Lemma 3.1, \(n\)-cubes in \(H_n\) that represent \((n-m)\)-facets in \(C_n\) then map to \(m\)-coloured pieces on the \(s^n\) Rubik’s cube, so the number of \(m\)-coloured pieces in an \(s^n\) Rubik’s cube is \(f_{n-m}(C_n)(s-2)^{n-m} = 2^m{n \choose m}(s-2)^{n-m}\). \(\square\)

Corollary 3.3: Let \(n \ge 3\). The number of cubies in a \(2^n\) Rubik’s cube is \(2^n\), and they are all \(n\)-coloured pieces.

Proof: \(s = 2\) in this case. By Theorem 3.2, only for \(m = n\) does \((s - 2)^{n-m} = 0^0 = 1 \ne 0\), meaning the \(2^n\) Rubik’s cube consists solely of \(2^n{n \choose n}(s-2)^{n-n} = 2^n(1)(1) = 2^n\) \(n\)-coloured pieces. \(\square\)

Corollary 3.4: Let \(n \ge 3, 1 \le m \le n\). The number of \(m\)-coloured pieces in a \(3^n\) Rubik’s cube is \(2^m{n \choose m}\).

Proof: \(s = 3\) in this case, so \(s - 2 = 1\). By Theorem 3.2, we thus obtain \(2^m{n \choose m}(1)^{n - m} = 2^m{n \choose m}\) \(m\)-coloured pieces in a \(3^n\) Rubik’s cube. \(\square\)