Ignore, wrong

aleksam wrote: Not sure this is true... may someone find the hole in my counterexample... Let's reformulate this as a graph, with numbers $1, 2... n $ as vertices and let the edge exist between $x, y $ iff there is an two element subset containing both. Now, suppose the contrary, for sake of contradiction(which I didn't find for some reason...) The contrary is that every $2/3n+1$ element subset contains not more than $n-1$ edges. Taking the complement, we find that amog every $n/3-1$ vertices, the sum of their degrees in the whole graph is at least $n $. Unfortunately, this can happen as we can take the graph to have edges $(i, i+1)$ , for $i \leq n $(taking indices mod $n $), and $(i, i+2)$, for $i\leq n-1$... Am I mistaken? If I understood correctly for $n=5$ you are taking subsets: $(1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(2,4),(3,5),(4,1)$ but choosing our $5$ subsets to be $(1,2),(2,3),(3,4),(1,3),(4,1)$ we have $4<\frac{10}{3}+1$ elements therefore your counterexample doesn't work.

My solution: Let $3m$ be number of couples we can take out( of set of subsets) such that remaining part of the set of subsets has at most $n-m$ elements. For $m=0$ is easy. Assume it's true for $m$, that we took $3m$ two element subsets such that remaining union has $n-m$ element. Induct on $m$. Since $2n-1-3m\le 2(n-m)$ there exists an element which is contained in rest no more than $3$ of $2n-3m-1$ two element subsets so if we take all the two element subsets containing him out we have increased $m$ by $1$. Therefore it holds for all $m\le \frac{n}{3}$. Specially for $m=\frac{n-1}{3}$ which implies the statement.

Using terminology of graphs, the problem is equivalent to the following: Given a graph $G$ with $n$ vertices and $2n-1$ edges, prove that there exists an induced graph with $d=\lfloor {\frac {2}{3}n+1}\rfloor$ vertices and at least $n$ edges. To construct such an induced graph, it is intuitive to remove vertices with small degrees. To this end, we define the two induced subgraphs of $G$: graph $U$ with vertices $ u_1, u_2, \dots , u_{d}$ and graph $W$ with vertices $w_1,w_2, \dots ,w_{n-d}$, such that \[d(w_1)\le d(w_2)\le \dots \le d(w_{n-d})\le d(v_1) \le \dots \le d(v_d)\](Here the degree function is taken over $G$). We next prove the problem by contradiction. Suppose $|E(U)|\le n-1$ and let $|E(W)|=t$. There are edges that bridge $U$ and $W$, the number of which is denoted by $s$. Thus $2n-1=s+t+|E(U)|\implies s+t\ge n$ and $s\le 2n-1-|E(U)|$. By handshake lemma on $W$, we have \[d(w_1)+d(w_2)+\dots +d(w_{n-d})=2(s+t)\ge 2n\implies d(w_{n-d})\ge \frac {2n}{n-d}\]Applying handshake lemma on $U$ gives: \[d(u_1)+\dots +d(u_d)=2(|E(U)|+s)\le 2(|E(U)|+2n-1-|E(U)|)=4n-2\]. Since $d(w_{n-d})\le d(u_{i})$ for all $i=1,\dots , d$ by construction, thus \[d\cdot \frac {2n}{n-d}\le 4n-2\]We can check that this equality never holds, which is the contradiction we need.

XmL wrote: . By handshake lemma on $W$, we have \[d(w_1)+d(w_2)+\dots +d(w_{n-d})=2(s+t)\ge 2n\implies d(w_{n-d})\ge \frac {2n}{n-d}\]. This should be $s+2t$ as the edges between $W$ and $U$ are counted exactly once in the sum. This makes your solution wrong.

In official solutions http://srb.imomath.com/zadaci/2016_smo_resenja.pdf it is said that with probabilistic method we can get bound approximately ${n\over \sqrt{2}}$. Can someone show that approach?

Lemma: $\binom{2n}{n} = 2^n \cdot \frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} \ge 2 \cdot 3^{n-1}$. Proof: See here for the first part. For the second part, note that $2k-1> \frac 32 k$ for $k>1$. $\square$ Back to the problem. Let $x_i \; (1 \le i \le n)$ be number of two-element sets among $2n-1$ sets that $i$ belongs. Note that $x_i \le n-1$. Pick $n$ sets randomly from $2n-1$ sets then the probability in getting at least one set that has $i$ is $$\displaystyle \mathbb{P}(X_i)= \frac{ \displaystyle \sum_{j=1}^n \binom{x_i}{j}}{\displaystyle \binom{2n-1}{n}} \le \frac{2^{n-1}-1}{\displaystyle \binom{2n-1}{n}}.$$In here, $X_i=1 \; (1 \le i \le 2n-1)$ if $i$ belongs to at least one of the chosen sets, $X_i=0$ otherwise. Thus, the expected number of elements in the union of $n$ sets is $\mathbb{E}[X] \le \frac{n(2^{n-1}-1)}{\binom{2n-1}{n}}.$ It suffices to prove $2^{n-1}-1< \binom{2n-1}{n} \cdot k$ for the best $k$ possible. It is equivalent to $2^{n}-2< \binom{2n}{n} \cdot k$ so from the lemma, $k= \frac 23$ is enough. Thus $\mathbb{E}[X] \le \frac 23 n$, which means there exists $n$ subsets so that their union has at most $\frac 23 n$ elements. Comment. We don't even need to use the condition $\sum_{i=1}^nx_i = 2(2n-1)$ so we can say that $k=\frac 23$ is a very weak bound.

