In each field of 2009*2009 table you can write either 1 or -1. Denote Ak multiple of all numbers in k-th row and Bj the multiple of all numbers in j-th column. Is it possible to write the numbers in such a way that $ \sum_{i=1}^{2009}{Ai}+ \sum_{i=1}^{2009}{Bi}=0$?
Problem
Source: Middle Europe Mathematical Olympiad 2009 TST Second Day Second problem
Tags: combinatorics unsolved, combinatorics
Abnormal Distribution
19.06.2009 18:34
Consider a board with all the numbers already filled in. Any other possible configuration of numbers can be formed by changing numbers one at a time. When a number is changed, it will change the parity of the number of -1s in a row and in a column and will therefore change two of the products. Let's examine the possible effects of changing a number:
1) Two products change from -1 to 1.
Net result: +4
2) Two prodcuts change from 1 to -1.
Net result: -4
3) One product changes from 1 to -1 and the other product changes from -1 to 1.
Net result: no change
Clearly, all possible sums must be congruent mod 4. Since a field completely filled with 1s would yield a sum of 4018, which is not congruent to 0 mod 4, a sum of 0 is impossible.
Matematika
19.06.2009 20:39
Yes it is that easy
kasym
09.12.2009 15:36
Please, teach me to solve this type of problems.
Math_Is_Fun_101
07.05.2022 10:53
Consider what happens when we change one entry. Each sum $\sum A_k,\sum B_k$ increases or decreases by $2$. Therefore, the total sum $\sum A_k+\sum B_k$ changes by a multiple of $4$. In other words, $\sum A_k+\sum B_k$ is invariant mod $4$. However, when all the entries are $1$, this sum is $2\cdot 2009\equiv 2\pmod 4$, so it is impossible. $\blacksquare$