Let $n$ be an integer greater than $1$. For a positive integer $m$, let $S_{m}= \{ 1,2,\ldots, mn\}$. Suppose that there exists a $2n$-element set $T$ such that (a) each element of $T$ is an $m$-element subset of $S_{m}$; (b) each pair of elements of $T$ shares at most one common element; and (c) each element of $S_{m}$ is contained in exactly two elements of $T$. Determine the maximum possible value of $m$ in terms of $n$.
Problem
Source: USA TST 2005, Problem 1
Tags: geometry, rectangle, combinatorics proposed, combinatorics
21.07.2007 03:23
Let the sets $ A_{1}, A_{2}, ..., A_{2n}$ be the elements of $ T$. Then for each $ n \in S$ there is exactly one, unique, pair of $ i, j$ such that $ A_{i}\cap A_{j}= \{n\}$ (second and third condition), there are possibly some empty intersections, so the number of intersection is not less then the number of elements of $ S$. In other words: $ \binom{2n}{2}\geq mn$ or $ m \leq 2n-1$. We will show that $ m=2n-1$ is attainable. We construct $ A_{1}, ..., A_{2n}$ as follows. $ A_{1}=\{1,2,...,2n-1\}$. If we have constructed $ A_{1}, ..., A_{k}$ then for $ A_{k+1}$ we take an element on the $ k$-th position from each of the builded sets and for the rest of elements we choose smallest, unused elements of $ S$. So it goes like: $ A_{1}=\{1,2,...,2n-1\}$ $ A_{2}=\{1,2n,...,4n-3\}$ $ A_{3}=\{2,2n,4n-2...,6n-6\}$ $ A_{4}=\{3, 2n+1, 4n-2, 6n-5, ..., 8n-10\}$ ... $ A_{2n}=\{2n-1, 4n-3, 6n-6, 8n-10, ..., (2n-1)n\}$ It's easy to verify that such construction satisfies all required conditions.
12.12.2007 11:52
Here's another way of thinking about the problem: Consider a table with $ mn$ columns and $ 2n$ rows. Let each of the $ 2n$ rows represent each subset that is an element of $ T$, and each of the $ mn$ columns represent a subset; for each element that is an a certain subset of $ T$, in the row representing that subset, mark the relevant box. The given conditions tell us that: Each row has $ m$ marked squares, and each column has $ 2$ marked squares; and it's easy to see that each pair of elements in $ T$ shares at most one common element, iff there are no rectangles in the figure. So we have to find the largest $ m$, so that there are no rectangles. Suppose $ m \geq 2n$. WLOG (for convenience) the first row in the figure has the first $ m$ squares marked. Also WLOG, that the 2nd row has the 1st square marked, the 3rd row has the 2nd square marked ... the 2n-th row has the $ 2n-1$-th square marked (to satisfy the condition that each column has 2 marked squares). Consider the $ 2n$-th row. We must have one marked square apart from the one already marked, but we easily see that marking any of the remaining of $ 2n-1$ squares will complete a rectangle - which gives us a desired contradiction. When $ m = 2n-1$, greedy principle does the job. Mark the first $ 2n-1$ squares of the first row. Starting from the $ 1$-st square in the $ 2$-nd row, tick the diagonal going down. Now mark, the next set of $ 2n-2$ squares, and mark the diagonal downwards again - keep doing this, and some simple computations show that when you finish you just finish filling the table.
23.07.2010 16:46
Oh. This problem is very easy. If you have a graph with the vertexs is all sets. If two vertex are conected, we have two sets respect to two sets have common elements. So by the given conditions, we have each sides is respect to elements of the set $S_m$. Easily, we have $m_{max}=2n-1$
17.04.2016 02:40
I got a solution similar to DangChien's, but the write-up is a bit more formal.
18.12.2018 18:36
ANSWER: The maximum possible value of $m$ is $m=2n-1$. PROOF: Let $T=\{A_1,A_2, \dots ,A_{2n}\}$. Consider a $mn \times 2n$ matrix with all entries either $0$ or $1$, such that $a_ij=1$ iff $j \in A_i$. Call a triplet of the form $(i,A_j,A_k)$ nice if $i \in A_j$ and $i \in A_k$. We count the number of nice triplets in two different ways:- First fix an element $i$. Then, as $i$ is present in exactly two unique sets $A_j$ and $A_k$ according to problem condition $(c)$, so we get that $$\text{Total number of nice triplets}=\sum_{i=1}^{mn} \binom{2}{2} =mn$$ This time, we choose two sets $A_j$ and $A_k$ in $\binom{2n}{2}$ ways. Then, according to condition $(b)$, these two sets have atmost one common element, which gives $$\text{Total number of nice triplets} \leq \binom{2n}{2}$$ Thus, we get that $mn \leq \frac{2n(2n-1)}{2} \Rightarrow m \leq 2n-1$. Now, all that needs to be done is show that this bound is achievable. Let us take $S=\{1,2, \dots ,n(2n-1)\}$ for $m=2n-1$. Then we define the elements of $T=\{A_1,A_2, \dots ,A_{2n}\}$ as follows:- \[\displaystyle A_i = \left\{ \begin{array}{lr} \{x:x=(p-1)(2n-1)+q \cup (n-1)(2n-1)+i \text{ for } 1 \leq p \leq n \text{ and } 1 \leq q \leq 2\} & \text{when}\ \ 1 \leq i \leq n-1 \\ \\ \{x:x=a(2n-1) \cup (n-1)(2n-1)+b \text{ for } 1 \leq a \leq n \text{ and } n \leq b \leq 2n-1\} & \text{when}\ \ i=n \\ \\ \{x:x=(i-n-1)(2n-1)+j \text{ for } 1 \leq j \leq 2n-1\} & \text{when}\ \ n+1 \leq i \leq 2n \end{array} \right.\]Then one can easily see that this set $T$ satisfies all the three conditions given in the problem statement. Hence, done. $\blacksquare$
13.01.2019 00:16
08.05.2023 20:19
Easy problem. Solved with geoking and myself. The bound is pretty easy to get consider a $\binom{2n}{2} \text{x } mn$ incidence matrix, where the rows represent the pair of $A_{i}$ and the column $j$ represents the number $j$. If the number $j$ is in the i'th pair, we put 1 in the $(i,j)$ cell. Note that for each element, there is a pair of set and the intersection of any set is atmost 1. So we get $\binom{2n}{2} \geq mn$, by further simplifying one can get $m \leq 2n-1$. For construction, note that this incidence matrix is a square, and now diagonally fill $1$ to finish.
07.01.2025 14:17
Neat double counting problem My construction is one that I have not seen on the thread Double count the number $X$ of pairs $(e, T_1, T_2)$ where $e\in T_1, T_2\in T$. Fixing $T_1$ and $T_2$ and using condition (b), we get that $X\le \binom{2n}{2}$. Fixing $e$ and using (c), we get that $X=mn$. Combining the two, we get a bound $m\le 2n-1$. For the construction, consider $2n$ lines in general position, which can easily be checked to work