Team Selection Test for EGMO, 2024

Only $(p^2, p+1)$.

Obviously $|S_i| = k$ for every $i$. Also note that given conditions imply that for every pair of squares belonging to different columns there exists a unique $S_i$ containing these two squares. Therefore, by a double counting argument we get $\binom{k}{2}p^2 = n\binom{k}{2}$, which yields $n = p^2$.

Let $A$ and $B$ be two different squares in the first column. By the given conditions, if we consider the squares in the second column, we see that there exist exactly $p$ sets containing $A$. Now any set containing $B$ must intersect those $p$ sets in different columns. Thus, we obtain $k \ge p+1$. On the other hand, at each column we must see an intersection as there are $p$ squares in a column and there are $p$ sets containing $A$. Therefore, we can conclude that $k = p+1$.

We next give an example for the sets when $n = p^2$ and $k = p + 1$. In each column numerate the squares from $0$ to $p-1$ from bottom to top. Also numerate the columns from left to right as $0, 1, \dots, p$. For any $a, b \in \{0, 1, \dots, p-1\}$ let $S_{a,b}$ be the set containing $a$ from column $0$ and $b + ai$ (mod $p$) from column $i$ for $i = 1, 2, \dots, p$.

Note that it is enough to verify that any two of those sets have exactly one common square. Let $a, b, c \in \{0, 1, \dots, p-1\}$. Then $b + ai \equiv c + ai \pmod p \iff b \equiv c \pmod p \iff b = c$. So $|S_{a,b} \cap S_{a,c}| = 1$ for $b \ne c$.

Let $a_1 \ne a_2 \in \{0, 1, \dots, p-1\}$. $b+a_1i \equiv c+a_2i \pmod p \iff i \equiv (a_1-a_2)^{-1}(c-b) \pmod p$. Since $p$ is prime, that inverse always exists and that $i$ is unique. Thus, $|S_{a_1,b} \cap S_{a_2,c}| = 1$ for all $a_1 \ne a_2$, $b$ and $c$. The solution is completed.