In each square of a $4$ by $4$ grid, you put either a $+1$ or a $-1$. If any 2 rows and 2 columns are deleted, the sum of the remaining 4 numbers is nonnegative. What is the minimum number of $+1$'s needed to be placed to be able to satisfy the conditions
Problem
Source: 2018 China North Mathematical Olympiad Grade 10 Test 1 P4
Tags: combinatorics, China, Find maximum
31.05.2019 15:04
I think I have proved that the answer is $10$. Such an example is: \begin{tabular}{|c|c|c|c|}\hline $-$1&$-$1&$-$1&1\\\hline 1&1&1&$-1$\\\hline 1&1&1&$-1$\\\hline 1&1&1&$-1$\\\hline\end{tabular}
04.08.2019 08:00
RANDOMMATHLOVER wrote: I think I have proved that the answer is 10. Example with 10 (+)1s : 1st row —1 —1 —1 1 2nd row 1 1 1 —1 3rd row 1 1 1 —1 4th row 1 1 1 —1 How do you know that that's the minimum?
04.08.2019 09:36
We will show that the maximum number of $-1$'s we can have is $6$. For the constructive part, take any row and any column. Fill them up with $-1$'s except for their intersection. Then, fill the rest with $+1$'s. Now, take any grid with largest number of $-1$'s. Given condition is equivalent to the following "Take any four squares whose centres form a rectangle (not slanty squishy ones), then there are at most two $-1$'s in these squares." If every row had at most one $-1$'s, then there will only be four $-1$'s on the grid and this contradicts our maximlaity assumption as we have given a example with six $-1$'s. Thus, there is some row with at least two $-1$'s. Take those two (say $a$ and $b$) and note that no more $-1$'s can be on the columns containing these two. Similarly, we can find two $-1$'s (say $c$ and $d$) on a same column and there are no more $-1$'s on the rows containing them. Removing the columns containing $a, b$ and rows containing $c, d$, we are left with four squares forming a rectangle. Then, agian, we know that there are at most two $-1$'s on these four squares. Hence, altogether, there are at most six $-1$'s on the maximal grid and we're done. I'm sorry for my vague and bad proof writing. XD
04.08.2019 09:46
I welcome you all to join MARS where actually I've posted optimized determinant conjecture which requires more well defined and mathematical arguments. It's not simply grids I see, it's a determinant which you all are trying to optimize.