4
$\begingroup$

Consider an $11$ x $11$ grid, where in each square, the number $1$ or $-1$ is written. One multiplies the numbers in each row and column, and then sums up these $22$ products. Is it possible for this sum to be equal to $0$?

My approach was to realize that the product in every row or column is either $1$ or $-1$. This means, since we have $22$ products, that $11$ of them must be equal to $1$ and the other $11$ to $-1$. If there is an odd number of $-1$:s in a row or column, the product will be $-1$, while if there is an even number of $-1$:s, the product will be $1$. Then, I considered coloring each square in the following way: black if the cell contains a $-1$, uncolored if the cell contains a $1$. Thus, the question becomes: can one color grid cells in an $11$ x $11$ grid in such a way that an odd number of cells is colored in $11$ rows/columns, and an even number of cells is colored in the remaining $11$ rows/columns? However, from here, I couldn't make much progress. Does anyone have any ideas?

$\endgroup$
4
  • $\begingroup$ Can you work out the answer in a smaller grid? 2x2? 3x3? $\endgroup$
    – JMP
    Commented Jan 31, 2023 at 7:53
  • 1
    $\begingroup$ @JMP, well it doesn't work for a 2x2, but I don't really know how to prove it for a 3x3... maybe you can prove that it works differently for an $n$x$n$ grid if $n$ is even or odd...? $\endgroup$ Commented Jan 31, 2023 at 7:57
  • $\begingroup$ 1/ Are you sure it doesn't work for a 2x2? 2/ Hint: What can you say about the product of all the values in the cells? What about the square of the product? $\endgroup$
    – Calvin Lin
    Commented Jan 31, 2023 at 8:04
  • 1
    $\begingroup$ What about a row of -1 and a row of +1 for 2x2? Or perhaps I don’t understand correctly. $\endgroup$
    – JMP
    Commented Jan 31, 2023 at 8:05

2 Answers 2

8
$\begingroup$

Start with a grid $11\times11$, with $1$ in each square. Total is $22$.

Change $1$ to $-1$ in one square, new total is $18$.

Start with a grid $11\times11$, with random values. Change $1$ value, new total of rows increase or decrease by $2$, new total of columns increase or decrease by $2$, new total of rows+columns change by $-4, 0$ or $+4$.

Total is always equal to $2\pmod 4$. Total cannot be $0$, neither $4$ or $8$ or $12$ ...

$\endgroup$
2
  • $\begingroup$ very clever solution... thank you very much $\endgroup$ Commented Jan 31, 2023 at 8:12
  • $\begingroup$ Nice description of your discovery process, +1. $\endgroup$
    – Joffan
    Commented Jan 31, 2023 at 8:29
1
$\begingroup$

While Lourrran's solution is very nice, I was wish to point out something that feels more natural to me.

Since $121$ is odd, there should an even no. of $+1$ or $-1$.

If the no. of negatives on the board is even, then the no. of rows/columns with odd number of negatives have to be even.

If we denote the no. of rows with odd number of negatives with $R$ and the no. of columns with odd number of negatives to be $C$, then the sum we are interested in is $(11-R)-R+(11-C)-C$. If this sum were zero, this would imply that $2(R+C)=22$ but $R,C$ are both even.

In the other case, take a look at the negation of the whole board. If sum of products of the original board is zero, so is the sum of products on the negated board. This board will have an even no. of negatives. The same argument follows

$\endgroup$
3
  • $\begingroup$ Fixed. Thank you. $\endgroup$ Commented Jan 31, 2023 at 12:30
  • $\begingroup$ "If the no. of negatives on the board is even, then the no. of rows/columns with odd number of negatives have to be even." No. Take the case where we only have two negatives in the first row and nothing else. Then the number of columns with an odd number of negatives is 9, which is not even. $\endgroup$
    – 5xum
    Commented Jan 31, 2023 at 12:38
  • $\begingroup$ But there are only 2 columns with odd number of negatives? I'm not following. Can you elaborate? $\endgroup$ Commented Jan 31, 2023 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .