16th Junior Turkish Mathematical Olympiad

For $1\le i\le 20$ and $1\le j\le 11$ we define $a_{i,j}$ as follows; $a_{i,j}=1$ if the $i$-th mathematics problem and $j$-th physics problem are chosen by some student, $a_{i,j}=0$ otherwise. Now we can reformulate the problem: Find the maximal possible value of the expression $$A=\sum _{i=1}^{20}\sum _{j=1}^{11}{a}_{i,j}\text{ under the following two conditions:}$$ $$\bullet a_{i,j}=0\text{ or }1$$ if $a_{k,l}=1$ for some $k$ and $l$, then at least one of the sums ${\sum }_{j=1}^{11}{a}_{k,j}$ and ${\sum }_{i=1}^{20}{a}_{i,l}$ does not exceed $2$.

First of all, let us show that $A\le 54$. Suppose that $a_{k,l}=1$. We say that $k$ is 1-good*, if $$\sum _{j=1}^{11}{a}_{k,j}\le 2;\text{ we say that }l\text{ is 2-good if }\sum _{i=1}^{20}{a}_{i,l}\le 2.$$ If the total number of 1-good values of $k$ is $20$, then $A\le 2\cdot 20=40$. If the total number of 2-good values of $l$ is $11$, then $A\le 2\cdot 11=22$. If the total number of 1-good values of $k$ is $19$, then $A\le 2\cdot 19+11=49$. If the total number of 2-good values of $l$ is $10$, then $A\le 2\cdot 11+20=32$. Finally, if the total number of 1-good values of $k$ is less than or equal to $18$ and the total number of 2-good values of $l$ is less than or equal to $9$, then the total number of good values is at most $27$ and readily $A\le 2\cdot 27=54$, since the number of nonzero terms of $A$ is less than or equal to twice the number of good values. Thus, $A\le 54$.

Now we give an example for $A=54$. Let $a_{i,j}=1$ only for $$(i,j)\in \{(i,j):i\in \{1,20\}\text{ or }j\in \{1,11\}\}\setminus \{(1,1),(20,1),(1,11),(20,11)\}.$$ The conditions are readily satisfied and we are done.