Balkan Mathematical Olympiad Shortlisted Problems

Let $x$ be the number of elements of $A$ that appear exactly once, and $y$ be the number of elements of $A$ that appear at least twice in the table. There is at most one number that does not appear in the table, otherwise, there would be two numbers that do not appear in any row, a contradiction. From there, we deduce that $$x+y\ge 2024$$ Since the total number of cells in the table is equal to $22m$, we have $$x+2y\le 22m$$ If $x>m$, there are two elements that appear exactly once but are in the same row, violating the given condition. Thus, $x\le m$ and we get $$2\cdot 2024\le 2(x+y)=(x+2y)+x\le 23m⟹m\ge 176.$$ Next, we will build a table of size $176\times 22$ that satisfies the given condition. For the equality to occur, we must have $x=m=176$, $y=2024-176=1848$, which means 1848 numbers appear exactly twice. We can assume that the elements from 1 to 1848 appear at least twice, and elements from 1849 to 2024 appear exactly once. The element 2025 will not be used. Now consider a simple, regular, undirected graph $G$ with 176 vertices corresponding to 176 rows of the table, all of which have the same degree 21. This graph can be easily constructed: arrange 176 vertices on the circle to form a regular polygon, connect each vertex to its reflection and the 10 nearest vertices on either side. For convenience, we enumerate the vertices from 1 to 176. The number of edges of the graph $G$ is $\frac{176\cdot 22}{2}=1848$ by the handshaking lemma. The 1848 edges correspond to 1848 elements that appear at least twice, thus enumerate the edges from 1 to 1848. If the edge $i$ connects vertices $u_i,v_i$, we place the element $i$ in the $u_i^{th}$ and $v_i^{th}$ rows of the table. When this step is completed, each row will have exactly 21 rows, as the degree of every vertex is 21. We arrange the remaining 176 elements from 1849 to 2024 arbitrarily so that each row has exactly 22 elements, meaning that every row will get exactly one of these elements. Now we check that the condition is satisfied for any two arbitrary $i,j\in A$ and $i<j$. If $j=2025$ then it is easy to see that the condition is satisfied, so we focus on $j\le 2024$. We consider the following cases: If $i,j\ge 1849$ then these elements correspond to the elements appearing only once, and by construction every row gets exactly one of these elements. Therefore, both the row that contains $i$ and the row that contains $j$ satisfy the condition. If $i\le 1848<j$ then $i$ appears twice (in different rows) while $j$ appears once, so there must be a row containing $i$ that does not contain $j$.

* If $i,j\le 1848$, both of them are in the set of elements that appear twice. By construction, those correspond to two distinct edges $i,j$ of $G$. As our $G$ is simple, it is impossible that distinct edges have the same endpoints. Those endpoints correspond to the rows where elements $i,j$ are placed. An endpoint for one edge that is not an endpoint for another corresponds to a row where one element is placed, but not the other. This list exhausts all the possibilities. Therefore, the table constructed satisfies the condition, and the minimum value to find is 176.