Cube-related counting puzzle

[Jorian Meeuse]

Here is a cube-related puzzle: Say you have a lineup of all cubes from 1x1 to NxN with N > 1. Show that the number of piece types* present in this lineup is equal to the number of binary (N-1) x 2-matrices satisfying:

• The binary number in the second column is greater than or equal to that in the first;
• If i<j, then the binary number in the j^th row is greater than or equal to that in the i^ith row;
• There are at least as many 1s in the first column as in the second.

Try to solve this problem without constructing formulas for both and stating they match, because that isn’t really a fun solution.

*innermost centers on odd NxNs do not count as a piece type. The 1x1 piece does count as a piece type.

Spoiler: Possible solution

Write n = N-1 for convenience, and assume the statement holds for a lineup of all 1x1-nxn cubes. There are four possibilities for the last row of a binary nxn-matrix:

• If the last row is (1 1), then the 3 requirements are met if and only if they are met for the (n-1) x 2 matrix above it. Therefore, this possibility accounts for all piece types present in the 1x1-nxn lineup, and we only need to worry about the NxN’s piece types.
• If the last row is (0 0), then every row has to be (0 0) by condition 2, so this gives 1 valid matrix, which we will assign to the corners of the NxN.
• The last row can not be (0 1). Since there would be a 1 in the second column, there would need to be one in the first. However, then there needs to be a row equal to either (1 0) or (1 1), both greater than (0 1).
• If the last row is (1 0), we can keep going up a row and setting it to (1 0) as long as we like. There are n-1 possible choices for k, the smallest index such that row k is equal to (1 0), namely any 1 < k < N (if k = 1, the second column reads 0 < 2^n – 1). We distinguish 2 cases:
  • 1 < k <= ceil(n/2). This guarantees condition 3. There are k-1 rows above row k, of which at least 1 and at most k-1 have to be (0 1). This brings a total of \sum_{k = 2}^{ceil(n/2)}(k-1) = 1/2*(ceil(n/2)^2-ceil(n/2)) possible matrices.
  • Ceil(n/2) < k < N. Now condition 3 requires that at most N – k of the rows above row k are equal to (0 1). Still, at least one has to be, so there are N – k possible choices, for a total of \sum_{k = ceil(n/2)+1}^{n-1}(n-k+1) = 1/2*(n – ceil(n/2))(-ceil(n/2)+n+1) valid matrices. Therefore, the option that the last row is (1 0) gives ceil(n/2)^2 – (n+1)*ceil(n/2) + (n^2+n)/2 possibilities total.

Now we need to show that the number of edge + center types on the NxN is equal to ceil((N-1)/2)^2 – N*ceil((N-1)/2) + (N^2-N)/2. There are 2 cases:

• N is odd, in which case the expression simplifies to ((N-1)/2)^2. The following shows that this is equal to the number of edge + corner types on the NxN: look at the U face of the cube, and take the square at the bottom right of the innermost center. The (N-3)/2 wings on the UF edge accounts for all wing types. The ((N-3)/2)^2 centers are all of different type. The remaining (N-3)/2 center types (those directly below the innermost center) are accounted for by the wings on the UR edge. The UFR corner represents the midges.
• N is even, in which case the expression simplifies to (N/2)^2 – N/2. This is indeed equal to the number of edge+center types on the NxN: look again at the bottom-right square on the U face, but this time take away the corner and right-side wings. This accounts for each edge and center type, and its size is precisely (N/2)^2 – N/2

So far, we have shown that if the claim is true for some N, then it is true for N + 1. The last thing that remains is to check that the statement holds for N=2. In this case, there are 2 piece types in the lineup: the 1x1 piece, and the corners of the 2x2. The only binary 1x2-matrices that exist are (0 0), (1 1), (0 1), (1 0). The first two meet all requirements. The third fails at requirement 3, and the last at requirement 1, so indeed the case N=2 holds. Therefore, the statement inductively holds for all N > 1. In fact, it also holds for N=1 if you agree that there exists a 0x2-matrix.