I like this one. For any logical assertion $\mathcal{A}$, we define a number $\left[\mathcal{A}\right]$ by setting $\left[\mathcal{A}\right]=1$ if $\mathcal{A}$ is true, and $\left[\mathcal{A}\right]=0$ if $\mathcal{A}$ is false. Then, every $i\in\left\{1,2,...,k\right\}$ and $j\in\left\{1,2,...,k\right\}$ satisfy $\left|S_i\backslash S_j\right| = \sum_{x\in S}\left[x\in S_i\backslash S_j\right]$ (because every subset $T$ of $S$ satisfies $\left|T\right| = \sum_{x\in S}\left[x\in T\right]$). Thus, $\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\left|S_i\backslash S_j\right| = \sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\sum_{x\in S}\underbrace{\left[x\in S_i\backslash S_j\right]}_{= \left[x\in S_i\wedge x\notin S_j\right]} = \sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\sum_{x\in S}\left[x\in S_i\wedge x\notin S_j\right]$ $=\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k}}\sum_{x\in S}\left[x\in S_i\wedge x\notin S_j\right]$ (we have left out the condition $i\neq j$ here, because the terms of the sum which are obtained for $i = j$ are all zero and thus don't matter - in fact, if $i = j$, then $\left[x\in S_i\wedge x\notin S_j\right]=0$). Continuing the computation, $\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\left|S_i\backslash S_j\right|=\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k}}\sum_{x\in S}\underbrace{\left[x\in S_i\wedge x\notin S_j\right]}_{=\left[x\in S_i\right]\cdot\left[x\notin S_j\right]}$ $=\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k}}\sum_{x\in S}\left[x\in S_i\right]\cdot\left[x\notin S_j\right]=\sum_{x\in S}\left(\sum_{i=1}^k\left[x\in S_i\right]\cdot\sum_{j=1}^k\left[x\notin S_j\right]\right)$. Now, by the AM-GM inequality (applied to the numbers $\sum_{i=1}^k\left[x\in S_i\right]$ and $\sum_{j=1}^k\left[x\notin S_j\right]$), we have $\sum_{i=1}^k\left[x\in S_i\right]\cdot\sum_{j=1}^k\left[x\notin S_j\right]\leq\frac14\left(\sum_{i=1}^k\left[x\in S_i\right]+\sum_{j=1}^k\left[x\notin S_j\right]\right)^2$. But $\sum_{i=1}^k\left[x\in S_i\right]+\sum_{j=1}^k\left[x\notin S_j\right] = \sum_{i=1}^k\left[x\in S_i\right]+\sum_{i=1}^k\left[x\notin S_i\right] $ $=\sum_{i=1}^k\left(\underbrace{\left[x\in S_i\right]+\left[x\notin S_i\right]}_{=1\text{, since one of the terms is }0\text{ and one is }1}\right)=\sum_{i=1}^k 1=k$, so this becomes $\sum_{i=1}^k\left[x\in S_i\right]\cdot\sum_{j=1}^k\left[x\notin S_j\right]\leq\frac14k^2$. Hence, $\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\left|S_i\backslash S_j\right| = \sum_{x\in S}\underbrace{\left(\sum_{i=1}^k\left[x\in S_i\right]\cdot\sum_{j=1}^k\left[x\notin S_j\right]\right)}_{\leq\frac14k^2} \leq \sum_{x\in S}\left(\frac14k^2\right)=n\cdot\frac14k^2$ (since the set $S$ has $n$ elements). So we have seen that the sum $\sum_{\substack{1\leq i\leq k;\\1\leq j\leq k;\\i\neq j}}\left|S_i\backslash S_j\right|$ consists of $k \left(k - 1\right)$ terms, and their sum is $\leq n\cdot\frac14k^2$; thus, according to the pigeonhole principle, at least one of them is $\leq\frac{n\cdot\frac14k^2}{k\left(k-1\right)}=\frac{nk}{4\left(k-1\right)}$. In other words, there are two $i$ and $j$ satisfying $1\leq i\leq k$, $1\leq j\leq k$ and $i\neq j$ and $\left|S_i\backslash S_j\right|\leq\frac{nk}{4\left(k-1\right)}$. Consider these $i$ and $j$. Since the set $S_i$ has at least $r$ elements, $\left|S_i\right|\geq r$. Thus, the number of common elements of the sets $S_i$ and $S_j$ is $\left|S_i\cap S_j\right|=\underbrace{\left|S_i\right|}_{\geq r}-\underbrace{\left|S_i\backslash S_j\right|}_{\leq\frac{nk}{4\left(k-1\right)}}\geq r-\frac{nk}{4\left(k-1\right)}$. So we have found two $i$ and $j$ such that $i\neq j$ and the number of common elements of the sets $S_i$ and $S_j$ is greater or equal to $r-\frac{nk}{4\left(k-1\right)}$. If $i < j$, then we are done; if $i > j$, then we have to interchange $i$ and $j$ in order to have the condition $i < j$ fulfilled, and the problem is solved. Darij

This following solution is due to a very close friend of mine:

panamath wrote: This following solution is due to a very close friend of mine:

Not sure if this is correct. Take $n$ arbitary large, $r=3$ and $k=\textstyle\binom n3$ and $S_1,S_2,.....S_n$ be all the $3-element$ subsets of ${1,2,3,...n}$ It is ease to see that there are no $S_i$ and $S_j$ such that $|S_i/S_j| \le \frac{n}{k}$ since $|S_i/S_j|\ge 1$ and $k=\textstyle\binom n3$ $>$ $n$ But you don't need $\frac{n}{k}$ Just assume that $|S_i/S_j| > r-\frac{nk}{4(k-1)}$ for all pairs $(S_i,S_j)$ with $i\neq j$ We then have $\sum_{i\neq j}|S_i/S_j| >\frac{nk^2}{4}$ (Because the number of pairs $(S_i,S_j)$ is $k(k-1)$) Now if $a$ is an arbitary element of $S$ and $a$ is in $m$ (so it's not in $k-m$) subsets, than $a$ will appear in the counting above if and only if we have pair $(S_i,S_j)$ such that $a\in S_i$ and $a\not\in S_j$ and the number of these pairs is exactly $m(k-m)$, which, by AM-GM, is $m(k-m)\le\frac{k^2}{4}$ Now we have $n$ elements in $S$ so we find that $\frac{nk^2}{4}\ge\sum_{i\neq j}|S_i/S_j| >\frac{nk^2}{4}$, absurd. So we have a pair $(S_i,S_j)$ such that $|S_i/S_j|\le\ r-\frac{nk}{4(k-1)}$ For that pair we see that $|S_i \cap S_j| = |S_i| - |S_i/S_j| \ge r - \frac{nk}{4(k-1)}$ and we are done

