Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Let $p = 5q + 1$, $q \ge 2$, and write $4p = 5(4q + 1) - 1$. Form a $5$-by-$(4q + 1)$ matrix consisting of ones only except for a single entry. Such a matrix has exactly $4p$ ones. A submatrix comprising $r$ rows, $1 \le r \le 5$, and $s$ columns, $1 \le s \le 4q + 1$, contains $rs$ or $rs-1$ ones. In the former case, $rs = 2p$ implies $r \ge p$ or $s \ge p$, because $p$ is prime; in the latter, $rs-1 = 2p$ implies $rs = 2p+1$, so $r = 2p+1$ or $s = 2p+1$, because $2p+1$ is prime. Both cases contradict the size of the matrix, so no submatrix contains exactly $2p$ ones.

Next, write $4p+2 = 5(4q+1)+1$. Now form a $5$-by-$(4q + 1)$ matrix consisting of ones only except for one column that contains only a single one. Such a matrix has exactly $4p + 2$ ones. A submatrix comprising $r$ rows, $1 \le r \le 5$, and $s$ all-one columns, $0 \le s \le 4q+1$, contains $rs$ or $rs+1$ ones. In the former case, $rs = 2p+1$ implies $r = 2p+1$ or $s = 2p+1$ because $2p+1$ is prime; in the latter, $rs+1 = 2p+1$, so either $r \ge p$ or $s \ge p$ since $p$ is prime. Again, this contradicts the size of the matrix and the conclusion follows.