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 $\left(\genfrac{}{}{0ex}{}{k}{2}\right)p^2=n\left(\genfrac{}{}{0ex}{}{k}{2}\right)$, 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(\mathrm{mod}p)⟺b\equiv c(\mathrm{mod}p)⟺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_{1}i\equiv c+a_{2}i(\mathrm{mod}p)⟺i\equiv (a_1-a_2{)}^{-1}(c-b)(\mathrm{mod}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.