Solution from Twitch Solves ISL: Assume for contradiction this is not the case. We double-count the number $N$ of triples of the form \[ (x, A_i, A_j) \qquad\text{where}\quad x \in A_i, \; x \in A_j. \]On the one hand, counting by $(A_i, A_j)$ first, we have \[ N \le \binom k2 \cdot \left[ r - \frac{nk}{4(k-1)} \right]. \]On other hand, summing by $x \in X$, we have \[ N = \sum_x \binom{\text{\# times $x$ appears}}{2} \ge n \cdot \binom{\frac{rk}{n}}{2} \]by Jensen. Therefore we obtain \[ \frac{1}{2} n \cdot \frac{rk}{n} \cdot \left( \frac{rk}{n} - 1 \right) < \frac{k(k-1)}{2} \cdot \left[ r - \frac{nk}{4(k-1)} \right] \]which rearranges to \[ r \cdot \left( \frac{rk}{n}-1 \right) < (k-1) r - \frac n4 \cdot k \iff \frac 1n \left( r - \frac n2 \right)^2 < 0 \]and this is a contradiction.

Posting for storage.

Suppose that element $i$ of the set belongs to $a_i$ such subsets. The average size of set intersections across all sets $\{S_i, S_j\}$ is equal to $$\frac{\sum {a_i \choose 2}}{{k \choose 2}} \geq \frac{n {kr/n \choose 2}}{{k \choose 2}}$$by Jensen. Thus it suffices to show the inequality $$r - \frac{nk}{4(k-1)} \leq \frac{r\left(\frac{kr}n-1\right)}{k-1} \iff \frac{k(2r-n)^2}{4n(k-1)} \geq 0,$$which is obviously true.

Let $s_i$ be the number of subsets that an element $i$ is in. Notice that \[\sum_i s_i\le kr\]and \[\sum_{i=1}^n \binom{s_i}2 \ge n\binom{\frac{s_1+s_2+\dots+s_n}n}2\ge n\binom{kr/n}{2}.\]The expected value of the number of intersections between any two randomly chosen subsets is greater than or equal to \[\frac{n\binom{kr/n}{2}}{\binom k2}\]which we need to show is greater than or equal to $r-\tfrac{nk}{4(k-1)}$. \begin{align*} \frac{n\binom{kr/n}{2}}{\binom k2} &\ge r-\frac{nk}{4(k-1)}\Longleftrightarrow \frac{r(\frac{kr}{n}-1)}{k-1}\ge r-\frac{nk}{4(k-1)} \\&\Longleftrightarrow 4r\left(\frac{4r}{n}-1\right)\ge 4r(k-1)-nk \\&\Longleftrightarrow 4kr^2-4nr\ge 4nrk-4nr-n^2k \\&\Longleftrightarrow n^2k-4nrk+4kr^2\ge 0 \\&\Longleftrightarrow (n-2k)^2\ge 0 \end{align*}which is clearly true, therefore we are done. $\blacksquare$

We can see that the sum of the number of elements in all of the subsets combined is $k \cdot r$. We want to find $\sum_{a = 1}^n \binom{x_a}{2}$ where $x_a$ is the number of subsets that a certain element is in. We claim that the maximum value of this is $n \cdot \frac{\left(\frac{kr}{n}\right)\left(\frac{kr}{n} - 1 \right)}{2}$. This is becuase once we extend the function $\binom{n}{2}$ to $\mathbb{R}$ (by simply letting $\binom{n}{2}= \frac{n(n-1)}{2}$) we can see that it is an exponential function. Since the total number of pairs of subsets is $\binom{k}{2}$. It remains to prove that $$n \cdot \frac{\left(\frac{kr}{n}\right)\left(\frac{kr}{n} - 1 \right)}{2} \geq \binom{k}{2} \left(r - \frac{nk}{4(k-1)} \right)$$We can simplify this to $$\frac{r^2}{n} \geq r - \frac{n}{4} \Rightarrow 4r^2 - 4nr -n^2 \geq 0 \Rightarrow (2r-n)^2 \geq 0$$$\blacksquare$

Let the $i$'th element of $X$ be in $k_i$ subsets. Let $B$ be the set with the intersection of any two subsets. We can then say: \[\mathbb{E}[|B|]=\sum{\dfrac{\binom{k_i}{2}}{\binom{k}{2}}}.\]By Jensen's inequality, this is greater than or equal to: \[\dfrac{n}{\binom{k}{2}}\cdot \binom{\dfrac{k_1+\dots+k_n}{n}}{2}\geq \dfrac{n}{\binom{k}{2}}\cdot \binom{kr/n}{2}.\] Claim: $\dfrac{n}{\binom{k}{2}}\cdot \binom{kr/n}{2}\geq r-\frac{nk}{4(k-1)}$ Proof: We first simplify the LHS of the above claim, getting: \[n\cdot\dfrac{2}{k(k-1)}\cdot\dfrac{rk}{n}\cdot\left(\dfrac{rk}{n}-1\right)\cdot \frac{1}{2}\]\[=\dfrac{r(rk-1)}{n(k-1)}.\] Thus, our claim works if and only if: \[4r^2k-4nr\geq 4nr(k-1)-n^2k,\]\[4r^2-4nr+n^2\geq 0,\]\[(2r-n)^2\geq 0,\]which is true by trivial inequality $\square$.

Let $s_i$ be the number of subsets element $i$ is in. Notice \[\sum_{i=1}^n s_i \ge kr\] and \[\sum_{i=1}^n \binom{s_i}2 \ge n\binom{\frac{s_1+s_2+\dots+s_n}n}2\ge n\binom{kr/n}{2}.\] by Jensen's. Thus, it suffices to show \[r - \frac{nk}{4(k-1)} \leq \frac{r\left(\frac{kr}n-1\right)}{k-1}\] which simplifies to $(n-2k)^2 \ge 0$. $\square$

Define $a_i$ as the number of the number of subsets the $i^{th}$ element is in. Note that the total number of intersections is $\sum_{i=1}^{n} \binom{a_{i}}{2}$ By jensen we have the inequality $\sum_{i=1}^{n} \binom{a_{i}}{2} \geq n\binom{\tfrac{kr}{n}}{2}$ So the average number of intersections over all pairs of subsets is greater than $$\frac{n}{k}\binom{\tfrac{kr}{n}}{2}=\frac{r(\tfrac{kr}{n}-1)}{2}$$Also note that $\frac{r(\tfrac{kr}{n}-1)}{2} \geq r-\frac{nk}{4(k-1)}$ upon simplifying and the trivial inequality.

Let the elements in $X$ be $e_1$, $e_2$, $\dots$, $e_n$. Let element $e_i$ be in $s_i$ subsets for all integers $i$ between $1$ and $n$ inclusive. Note that then we have that \[s_1+s_2+\dots+s_n\geq kr,\]and the total number of intersections is \[\sum_{i=1}^{n}\binom{s_i}{2},\]and by Jensen's we have that \[\sum_{i=1}^{n}\frac{s_i(s_i-1)}{2}\geq n\left(\frac{\frac{kr}{n}\left(\frac{kr}{n}-1\right)}{2}\right).\]Now, notice that proving that at least one pair of sets has an intersection of $r - \frac{nk}{4(k-1)}$ is equivalent to proving that \[\frac{\sum_{i=1}^{n}\frac{s_i(s_i-1)}{2}}{\binom{k}{2}}\geq \frac{n\left(\frac{\frac{kr}{n}\left(\frac{kr}{n}-1\right)}{2}\right)}{\binom{k}{2}}\geq r - \frac{nk}{4(k-1)}.\]Multiplying both sides by $4n(k-1)$ and simplifying, we end up with \[4r^2-4nr+n^2=(2r+n)^2\geq{} 0,\]which is clearly true, finishing the problem.

Assume ftsoc every two subsets of the $k$ given have less than $r = \tfrac{nk}{4(k - 1)}$ elements in common. Let $X = \{1, 2, \ldots, n\}$ and let $i$ be in $x_i$ of the $k$ given subsets for $1 \le i \le n$. Additionally, denote by $S$ the number of unordered triplets $(X_1, X_2, i)$ where $X_1, X_2$ are two of the $k$ subsets of $X$ and $i$ is in both $X_1$ and $X_2$. On one hand, we have $$S = \sum_{i = 1}^n \binom{x_i}{2}.$$Since $$\sum_{i = 1}^n x_i \ge kr,$$by Jensen's this means that $$S \ge n \cdot \binom{kr/n}{2} = \frac{kr(kr/n - 1)}{2}.$$However, we also have $$S < \binom{k}{2} \cdot (r - \frac{nk}{4(k - 1)}) = \frac{rk(k - 1)}{2} - \frac{nk^2}{8}.$$Therefore $$\frac{rk(k - 1)}{2} - \frac{nk^2}{8} > \frac{kr(kr/n - 1)}{2} \implies 4rn - n^2 > 4r^2 \implies (n - 2r)^2 < 0,$$contradiction.

WLOG set $X = \{1,2,\dots,n\}.$ Let $e_i$ be the number of the $k$ subsets that contains $i$ for $1 \le i \le n.$ Then if we select two of the subsets that contain the number $i,$ each selection contributes $1$ to their union. Therefore, if $A_{j,m}$ is the number of elements in the intersection of the $j$th and $m$th subsets, we get \[ \sum_{1 \le j < m \le k} A_{j,m} = \binom{e_1}{2} + \dots + \binom{e_n}{2}. \]Therefore, the expected number of elements in the intersection of two subsets is equal to \[ \frac{\binom{e_1}{2} + \dots + \binom{e_n}{2}}{\frac{k(k-1)}{2}}. \]Now, suppose that there are $x_i$ elements in the $i$th subset. By a simple double-counting argument, we have that $e_1 + \dots + e_n = x_1 + \dots + x_k \ge rk$ by the given condition. Hence by Jensen's inequality we get \begin{align*} \frac{\binom{e_1}{2} + \dots + \binom{e_n}{2}}{\frac{k(k-1)}{2}} &\ge \frac{n \binom{\tfrac{e_1 + \dots + e_n}{n}}{2}}{\frac{k(k-1)}{2}} \\ &\ge \frac{n \binom{\tfrac{rk}{n}}{2}}{\frac{k(k-1)}{2}} \\ &= \frac{n\left(\frac{rk}{n}\right)\left(\frac{rk}{n}-1\right)}{k(k-1)} \\ &= \frac{rk(rk-n)}{nk(k-1)} \\ &= \frac{r(rk-n)}{n(k-1)}. \end{align*}We will now show that \[ \frac{r(rk-n)}{n(k-1)} \ge r - \frac{nk}{4(k-1)} = \frac{4rk - 4r - nk}{4(k-1)}. \]Multiplying both sides by $k - 1,$ we get \[ \frac{r^2 k - rn}{n} \ge \frac{4rk-4r-nk}{4}. \]Cross-multiplying both sides, we get \[ 4r^2 k - 4rn \ge 4nrk - 4nr - n^2 k. \]Adding $4rn$ to both sides and dividing both sides by $k,$ we get \[ 4r^2 \ge 4nr - n^2. \]Moving all the terms on one side, we get \[ 4r^2 - 4nr + n^2 \ge 0, \]Since $4r^2 - 4nr + n^2 = (2r-n)^2,$ this is clear by the trivial inequality. Since $k \ge 2,$ all of our steps are reversible. Therefore, the expected size of the intersection of two of the chosen subsets is \[ \frac{\binom{e_1}{2} + \dots + \binom{e_n}{2}}{\frac{k(k-1)}{2}} \ge \frac{r(rk-n)}{n(k-1)} \ge r - \frac{nk}{4(k-1)}, \]which clearly suffices.

WLOG $X = \{1, 2, \dots, n \}$ and let $x_i$ be the number of subsets with $i$ in it. Choose two subsets at random, the expected cardinality of the intersection is $$\frac{1}{\binom{k}{2}} \sum_{i = 1}^n \binom{x_i}{2} \ge \frac{1}{\binom{k}{2}} n \binom{\sum_{i = 1}^n x_i / n}{2} \ge \frac{1}{\binom{k}{2}} n \binom{kr/n}{2} = \frac{r(kr - n)}{n(k - 1)}$$Now $r - \frac{nk}{4(k - 1)} = \frac{4kr - 4r - nk}{4(k - 1)}$ so it suffices to show $$\frac{r(kr - n)}{n} \ge \frac{4kr - 4r - nk}{4} \iff 4kr^2 - 4rn \ge 4krn - 4rn - n^2k \iff k(2r - n)^2 \ge 0$$which is true. We are done.

Without loss of generality relabel $X = \{1, 2, \dots, n\}$. Let's pick two random subsets and see what happens. Suppose we choose distinct subsets $S_1, S_2$, and let $N = |S_1 \cap S_2|$. For $i = 1, 2, \dots, n$ let $a_i$ denote the number of selected subsets containing $i$. Summing over $\{1, 2, \dots, n\}$, we have \[\mathbb{E}[N] = \sum_{i = 1}^n \frac{\binom{a_i}{2}}{\binom{k}{2}} \geq \frac{1}{\binom{k}{2}} \cdot n\binom{\frac1n(a_1 + a_2 + \dots + a_n)}{2} \geq \frac{2n}{k(k - 1)} \cdot \frac12\left(\frac{kr}{n}\right)\left(\frac{kr}{n} - 1\right)\]\[ = \frac{r}{k - 1}\left(\frac{kr}{n} - 1\right)\]by Jensen on $\binom{x}{2}$ and the fact that $a_1 + a_2 + \dots + a_n \geq kr$. So it suffices to show that \[\frac{r}{k - 1}\left(\frac{kr}{n} - 1\right) \geq r - \frac{nk}{4(k - 1)}.\]Multiplying by $\frac{k - 1}{k}$, this reduces to \[\frac{r^2}{n} - \frac rk \geq r - \frac rk - \frac{n}{4} \iff \frac{r^2}{n} + \frac{n}{4} \geq r,\]which is true by AM-GM. $\square$

Let the elements be $1, 2, 3, \dots n$ and each of the elements to be in $x_1, x_2, \dots x_n$ of the $k$ subsets respectively. We have $\sum x_i \geq kr$ by the problem condition. The expected number of pairs of common elements among two subsets is $\frac{\sum \binom{x_i}{2}}{\binom{k}{2}}$ so we wish to prove that $$\frac{\sum \binom{x_i}{2}}{\binom{k}{2}} \geq r - \frac{nk}{4(k-1)}$$or $$\frac{n \cdot \binom{\frac{kr}{n}}{2}}{\binom{k}{2}} \geq r - \frac{nk}{4(k-1)}$$by Jensens but this just rearranges into $\frac{k^2(n-2r)^2}{n} \geq 0$ among expansion, trivial.