Let $p$ be a given prime number. For positive integers $n,k\geq2$ let $S_1, S_2,\dots, S_n$ be unit square sets constructed by choosing exactly one unit square from each of the columns from $p\times k$ chess board. If $|S_i \cap S_j|=1$ for all $1\leq i < j \leq n$ and for any duo of unit squares which are located at different columns there exists $S_i$ such that both of these unit squares are in $S_i$ find all duos of $(n,k)$ in terms of $p$. Note: Here we denote the number of rows by $p$ and the number of columns by $k$.
Problem
Source: 2024 Turkey EGMO TST P5
Tags: Prime number, grid, combinatorics
12.02.2024 10:50
We claim that the only $(n,k)$ that works is $\boxed{(p^2,p+1)}$. Given a duo of unit squares in different columns, there exists exactly one $S_i$ containing both of them. Therefore by double counting these squares, we get $$p^2 \cdot \binom{k}{2} = n \cdot \binom{k}{2}$$which gives $n=p^2$. Further, we can count triples $(x,S_i,S_j)$ such that $x \in S_i \cap S_j$. Choosing $S_i$ and $S_j$ first gives $\binom{n}{2}$ choices. Now, if we choose $x$ first, then for any $y$ that is in a different column from $x$, there is a unique $S_i$ containing both $x$ and $y$. Hence there are $p$ choices for $S_i$ (for a fixed $x$), so $pk \cdot \binom{p}{2}$ for the triple. Equating both gives $k=p+1$. Now for the construction: Label the columns $0$ to $p$ and rows $0$ to $p-1$. For $a,b \in \{0,1, \dots, p-1\}$, let $$S_{(a,b)}=\{(x,ax+b \pmod p) \mid x=0,1, \dots, p-1\} \cup \{(a,p)\}$$These $p^2$ sets satisfy the given conditions because given any two points, there exists a line passing through them, and given a point and a slope, there exists a line passing through that point with a given slope. Further, given two lines, they intersect at exactly one point if they have different slopes, else their corresponding sets intersect in the last column.
12.02.2024 15:10
Pretty much European Mathematical Cup 2016 J4 and anything classical related to the theory of designs. Nevertheless, nice problem, in case no one has seen it before.