what number pyramids have one unique solution?

Question

Question

I came up with this question myself, so I don't know if it has a (nice) solution.

Consider number pyramids like this one, where two neighbouring numbers added are equal to the one on top of them. Only some of them are filled in, though.

If we are given a number pyramid of size n, and at least n spots where numbers have been put in so that it has at least one valid solution, how can we determine if it has one solution or infinitely many?

Example

We are given a pyramid of size 4 where the following spots have been filled in

          --------
          |Filled|
       ---------------
       |      |      |
   -----------------------
   |      |Filled|      |
-----------------------------
|Filled|      |      |Filled|
-----------------------------

For example they could be filled like this

          ---------
          |   15  | 
       ---------------
       |      |      |
   -----------------------
   |      |   3   |      |
-----------------------------
|   1  |      |      |   5  |
-----------------------------
Wich leads to infinitely many solutions:
          ---------
          |   15  | 
       ---------------
       | 4+a  | 11-a |
   -----------------------
   |  1+a |   3   |  8-a |
-----------------------------
|   1  |  a   |  3-a |   5  |
-----------------------------

Infact, all solvable pyramids of this kind have infinitely many solutions.

One idea I have is to interpret this pyramid as a system of linear equations with n(n+1)/2 variables. I do not now how to use this idea, though.

Answer 1

You can test whether the values uniquely determine a pyramid solution by testing whether a certain matrix is invertible.

Theorem. Consider a pyramid with height $h$ and $m\equiv h(h+1)/2$ nodes. Define the $h\times m$ ancestral path matrix $N$ as follows:

$$N_{i,j} = \text{number of distinct upward paths from the }i\text{th leaf node to node }j.$$

In other words, if you express each node's value as a sum involving just the values of the leaf nodes, $N_{i,j}$ is the coefficient of the $j$th leaf in the sum defining the value of the $i$th node. (More intuitively, each row of $N_{i,j}$ records the values of the nodes in the pyramid when one base node has value 1 and the other base nodes have value 0. These are primitive cases; every valid solution is made of multiples of these; they're a basis for the solution space.)

(!) If you fill in $h$ values of a pyramid, then those values form a unique solution to the pyramid if and only if the corresponding $h$ columns of $N$ are linearly independent.

(Note: So the uniqueness is determined solely by the placement of the $h$ variables; their values may be chosen freely.)

---

For example, the ancestral path matrix for height $h=3$ looks like: $$\begin{bmatrix}1&1&&1&&\\2&1&1&&1&\\1&&1&&&1\end{bmatrix}$$

(In this basis, variables are listed in "topological" order, where higher nodes come before lower nodes.) You can pick any $h=3$ columns of this matrix, corresponding to filling in any $h$ variables. Those columns are linearly independent if and only if filling in those variables will uniquely determine a solution.

---

Proof. A pyramid defines a homogeneous system of equations. This system can be represented as a matrix $A$. You can find a basis for the solution space by forming the augmented matrix $[A^T|I]$ and reducing it using Gaussian elimination, forming a matrix $[M | N^\prime]$. The rows of $N^\prime$ corresponding to all-zero rows of $M$ comprise a basis for the solution space (null space) of $A$. Call that submatrix $N$.

For the system of equations defining a pyramid, it is easy to prove that the null matrix $N$ is the ancestral path matrix of the pyramid. (This is because row reduction of $[A^T | I]$ always happens in a straightforward way; starting from the top of the pyramid, each parent row is added to all of its child rows. After this process is complete, the matrix is in reduced form.)

If $h$ columns of the null matrix are linearly independent, then those variables uniquely determine a solution, as described in my answer here: How to define pivot columns? .

---

So you can determine whether a certain set of filled in values uniquely determines a solution by selecting the corresponding columns of $N$, and computing the determinant of that submatrix. That set of values uniquely determines a solution if and only if the determinant is non-zero.

Answer 2

Let $x_v$ be the value of cell $v$ in the pyramid in a solution, and let $c_v$, for $v \in V$, be the given fixed values. The $x_v$ are goverened by the equations $$ x_v = x_{\ell(v)} + x_{r(v)}, $$ where $\ell(v),r(v)$ are the two children of $x_v$.

After substituting the values $c_v$ for $x_v$, you get an inhomogeneous linear system with one variable per each unfilled cell. If the rank of the system equals the number of variables, then there will be a unique solution, and otherwise there will be infinitely many solutions.

