Faster solution to puzzle: fill table with results of multiplication signs

Question

Fill + or - in the blank squares below so that:

• for each row, the sign in the rightmost (gray) column is the result of the multiplication of the signs in the row
• for each column, the sign in the bottom (gray) row is the result of the multiplication of the signs in the column

The rule is the same for multiplication, i.e., (-)(+)(-) results in (+)

The problem asks how many distinct solutions are possible to fill the whole grid.

I know that the answer is 4, but is there a faster solution than trying out all combinations?

Answer 1

You can map the problem to a set of linear constraints on a vector space over $\mathbb F_2$ (the finite field of size $2$ where addition is XOR and multiplication is AND). The $+$ signs map to $0$s, the $-$ signs map to $1$s. You have $7$ unknowns and $6$ linear constraints, and you want to find the dimension of the solution space. With

\begin{array}{|c|c|} \hline 0&a_1&a_2&\bf1\\\hline a_3&0&a_4&\bf0\\\hline a_5&a_6&a_7&\bf0\\\hline \bf1&\bf1&\bf1\\\hline \end{array}

your constraints are

$$ \pmatrix{ 1&1&0&0&0&0&0\\ 0&0&1&1&0&0&0\\ 0&0&0&0&1&1&1\\ 0&0&1&0&1&0&0\\ 1&0&0&0&0&1&0\\ 0&1&0&1&0&0&1 } \pmatrix{a_1\\a_2\\a_3\\a_4\\a_5\\a_5\\a_6}=\pmatrix{1\\0\\0\\1\\1\\1}\;. $$

You need to find the rank of the $6\times7$ matrix of constraints. I don’t know how to get Wolfram|Alpha to work over $\mathbb F_2$, but here’s a calculation of the reduced row echelon form using an online matrix tool that works over finite fields. The result is

$$ \pmatrix{ 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 }\;, $$

so as expected the rank is $5$, leaving a $2$-dimensional solution space with $2^2=4$ solutions.

Answer 2

My thinking (which is only one way to do it) is to note: A $-$ result requires an odd number of $-$s and an $+$ result an even number of $-$s.

The middle row, (Blank, +, Blank yields +) requires an even number of $-$s. So either no $-$x or $2 -$s (all $-$s). In either cases both cells must be either both $-$ or both $+$. That is our first choice:

So we start with:

$\begin{array}{|c|c|} \hline +&&&\bf-\\\hline \color{blue}A&+&\color{blue}A&\bf+\\\hline &&&\bf+\\\hline \bf-&\bf-&\bf-\\\hline \end{array}$

Now that leads directly to the The first column (+, A, Blank yields -) requires an odd number of $-$s. So exactly $1-$ and $2+$s. That means whatever $\color{blue}A$ is the third square must be the opposite.

So...

$\begin{array}{|c|c|} \hline +&&&\bf-\\\hline \color{blue}A&+&\color{blue}A&\bf+\\\hline \color{blue}{-A}&&&\bf+\\\hline \bf-&\bf-&\bf-\\\hline \end{array}$

The second column, (Blank, +, Blank yields -) requires an odd number of $-$s, and that can be either of the missing squares and the other missing square must be the opposite. Which one is our second choice.

$\begin{array}{|c|c|} \hline +&\color{red}{B}&&\bf-\\\hline \color{blue}A&+&\color{blue}A&\bf+\\\hline \color{blue}{-A}&\color{red}{-B}&&\bf+\\\hline \bf-&\bf-&\bf-\\\hline \end{array}$

The top row has two of three cells filled so third cell is determined entirely by our second choice:

$\begin{array}{|c|c|} \hline +&\color{red}{B}&\color{red}{-B}&\bf-\\\hline \color{blue}A&+&\color{blue}A&\bf+\\\hline \color{blue}{-A}&\color{red}{-B}&&\bf+\\\hline \bf-&\bf-&\bf-\\\hline \end{array}$

For the final cell, I use a slightly different logic. A $+$ can only result by multiplying two of the same together (either $+\cdot + = +$ or $-\cdot - = +$) and a $-$ can only result from multplying two opposites together (either $-\cdot + = -$ or $+\cdot - = -$). So if we look at the third row we must have the last cell being the same as $\color{blue}{-A}\cdot\color{red}{-B}$.

But if we look at the third column we must have the last cell being the opposite of $\color{red}{-B}\cdot \color{blue}{A}$

so:

$\begin{array}{|c|c|} \hline +&\color{red}{B}&\color{red}{-B}&\bf-\\\hline \color{blue}A&+&\color{blue}A&\bf+\\\hline \color{blue}{-A}&\color{red}{-B}&{\color{blue}{-A}\cdot\color{red}{-B}\text{by row}}\over{-(\color{red}{-B}\cdot \color{blue}{A})\text{by column}}&\bf+\\\hline \bf-&\bf-&\bf-\\\hline \end{array}$

Okay... we have some options depending on how often $\color{blue}{-A}\cdot\color{red}{-B}=-(\color{red}{-B}\cdot \color{blue}{A})$.

If $\color{blue}{-A}\cdot\color{red}{-B}$ always equals $-(\color{red}{-B}\cdot \color{blue}{A})$ then all choices are valid. And as we have two choices for $\color{blue}A$ and two choices for $\color{red}B$ for a total of $4$ solutions.

Or if $\color{blue}{-A}\cdot\color{red}{-B}$ never equals $-(\color{red}{-B}\cdot \color{blue}{A})$ we have a contradiction, and we have $0$ solutions.

Of if $\color{blue}{-A}\cdot\color{red}{-B}$ sometimes equals $-(\color{red}{-B}\cdot \color{blue}{A})$ depending on the options of $\color{blue}A$ or $\color{red}B$ we may have $1$ or $2$ solutions depending on the number of possible solutions to $\color{blue}{-A}\cdot\color{red}{-B}=-(\color{red}{-B}\cdot \color{blue}{A})$.

As $\color{blue}{-A}\cdot\color{red}{-B}$ always equals $-(\color{red}{-B}\cdot \color{blue}{A})$ we have four solutions.