Hi, I really would like to see a elegant combinatorial proof to this beatiful problem I just know of an ugly proof which uses some limit computations... I was thinking about if one could find the biggest such number p in dependence of n? mathe760

mathe760 wrote: Hi, I really would like to see a elegant combinatorial proof to this beatiful problem I just know of an ugly proof which uses some limit computations... I was thinking about if one could find the biggest such number p in dependence of n? mathe760 Dear mathe760, You can find an official solution here: artofproblemsolving.com/Forum/viewtopic.php?f=177&t=214623 I know it uses logarithm and limit, but, to me, it is very elegant as a combinatorial proof. What interests me more is that the approach used in the solution seems to create sets and simply count them. This is straightforward enough as an enumerative method. However, it is highly not obvious as to how to come up with such a solution. I'm eager to know how the proposer came up with it and used it to make the beautiful constant $\frac{3-\sqrt{5}}{2}$ and also how to prove that the constant is sharp. I believe that there may be some research behind this, which I would love to see. Sincerely, Disner.

In the book olympiad combinatorics this is placed in double counting section.The official solution uses only few double counting tricks.Does anyone has a solution using double counting as the main part of the solution?I have some idea but they seem to give us nothing since the result in the problem is quite strong.Here is a sketch of the idea:Assume for country that there doesn't exist such $n,p$ Then for every $p$ distinct subset of the set there are at most $p-1$ subsets that have a common element with all these subsets.Also we can count this in another way for a $k$ element subset there are $2^n-2^{n-k}$ subsets that have a common element with it so we can count this in another way(stars).In fact I used the same method of double counting used in Zarankiewicz’s problem.At the end I got into an inequality If we could show it is wrong for some $p,n$ We are done.Indeed we should use limit and I am not good at all in calculas.Can anyone verify if this works?Anyway if it doesn't I really like to see a solution using double counting(Or even a method that is easier to come up in an exam.

Let $a_0, \dots, a_{k-1}$ be positive integers, and define $s_i = a_0 + \dots + a_{i-1}$ (so $s_0 = 0$); let $s_k = s$. Partition the set $\{1, \dots, s\}$ into segments $I_i = \{s_i + 1, \dots, s_i + a_i\}$ for all $i$, and define two properties on subsets of $\{1, \dots, s\}$ as follows: Say a subset has property $P$ if it contains one of the segments $I_0, \dots, I_{k-1}$. Say a subset has property $Q$ if it contains at least one point from each of the segments $I_0, \dots, I_{k-1}$. Clearly each subset with property $P$ intersects each subset with property $Q$. By easy counting, we have \begin{align*} 2^{-s} |Q| & = \prod (1 - 2^{-a_i}),\\ 2^{-s} |P| & = 1 - \prod (1 - 2^{-a_i}),\\ 2^{-s} |P \cap Q| & = \prod (1 - 2^{-a_i}) - \prod (1 - 2^{-a_i+1}). \end{align*}To solve the problem, we let elements of $P$ be the $S_i$s, and elements of $Q \setminus P$ be the $T_i$s. For this to be valid, we need \[ \prod (1 - 2^{-a_i}) < 1 - \alpha \quad \text{and} \quad \prod (1 - 2^{-a_i+1}) > \alpha. \]We now specialize to solutions with $a_0 = \dots = a_{k-1} = a$, which requires \[ (1 - 2^{-a})^k < 1 - \alpha \quad \text{and} \quad (1 - 2^{-a + 1})^k > \alpha. \]Let $\lambda = \frac{3 - \sqrt{5}}{2}$, so $\alpha < \lambda = (1 - \lambda)^2 < (1 - \alpha)^2$. For each value of $a$, we try the choice $k_a = \left \lfloor -2^a \log (1 - \lambda) \right \rfloor$. Then easy limit computations give \[ \lim_{k \to \infty} (1 - 2^{-a})^{k_a} = 1 - \lambda \quad \text{and} \quad \lim_{k \to \infty} (1 - 2^{-a+1})^{k_a} = (1 - \lambda)^2 = \lambda. \]It follows that for sufficiently large $a$, both desired inequalities are satisfied.

This is a paper from the 80's by Daykin and Frankl. https://gilkalai.files.wordpress.com/2022/11/daykinfranklirrationalplusimage.pdf In recent progress on Frankl's conjecture this number $\frac{3-\sqrt{5}}{2}$ has also come up.

We prove that $\frac{3-\sqrt{5}}{2}$ is optimal. Let $[n]=\{1,\cdots,n\}$ and $\mathcal{P}([n])$ to be the set of all subsets (includes $[n]$ and $\emptyset$) of $[n]$. Define an up-set to be a set $\mathcal{S}$ such that for all $T\in \mathcal{S}$, any set $U$ satisfying $T\subseteq U \subseteq [n]$ Kleitman's lemma: Let $\mathcal{A}, \mathcal{B}\subseteq \mathcal{P}([n])$ be up-sets, then $$|\mathcal{A} \cap \mathcal{B}| \ge \frac{|\mathcal{A}| |\mathcal{B}|}{2^n}$$ Proof: Induct on $n$. The base cases are clear. To induct, let $\mathcal{A}_1$ be the set of elements containing $n$ in $\mathcal{A}$ and $\mathcal{A}_0$ be the other elements. Define $\mathcal{B}_1$ and $\mathcal{B}_0$ similarly. We can see that $|\mathcal{A}_1|\ge |\mathcal{A}_0|,|\mathcal{B}_1|\ge |\mathcal{B}_0|$. Therefore, by inductive hypothesis on $n-1$ on $\mathcal{A}_1, \mathcal{B}_1$ and $\mathcal{A}_0, \mathcal{B}_0$ \begin{align*} |\mathcal{A} \cap \mathcal{B}| &= |\mathcal{A}_1 \cap \mathcal{B}_1| + |\mathcal{A}_0 \cap \mathcal{B}_0| \\ &\le \frac{1}{2^{n-1}} \left( |\mathcal{A}_1||\mathcal{B}_1| + |\mathcal{A}_0||\mathcal{B}_0|\right) \\ &\le \frac{1}{2^{n}} \left( |\mathcal{A}_1|+|\mathcal{A}_0|\right) \left( |\mathcal{B}_1|+|\mathcal{B}_0|\right) \\ &= \frac{1}{2^{n}} |\mathcal{A}| |\mathcal{B}| \end{align*} Back to the original problem. Let $\mathcal{S} = \{ S_1, \cdots, S_p\}, \mathcal{T} = \{T_1,\cdots,T_p\}$. Let $\mathcal{S'}, \mathcal{T'}$ be the minimal up-sets that cover $\mathcal{S}$ and $\mathcal{T}$. We can see that $$|\mathcal{S}| + |\mathcal{T}| = |\mathcal{S} \cup \mathcal{T}| \le |\mathcal{S'} \cup \mathcal{T'}| $$ $$ = |\mathcal{S'}| + |\mathcal{T'}| - |\mathcal{S'} \cap \mathcal{T'}|$$ I claim for all $A'\in \mathcal{S'}, B'\in \mathcal{T'}$ we have $A'\cap B' \ne \emptyset$. Note there exists $A,B$ such that $A\subseteq A', B\subseteq B'$ and $A \in \mathcal{S}, B\in \mathcal{T}$. Let $X= |\mathcal{S'}| + |\mathcal{T'}|$. This implies that $$ |\mathcal{S'}| + |\mathcal{T'}| = \sum_{A\subseteq [n]} (1_{A\in \mathcal{S'}} + 1_{[n]\backslash A\in \mathcal{T'}}) \le 2^n$$ By Kleitman's lemma, $$|\mathcal{S'} \cap \mathcal{T'}| \ge |\mathcal{S'}||\mathcal{T'}| 2^{-n} \ge |\mathcal{S}| \left(|\mathcal{S'}| + |\mathcal{T'}| - |\mathcal{S}|\right) 2^{-n} = |\mathcal{S}| \left(X - |\mathcal{S}|\right) 2^{-n}$$ Since $|\mathcal{S}| \le |\mathcal{S'}|, |\mathcal{T'}|$ It readily follows that $$2|\mathcal{S}| \le X - |\mathcal{S}| \left(X - |\mathcal{S}| \right) 2^{-n} \le 2^n - |\mathcal{S}| \left(2^n - |\mathcal{S}| \right) 2^{-n} $$ Let $\alpha = \frac{|\mathcal{S}|}{2^n}$ then this becomes $$2\alpha \le 1-\alpha+\alpha^2 \iff \alpha^2-3\alpha+1 \ge 0 \iff \alpha < \frac{3-\sqrt{5}}{2}$$ Remark: The condition that $|\mathcal{S}| = |\mathcal{T}|$ is actually weaker than it looks; one can move/add sets "freely" between these two carefully.

Solved with megarnie (at HMMT February!). Let $a,b$ be (TBD) positive integer parameters and set $n=ab.$ Let $\gamma = \frac{3-\sqrt{5}}{2}$ and the key idea is $1 - 2\gamma + \gamma^2 = \gamma.$ Let the family $T$ be all subsets of $\{1,2, \dots n\}$ that include at least one integer $r \pmod{b}$ for any residue $r.$ Let the family $S$ be all subsets of $\{1,2, \dots n\}$ not in $T$ that include all integers $r \pmod{b}$ for some residue $r$. First, $|T| = (2^{a} - 1)^{b}.$ To count $|S|$ first subtract from $2^{ab}$ the number of subsets that don't have all the integers $r \pmod{b}$ for any residue $r,$ which is $(2^{a} - 1)^{b}.$ This is $2^{ab} - (2^{a} - 1)^{b}$ and now we have to subtract elements in $T.$ Note the number of subsets of $\{1,2, \dots n\}$ that include at least one integer, but not all integers $r \pmod{b}$ for any residue $r$ is $(2^{a} - 2)^{b}.$ So our final count is $$|S| = 2^{ab} - (2^{a} - 1)^{b} - ((2^{a} - 1)^{b} - (2^{a} - 2)^{b}) = 2^{ab} - 2(2^{a}-1)^{b} + (2^{a} - 2)^{b}.$$ Choose very large $a$ and $b$ so that $\left( \frac{2^{a} - 1}{2^{a}} \right)^{b} \approx \gamma,$ so $\frac{|T|}{2^{ab}}$ is arbitrarily close to $\gamma.$ But now see that $\frac{|S|}{2^{ab}} = 1 - 2\left( \frac{2^{a}-1}{2^{a}} \right)^{b} + \left( \frac{2^{a}-2}{2^{a}} \right)^{b}$ is arbitrarily close to $1 - 2 \gamma + \gamma^2 = \gamma$ as well, noting the approximation $(1-\epsilon )^{2} \approx 1 - 2\epsilon $ for small $\epsilon.$ $\blacksquare$

It turns out that CANBANKAN's bounding for $\alpha$ that don't work and the standard bounding for $\alpha$ that don't work ends up being are the same idea. Here's a sol with motivation for said bounding. We claim that $\alpha$ works iff $\alpha < \frac{3 - \sqrt{5}}{2}$. Claim: $\alpha < \frac{3 - \sqrt{5}}{2}$ works. Proof. Let $n = ab$ and let $a = c \cdot 2^b$. Take the limit as $a, b \to \infty$. Take a set of $2^n$ black and white colorings of a $a \times b$ grid, where black represents inclusion. We now assign elements of the set to the families $\mathcal{S}, \mathcal{T}$. Assign all grids with a black row to $\mathcal{S}$. Assign all grids with a black element in each row to $\mathcal{T}$. Then greedily remove duplicates from the family with more elements. Initially, $\mathcal{S}$ has size around $2^{n} - (2^b - 1)^a$ which taking the limit is $2^n(1 - e^{-c})$. Similarly, $\mathcal{T}$ has size around $(2^b - 1)^a$ which limits to $2^n(e^{-c})$. There are around \[ \sum_{k=1}^{a} \binom{a}{k} (2^b - 2)^{a-k} = (2^b - 1)^a - (2^b - 2)^a = (2^b -2)^a \left(\left(\frac{2^b - 1}{2^b - 2}\right)^a - 1\right) \]sets that are duplicated, which has limiting behavior $2^n \cdot e^{-c}(1 - e^{-c})$. We then want to find the $c$ which maximizes \[ \min(1 - e^{-c}, e^{-c}) - \frac{1}{2} \max(0, (e^{-c}(1 - e^{-c}) - \left|1 - 2e^{-c}\right|)) \]This is symmetric when $e^{-c}$ is replaced by $1 - e^{-c}$, so WLOG let $e^{-c} < \frac{1}{2}$. This then simplifies as $x - \frac{1}{2} \max(0, (-x^2 + 3x - 1))$ for $x = e^{-c}$ which occurs with $c = \log\left(\frac{3+\sqrt{5}}{2}\right)$ with a value of $\frac{3 - \sqrt{5}}{2}$. $\blacksquare$ Remark: This can be thought of taking the upward-closed completion of the sets over rows and the sets with one element from each row. We now jerry rig this to prove the bound $\alpha \le \frac{3 - \sqrt{5}}{2}$ which finishes by irrationality. WLOG take the families $\mathcal{S} = \{S_i\}, \mathcal{T} = \{T_i\}$ be upward closed. WLOG let $\mathcal{S} \ge \mathcal{T}$ as well. Then we get a eerily similar expression to the earlier proof that the value of $\alpha \cdot 2^n$ is at most \[ \min(\left|\mathcal S\right|, \left|\mathcal T\right|) - \frac{1}{2} \max\left(0, \left(\left|\mathcal S \cap \mathcal T\right| - \left(\left|\mathcal S\right| - \left|\mathcal T\right|\right)\right)\right) \]for the result on $\alpha$. If we show that $\left|\mathcal S\right| + \left|\mathcal T\right| \le 2^n$ and that $\left|\mathcal S \cap \mathcal T\right| \ge \frac{\left|\mathcal S\right|\left|\mathcal T\right|}{2^n}$ and $\left|\mathcal S\right| - \left|\mathcal T\right| \le 1 - 2\left|\mathcal S\right|$ then we actually get the exact same bound as we want. So let's prove these things. The first and third claim are actually equivalent. Claim: Let $\mathcal{S}$ and $\mathcal{T}$ be two families of sets which are upward closed. Then if $s \cap t \ne \emptyset$ for each $s \in \mathcal{S}, t \in \mathcal{T}$, it follows that $\left|\mathcal{S}\right| + \left|\mathcal{T}\right| \le 2^n$. Proof. FTSOC suppose not. Then by the size constraint, there exist some set $s$ such that $s \in \mathcal{T}$ and $[n] \setminus s \in \mathcal{S}$, this is a direct contradiction. $\blacksquare$ Claim: [Kleitman's Theorem] $\left|\mathcal{S} \cap \mathcal{T}\right| \ge \frac{\left|\mathcal{S}\right|\left|\mathcal{T}\right|}{2^n}$ Proof. Let $\mathcal{S}_1$ be the subset of $\mathcal{S}$ containing $1$, let $\mathcal{S}_2$ be the subset not containing $1$. Define $\mathcal{T}_1, \mathcal{T}_2$ simlarly. Then \begin{align*} \left|\mathcal{S}\right| \cap \left|\mathcal{T}\right| &= \left|\mathcal{S}_1 \cap \mathcal{T}_1\right| + \left|\mathcal{S}_2 \cap \mathcal{T}_2\right| \\ &\ge \frac{1}{2^{n-1}} (\left|\mathcal{S}_1\right|\left|\mathcal{T}_1\right| + \left|\mathcal{S}_2\right|\left|\mathcal{T}_2\right|) \\ &\ge \frac{1}{2^n} (\left|\mathcal{S}_1\right| + \left|\mathcal{S}_2\right|)(\left|\mathcal{T}_1\right| + \left|\mathcal{T}_2\right|) = \frac{1}{2^n} \left|\mathcal{S}\right|\left|\mathcal{T}\right| \end{align*}which finishes. $\blacksquare$

Let $n=ab$ and let partition $\{1,2,\dots,n\}$ into $b$ subsets of size $a$. Let $S$ be the family of all subsets that intersects all the subsets and let $T$ be the family of all subsets that is the superset of at least one of the subsets. $~$ Note that $|S|=(2^a-1)^b$ because for each one of the partitioned subsets, there are $2^a-1$ ways to choose elements such that at least one of them is chosen. Note that $|S\setminus T|=(2^a-2)^b$ because for each one of the partitioned subsets, there are $2^a-2$ ways to choose elements such that at least one of them is chosen, but not all of them is chosen. Then, note that for every set not in $T$, it is missing at least one element from each subset, so $|T|=2^n-(2^a-1)^b$. Note that \[|S\setminus T|+|T|=|T\setminus S|+|S|\]therefore $|T\setminus S|=(2^a)^b-2(2^a-1)^b+(2^a-2)^b$ and $|S|=(2^a-1)^b$ $~$ Clearly, if $x\in S$ and $y\in T\setminus S$ then $x\cap y\neq \emptyset$. Let $b$ be approximately $2^a\ln\left(\tfrac{3-\sqrt{5}}{2}\right)$ for some extremely large $a$, then \[|S|=2^n\left(\left(1-\frac{1}{2^a}\right)^{2^a}\right)^{\ln\left(\tfrac{3-\sqrt{5}}{2}\right)}=2^n e^{\ln\left(\tfrac{3-\sqrt{5}}{2}\right)}=2^n\left(\frac{3-\sqrt{5}}{2}\right)\]and similarly \[|T\setminus S|=2^n\left(1-2\left(\tfrac{3-\sqrt{5}}{2}\right)+\left(\tfrac{3-\sqrt{5}}{2}\right)^2\right)=2^n\left(\frac{3-\sqrt{5}}{2}\right)\]so we're done.