Yet another structure of cubes

https://brilliant.org/problems/yet-another-structure-of-cubes/

First, to preserve my sanity, let's convert images to something more friendly. Consider the following example structure:

The above structure is viewed slightly off from perfectly above the structure. This shows how the structure is composed of stacks; nonexistent stacks are simply stacks of height 0 (marked asterisk below). This also allows us to represent the above succinctly as a single matrix of their heights:

$\begin{pmatrix} 1 & 2 & 2 \\ 3 & 1 & * \\ 3 & 2 & 3 \end{pmatrix}$

Call the above matrix as the height matrix of the example structure. Thus, for our problem, the height matrix of our structure will be this, for some positive integers $a_{ij}$ :

$\begin{pmatrix} a_{11} & * & * & * & * & * & * \\ a_{21} & a_{22} & * & * & * & * & * \\ a_{31} & a_{32} & a_{33} & * & * & * & * \\ a_{41} & a_{42} & a_{43} & a_{44} & * & * & * \\ a_{51} & a_{52} & a_{53} & a_{54} & a_{55} & * & * \\ a_{61} & a_{62} & a_{63} & a_{64} & a_{65} & a_{66} & * \\ a_{71} & a_{72} & a_{73} & a_{74} & a_{75} & a_{76} & a_{77} \end{pmatrix}$

Now, what restrictions do the two pictures from the front and from the right give?

However, instead of deducing the structure from the pictures, it's better to do the other way around first: given the structure, what are the pictures? Given the example structure above, what is the picture from the front? From the right? Let's fix our attention to the one from the front first, since the two are actually similar (rotating the structure allows the right side to be the front side).

First, observe that when looking from the front, gravity affects the situation: all cubes must be supported. Any higher cubes must be supported with lower cubes. Thus actually we can represent a front picture with a single vector, the heights of the stacks in order.

Next, each column is precisely the visible cubes in the column. But we can claim that this is also the height of the highest stack in the column, for that reason: if there's a higher stack, then some of its high cubes (higher than what's in the picture) would be visible; if there's no stack of that height, then the highest cube in the picture shouldn't have been there. For example, a column of 3 in the picture means there's a stack of height 3 and none higher; if there's one higher, than their 4th-level cube would be visible in the picture, while if there's none of height 3, then there would be no stack that shows a 3th-level cube.

Thus we can now easily construct the front picture of the example structure: it's simply $\begin{pmatrix} 3 & 2 & 3 \end{pmatrix}$ , the maximum number in each column. What about the right picture? It's similar, but we need to be careful: it's the maximum number in each row, but read from bottom to up, giving $\begin{pmatrix} 3 & 3 & 2 \end{pmatrix}$ . You can verify that the above structure indeed gives the following pictures:

Thus, our front and right picture vectors are the same $\begin{pmatrix} 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}$ , which means:

• $\max \{a_{11}, a_{21}, \ldots, a_{71}\} = 7$
• $\max \{a_{22}, a_{32}, \ldots, a_{72}\} = 6$
• ...
• $\max \{a_{77}\} = 1$
• $\max \{a_{71}, a_{72}, \ldots, a_{77}\} = 7$
• $\max \{a_{61}, a_{62}, \ldots, a_{66}\} = 6$
• ...
• $\max \{a_{11}\} = 1$

Now our task is simpler. We have $28$ variables $a_{11}, \ldots, a_{77}$ , each of which taking a positive integer value, and we also have the $14$ equalities above. We need to determine $\max \sum a_i - \min \sum a_i$ .

Let's find the maximum first. This is far easier. $a_{ij}$ is involved in two equalities: $\max \{a_{7j}, a_{6j}, \ldots\} = 8-j$ and $\max \{a_{i1}, a_{i2}, \ldots\} = i$ . Thus $a_{ij} \le 8-j$ and $a_{ij} \le i$ , or $a_{ij} \le \min \{8-j, i\}$ . We can simply compute all $28$ inequalities to give this matrix, where each nonzero entry is the maximum height of the stack there:

$\begin{pmatrix} 1 & * & * & * & * & * & * \\ 2 & 2 & * & * & * & * & * \\ 3 & 3 & 3 & * & * & * & * \\ 4 & 4 & 4 & 4 & * & * & * \\ 5 & 5 & 5 & 4 & 3 & * & * \\ 6 & 6 & 5 & 4 & 3 & 2 & * \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}$

Conveniently, this structure is also a valid structure! We can check that they indeed give the required pictures. Since we already have the maximum possible height for each stack, we also have the maximum possible sum for everything, which is $106$ cubes.

Now we need to find the minimum. We have a few necessities: the first column and the last row must have a stack of height 7, the second column and the second-last row must have a stack of height 6, and so on. For some of these, we can actually satisfy both simultaneously: we can simply set $a_{71} = 7$ to satisfy both the first column and the last row criteria, $a_{62} = 6$ to satisfy the second column and the second-last row, and similarly $a_{53} = 5, a_{44} = 4$ . However, we cannot do so for the two 3-stack equalities: the fifth row and the third column don't have any intersection (it must be empty), so we're forced to have two 3-stacks. Likewise, we have two 2-stacks. The remaining stacks are at least 1 cube high, since they are positive integers. Note that this is also optimal: we need one 7-stack, one 6-stack, one 5-stack, one 4-stack, two 3-stacks, two 2-stacks, and the rest at least 1 cube each, for the described reasons (satisfy criteria, some criteria intersecting at no stack, etc). They total up to $52$ cubes:

$\begin{pmatrix} 1 & * & * & * & * & * & * \\ 1 & 2 & * & * & * & * & * \\ 1 & 1 & 3 & * & * & * & * \\ 1 & 1 & 1 & 4 & * & * & * \\ 1 & 1 & 5 & 1 & 3 & * & * \\ 1 & 6 & 1 & 1 & 1 & 2 & * \\ 7 & 1 & 1 & 1 & 1 & 1 & 1 \end{pmatrix}$

This gives a difference of $106 - 52 = \boxed{54}$ .