Mediterranean Mathematics Competition

Denote by $X$ the set of all matrices with entries in the set $\{1,2,3,...,p\}$ and let $A_i$, respectively $B_j$, the set of matrices in which the sum of elements in the row $i$, respectively on the column $j$, be divisible by $p$. Then we have to obtain the cardinality $N$ of the set $$X\setminus \left(\left(\bigcup _{i=1}^m{A}_i\right)\cup \left(\bigcup _{j=1}^n{B}_j\right)\right).$$ For this we apply the inclusion-exclusion principle. Then $$N=p^{mn}+\sum _{i=0}^m\sum _{j=0}^n(-1{)}^{i+j}\sum _{\begin{array}{c}{k}_1<k_2<\cdots <k_i\\ l_1<l_2<\cdots <l_j\end{array}}|A_{k_1}\cap A_{k_2}\cap \cdots \cap A_{k_i}\cap B_{l_1}\cap B_{l_2}\cap \cdots \cap B_{l_j}|(i)$$ the sum being taken for all $i,j$ with $i+j\ne 0$. But we have $$|A_{k_1}\cap A_{k_2}\cap \cdots \cap A_{k_i}\cap B_{l_1}\cap B_{l_2}\cap \cdots \cap B_{l_j}|=|A_1\cap A_2\cap \cdots \cap A_i\cap B_1\cap B_2\cap \cdots \cap B_j|(ii)$$ and moreover $$p^{mn}=(-1{)}^{0+0}(\genfrac{}{}{0ex}{}{m}{0}\left)\right(\genfrac{}{}{0ex}{}{n}{0})p^{mn-0-0}.$$ For all $i,j$ participating in the summation we have $$|A_1\cap A_2\cap \cdots \cap A_i\cap B_1\cap B_2\cap \cdots \cap B_j|=\{\begin{array}{ll}{p}^{mn-i-j},& \text{if }i\ne m\text{ or }j\ne n\\ p^{mn-m-n-1},& \text{if }i=m\text{ and }j=n\end{array}$$ So, $$\begin{array}{rl}N& =\sum _{i=0}^m\sum _{j=0}^m\sum _{i+j\ne m+n}(-1{)}^{i+j}(\genfrac{}{}{0ex}{}{m}{i}\left)\right(\genfrac{}{}{0ex}{}{n}{j})p^{mn-i-j}+(-1{)}^{m+n}\left(\genfrac{}{}{0ex}{}{m}{m}\right)\left(\genfrac{}{}{0ex}{}{n}{n}\right)p^{mn-m-n+1}=\\ & =\sum _{i=0}^m\sum _{j=0}^m(-1{)}^{i+j}(\genfrac{}{}{0ex}{}{m}{i}\left)\right(\genfrac{}{}{0ex}{}{n}{j})p^{mn-i-j}-(-1{)}^{m+n}\left(\genfrac{}{}{0ex}{}{m}{m}\right)\left(\genfrac{}{}{0ex}{}{n}{n}\right)p^{mn-m-n}+\\ & +(-1{)}^{m+n}(\genfrac{}{}{0ex}{}{m}{m}\left)\right(\genfrac{}{}{0ex}{}{n}{n})p^{mn-m-n+1}=\end{array}$$ ---

$$\begin{array}{rl}& =\sum _{s=0}^{m+n}(-1{)}^s{p}^{mn-s}\sum _{i+j=s}(\genfrac{}{}{0ex}{}{m}{i}\left)\right(\genfrac{}{}{0ex}{}{n}{j})+(-1{)}^{m+n}\left(\genfrac{}{}{0ex}{}{m}{m}\right)\left(\genfrac{}{}{0ex}{}{n}{n}\right)p^{mn-m-n}(p-1)=\\ & =p^{mn}\sum _{s=0}^{m+n}{\left(\frac{-1}{p}\right)}^s\left(\genfrac{}{}{0ex}{}{m+n}{s}\right)+(-1{)}^{m+n}{p}^{mn-m-n}(p-1)=\\ & =p^{mn}\left({\left(-\frac{1}{p}\right)}^{m+n}+(-1{)}^{m+n}(\genfrac{}{}{0ex}{}{m}{m}\left)\right(\genfrac{}{}{0ex}{}{n}{n})p^{mn-m-n}(p-1)\right)=\\ & =p^{mn-m-n}\left((p-1{)}^{m+n}+(-1{)}^{m+n}(p-1)\right)\end{array}$$ $$