Maths Olympiad Prep

Library / /7 of 8

Combinatorics Difficulty 8.8 Shortlist Prove it Balkan Mathematical Olympiad

Consider a table with mm rows and 22 columns. Each cell is filled with a number from the set A={1,2,3,,2025}A = \{1, 2, 3, \dots, 2025\} (numbers may be repeated), such that for every pair of distinct numbers in AA, there exists a row that contains exactly one of these two numbers. Find the minimum value of mm.

Solution

Let xx be the number of elements of AA that appear exactly once, and yy be the number of elements of AA 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+y2024 x + y \geq 2024
Since the total number of cells in the table is equal to 22m22m, we have
x+2y22m x + 2y \leq 22m
If x>mx > m, there are two elements that appear exactly once but are in the same row, violating the given condition. Thus, xmx \leq m and we get
220242(x+y)=(x+2y)+x23m    m176. 2 \cdot 2024 \leq 2(x + y) = (x + 2y) + x \leq 23m \implies m \geq 176.
Next, we will build a table of size 176×22176 \times 22 that satisfies the given condition.
For the equality to occur, we must have x=m=176x = m = 176, y=2024176=1848y = 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 GG 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 GG is 176222=1848\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 ii connects vertices ui,viu_i, v_i, we place the element ii in the uithu_i^{th} and vithv_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,jAi, j \in A and i<ji < j. If j=2025j = 2025 then it is easy to see that the condition is satisfied, so we focus on j2024j \leq 2024. We consider the following cases:
* If i,j1849i, j \geq 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 ii and the row that contains jj satisfy the condition.
* If i1848<ji \leq 1848 < j then ii appears twice (in different rows) while jj appears once, so there must be a row containing ii that does not contain jj.

* If i,j1848i, j \le 1848, both of them are in the set of elements that appear twice. By construction, those correspond to two distinct edges i,ji, j of GG. As our GG is simple, it is impossible that distinct edges have the same endpoints. Those endpoints correspond to the rows where elements i,ji, 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.