Let $n$ be an integer greater than two, and let $A_1,A_2, \cdots , A_{2n}$ be pairwise distinct subsets of $\{1, 2, ,n\}$. Determine the maximum value of \[\sum_{i=1}^{2n} \dfrac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|}\] Where $A_{2n+1}=A_1$ and $|X|$ denote the number of elements in $X.$
Problem
Source:
Tags: ratio, algebra proposed, algebra
17.08.2010 20:28
NOTE: We assume that none of the sets is empty, as otherwise some of the ratios are not defined. Since the sets are pairwise distinct, at most one of $A_i$ and $A_{i+1}$ can be equal to the intersection $A_i\cap A_{i+1}=:X$. This implies \[\frac{|A_{i}\cap A_{i+1}|}{|A_{i}|\cdot |A_{i+1}|} \le \frac{|X|}{|X|\cdot (|X|+1)} \le \frac12.\] By bounding every term in the sum from above by $1/2$, this yields that the considered sum is at most $n$. On the other hand, we can put $A_{2i-1}=\{i\}$ and $A_{2i}=\{i,i+1\}$ (in the last set $A_{2n}$ we write $2n+1$ for $1$). In this construction, the bound $n$ is attained. Hence the answer is: The maximum value of this sum is $n$.
30.06.2011 12:19
test20 wrote: ... in the last set $A_{2n}$ we write $2n+1$ for $1$ ... Of course, it was meant ... in the last set $A_{2n}$ we write $1$ instead of $n+1$ ... i.e. $A_{2n} = \{n,1\}$.
02.04.2018 09:43
For all $i\neq j$ $t=\frac{|A_i \cap {A_j}|}{|A_i||A_j|}\le \frac{1}{2}$ If their intersection is 0 Let wlog $|A_i|=a$ ,$|A_j=b$ and intersection is $c$ Then $|a|\le |b|$ If they intrrsect $|b|\ge 2$ and $|c|\le |a|$ $t\le \frac{1}{2}$ the sum is almost $n$ Which we get by $A_1=({1})$,$A_2=({1,2})$...... ,$A_{2n}=({n, 1})$
09.06.2018 15:03
Amir Hossein wrote: Let $n$ be an integer greater than two, and let $A_1,A_2, \cdots , A_{2n}$ be pairwise distinct subsets of $\{1, 2, ,n\}$. Determine the maximum value of \[\sum_{i=1}^{2n} \dfrac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|}\]Where $A_{2n+1}=A_1$ and $|X|$ denote the number of elements in $X.$ I got scared when I saw such an easy problem in a Chinese-Olympiad(!), But then it is CGMO
Construction for $\sum_{i=1}^{2n} \dfrac{|A_i \cap A_{i+1}|}{|A_i| \cdot |A_{i+1}|} = \text{n}$ ; $\rightarrow A_{2i-1} = \{2i-1\} , A_{2i} = \{2i-1,2i\}\blacksquare$