As an example, let us denote the cells in your pyramid as $1,\ldots,10$, reading from top to bottom and from left to right. We get the following system: $$ \begin{align} 15 &= x_2 + x_3 \\ 3 &= x_2 - x_4 \\ 3 &= x_3 - x_6 \\ 1 &= x_4 - x_8 \\ 3 &= x_8 + x_9 \\ 5 &= x_6 - x_9 \end{align} $$ This is a set of 6 equations in 6 unknowns. However, the constraints are not linearly independent, since $$ (x_2+x_3)-(x_2-x_4)-(x_3-x_6)-(x_4-x_8)-(x_8+x_9)-(x_6-x_9) = 0. $$ The rank of the system is 5, and so there is a 1-dimensional space of solutions.

Answer 3

Pyramid of size n will have exactly $\dfrac{n(n+1)}{2} = \dfrac{n^2}{2} + \dfrac{n}{2}$ variables and exactly $\dfrac{n(n-1)}{2} = \dfrac{n^2}{2} - \dfrac{n}{2}$ equations. Note that variables in the bottom-most row do not create any new equations but rest all do. So we have exactly $(\dfrac{n^2}{2} + \dfrac{n}{2}) - (\dfrac{n^2}{2} - \dfrac{n}{2}) = n $ extra free variables. Which when we fill up makes number of unknowns same as number of equations.

Unique solution is possible if the row vectors associated with the equations are linearly independent, otherwise not.

For this size 4 pyramid we have $(4*5)/2=10$ variables and $(3*4)/2 = 6$ equations. When we choose the 4 free variables, as is done here (15,3,1,5) in a particular way we get 6 unknowns and 6 equations.

$a_1+a_2+0+0+0+0 = 15--(1)\\ a_1+0-a_3+0+0+0 = 3--(2)\\ 0+a_2+0-a_4+0+0 = 3--(3)\\ 0+0+a_3+0-a_5+0 = 1--(4)\\ 0+0+0+a_4+0-a_6 = 5--(5)\\ 0+0+0+0+a_5+a_6 = 3--(6)$

Now the row vectors associates with this are linearly dependent. We get the last row vector as a linear combination of others, that indicates when we solve the first five equations we always get $0+0+0+0+a_5+a_6 = k$ for some k. So unique solution is not possible. For solutions to exist values at the right side of the equation also should match, here k should be equal to 3, which is true here, so infinitely many solutions exist. If $k\ne 3$ then no solution exist. Here as k = 3, solutions exist and we can choose any value for $a_5$ that will give a value for $a_6$ and from this systematically we can get all other values.

Answer 4

Here are some observations:

1. You can fill in all but $n$ values and still have an undetermined solution:

2. You can get an overdetermined system with as few as three values:

3. It takes at most $n$ values to completely, uniquely determine the rest.

4. Here's a useful question: what is the maximum number of spaces you can freely fill in? How many— and which —spaces can you fill in such that (1) the resulting pyramid has a unique solution, but (2) if you remove any of your specified values, the pyramid no longer has a unique solution.

   For example, you can fill in the bottom row of $n$ spaces. This determines the entire pyramid, and if you erase any of those spaces, the pyramid no longer has a unique solution. Can you fill in more than $n$ spaces somewhere and still have this property?

   By a dimensionality argument, it turns out that for any pyramid, you can fill in at most $n$ spaces before the rest are all determined. Free pyramids have exactly $n$ independent spaces filled in. It doesn't have to be the bottom row, but it also cannot just be anywhere; here are all of the fully specified pyramids for $n=3$:

   For any pyramid (in this case $n=3$), if your filled in values match a free pyramid, the problem is guaranteed to have exactly one solution, no matter what values you've chosen. If you've filled in a superset of these values, the problem either has one solution (if you chose those values consistently), or no solution at all. If you've filled in a subset, the problem has infinitely many solutions. If you've filled in some other subset of values, all bets are off: the problem may have no solution, or infinitely many solutions, or one.

---

I note that if you represent the summation requirement as a homogeneous system of equations $A$, the null space of that matrix has a basis comprised of the "ancestral graphs" of the leaves. (My term: the ancestral graph of a leaf is a vector where the $i$th entry is the number of paths from the leaf to the root passing through node $i$.) The filled-in solutions that uniquely determine the whole pyramid have some relation to the null space, but I haven't determined exactly what.