Skip to main content
OlympiadHQ

Browse · MathNet

Print

Slovenija 2008

Slovenia 2008 counting and probability

Problem

On every square of an chessboard we write one of the numbers or . Let be the product of all numbers in the row and be the product of all numbers in the column. Assuming , can we choose the numbers in such a way that the sum will be zero? What about ?
Solution
If fill the first row of the board with and all other squares with . Then for all and for all , so

Now, let . We will show that we cannot choose the numbers so that Assume, on the contrary, that this can be done. Obviously, each of and is either or . Let denote the number of negative elements of the set and let be the number of negative elements in . Then and This implies How many s are there on the board? If , then the row contains an odd number of s. If , then this number is even. So, the parity of the number of s is the same as the parity of . A similar argument for the columns shows that the parity of the total number of s is the same as the parity of . So, and have the same parity, which contradicts the equation from above.

When we cannot fill the board with s and s so that
Final answer
For n = 2008: Yes. For n = 2007: No.

Techniques

Invariants / monovariantsCounting two ways