shinichiman wrote: ... $$\displaystyle \mathbb{P}(X_i)= \frac{ \displaystyle \sum_{j=1}^n \binom{x_i}{j}}{\displaystyle \binom{2n-1}{n}}$$... I don't understand this. Should not that be: $$ \displaystyle \mathbb{P}(X_i)= \frac{ \displaystyle \sum_{j=1}^n \binom{x_i}{j} \binom{2n-1-x_i}{n-j} } {\displaystyle \binom{2n-1}{n}}$$

You are right, my bad. If that so then $\mathbb{P}(X_i)= 1- \frac{\binom{2n-1-x_i}{n}}{\binom{2n-1}{n}}.$ Thus, $\mathbb{E}[X]= n - \frac{\sum_{i=1}^n \binom{2n-1-x_i}{n}}{\binom{2n-1}{n}}$. By Jensen inequality, we have $$\sum_{i=1}^n \binom{2n-1-x_i}{n} \ge n \binom{ 2n-1- \bar{x}}{n},$$where $\bar{x}= \frac 1n \sum_{i=1}^nx_i= \frac{4n-2}{n}$. Hence, $$\mathbb{E}[X] \le n-n \cdot \frac{\binom{2n-5+2/n}{n}}{\binom{2n-1}{n}}.$$It suffices to find a lower bound of $\frac{\binom{2n-5+2/n}{n}}{\binom{2n-1}{n}}$ but it doesn't give a better result than the final $2/3n$.

Yes, I did the same. It does not give you neither something like ${n\over \sqrt{2}}$.

Finally I think I got it. We have actually graph on $n$ vertices and $2n-1$ edges. We have to show that there is subgraph with at most $2n/3 +1$ vertices and at least $n$ edges. Take any vertex independently with probability $p$. Let $X$ be the number of chosen vertices and $Y$ number of chosen edges. We see that for $p= {1\over \sqrt{2}}$ we get $E(X) = n\cdot p = {n\over \sqrt{2}}$ and $E(Y) = (2n-1)\cdot p^2 = n-{1\over 2}$. So there exist graph on at least $n$ edges with approximately ${n\over \sqrt{2}}$ vertices as clammed. Perhaps we can get better result ($2n/3+1$) if we subtract vertices which have small degree (say only one) in subgraph.

Very nice idea Number1. The expected values also matched the answer perfectly! But I think the two expected value are not good enough to state the existence. We know that if $\mathbb{E}[X]=\frac{n}{\sqrt 2}$ then there exists some events so that $\mathbb{E}[X] \le \frac{n}{\sqrt{2}}$. For such each event, we get a fix number of edges, which means there is a possibility that for each such event, number of edges is less than $n$. We can't actually use $\mathbb{E}[Y]$ anymore because after picking the vertices, we already got a fix number of edges. I hope my opinion makes senses somehow. I'm not certain about this opinion. If it's wrong, please let me know. Thank you.

We use the graph formulation with $n$ vertices and $2n-1$ edges; we permit multiple edges. Our goal is to show that an induced subgraph of some $\tfrac 23 n+1$ vertices has at least $n$ edges. To that end, the following algorithm works: start with all $n$ vertices at once and keep removing the vertex with the smallest degree. To prove its validity, we present the following main claim. Claim. After we have removed $m$ vertices, we have removed at most $3m$ edges. Proof. Induction on $m$; the base case $m=1$ is clear as at least one vertex has degree $\leq 3$. Now suppose that we currently have $n-m$ vertices and $e$ edges. Let $d$ be the smallest degree. Then we obtain the following bound by handshaking lemma. $$d(n-m) \leq 2e$$Thus, we have the new number of edges, \begin{align*} e' &\geq e - \frac{2e}{n-m} \\ &\geq (2n-1-3m) - \frac{2(2n-1-3m)}{n-m} \\ &= (2n-1-3m) - 4 + \frac{2m+2}{n-m} \\ &>(2n-1-3m)-4 \end{align*}so we are done. $\blacksquare$ The problem is completed upon taking $m = \left\lfloor\tfrac{n-1}{3}\right\rfloor$.