Set $X$ is called fancy if it satisfies all of the following conditions: The number of elements of $X$ is $2022$. Each element of $X$ is a closed interval contained in $[0, 1]$. For any real number $r \in [0, 1]$, the number of elements of $X$ containing $r$ is less than or equal to $1011$. For fancy sets $A, B$, and intervals $I \in A, J \in B$, denote by $n(A, B)$ the number of pairs $(I, J)$ such that $I \cap J \neq \emptyset$. Determine the maximum value of $n(A, B)$.
Problem
Source: FKMO 2022 Problem 6
Tags: combinatorics, Sets, interval
23.04.2022 22:57
@below sorry you're right and nice solution
27.04.2022 07:24
The answer is $3\cdot 1011^2$. Construction is $A$ being $1011$ copies of $\{ [0,0.4], [0.45,1]\}$ and $B$ being $1011$ copies of $\{ [0,0.46], [0.5,1]\}$. Proof of optimality: We first make a circular optimization. Claim: If $b\le c$, then replacing two intervals $[a,c], [b,d]$ in $A$ by $[a,d], [b,c]$ doesn't change the answer. Proof: If an interval in $B$ is not disjoint with $[b,c]$ then it originally and is now not disjoint to both intervals. If an interval in $B$ is disjoint with $[b,c]$, it cannot be not disjoint to $[a,b]$ and $[c,d]$ at the same time. Therefore, if it is not disjoint to one of them, it will still be not disjoint to one of them after replacing the intervals. Let a set $X$ be $(a,b)-$good if $|X|=a$, each element of $X$ is a closed interval contained in $[0, 1]$, and for any real number $r \in [0, 1]$, the number of elements of $X$ containing $r$ is less than or equal to $b$. Let $f(a,b,c,d)$ be the maximum value $n(A,B)$ can obtain where $A$ is a $(a,b)$-good set and $B$ is a $(c,d)$-good set. I will prove $f(a,b,c,d)\le bc+ad-bd$, which solves the problem by substituting $a=c=2k, b=d=k \to f(2k,k,2k,k)\le 3k^2$ Base Case: $b=d=1$. In this case, we do a smaller induction on $a+c$. If $\min\{a,c\}=1$ this is clear. Otherwise, let $[l_1, r_1], [l_2,r_2]$ be the two leftmost intervals (we can compare positions of intervals since they are disjoint) in $A$ (note $r_1<l_2$) and $[x_1,y_1], [x_2,y_2]$ be the two leftmost intervals in $B$. I claim either $[l_1,r_1]$ or $[x_1,y_1]$ has nonempty intersection with at most one interval from the other set; if $[l_1,r_1]$ has nonempty intersection with $[x_k,y_k]$ for some $k\ge 2$, then $y_1<x_2\le x_k \le r_1 \le l_2$. Therefore, $[x_1,y_1]$ has empty intersection with $[l_j,r_j]$ for all $j\ge 2$, so we remove $[x_1,y_1]$ and induct down. Inductive Step: WLOG, $b\ge 2$, or we swap $(a,b)$ with $(c,d)$. Let $S$ be the set of intervals in $A$ that are not contained by another interval (if multiple intervals are the same and not strictly contained by a bigger interval, pick an arbitrary one). Then note $S$ satisfies criteria for a $(|S|,1)$-good set and $A\backslash S$ satisfies the criteria for a $(a-|S|, b-1)$-good set. Then $n(A,B)=n(S,B)+n(A\backslash S, B) \le f(|S|,1,c,d)+f(a-|S|,b-1,c,d) = |S|d + c - d + (a-|S|)d + (b-1)c - (b-1)d=ad+bc-bd$, completing the induction.
27.04.2022 07:25
asbodke wrote: For all integers $i$ between $1$ and $1011$, interval $i$ does not share any real number with interval $i+1011$. Indeed, if it did, then intervals $i,\,i+1,\,\dots, i+1011$ would all share this real number, contradiction. This claim is wrong. Replace 1011 by 2, and consider the counterexample $A=\{ [0,1], [0,0.2], [0.4, 0.5], [0.8,0.9]\}$
29.04.2022 19:07
Let a set $A$ is called $n$-fancy set if we can change $1011$ and $2022$ in the condition to $n$ and $2n$. Then we can also use induction in two variables $m, n$ with the following statement: If $A$ is $m$-fancy and $B$ is $n$-fancy, $n(A, B)\leq 3mn$. We are going to do an induction on $m+n$. First, we can easily show the base case, $m=n=1$. Before solving, we should apply an idea that we can replace two intervals $(a,d)$ and $(b,c)$ to $(a,c)$ and $(b, d)$ without changing any conditions. $(a\leq b\leq c\leq d)$ The main idea is the following claim. Claim. If $m\geq 2$, we can choose two elements $x$ and $y$ in $A$ such that $x\cap y=\emptyset$ and $A-\{x, y\}$ is $(m-1)$-fancy. pf) Let's think about a set of real numbers in $[0,1]$ such that there are exactly $m$ elements in $A$ which contain it. We can express this set into an union of closed intervals. Let these intervals be $I_1, \cdots, I_k$. If $k=0$, we can choose any non-intersecting two elements in $A$ (there exists), so I will assume $k>0$. By the definition, all elements in $A$ contain each intervals or do not intersects. If an element in $A$ contains at least one of the intervals, I will denote this element $(i, j)$ as it means the element exactly contains $I_i, \cdots, I_j$. Case 1. There are no $(1, k)$: Then we can find the largest $l(<k)$ such that $x=(1,l)$ is in $A$. Since all $m$ elements which contains $I_1$ do not contain $I_{l+1}, \cdots, I_k$, the rest $m$ elements in $A$ should contain $I_{l+1}, \cdots, I_k$. If all of these elements contain $I_l$, it is a contradiction since $m+1$ elements contain $I_l$. Hence, there is an element $y=(l+1, k)$ and we would choose $x$ and $y$. Case 2. $A$ contain some $(1, k)$: If there is an element $x\in A$ such that does not contain any intervals, $x$ would be located before $I_1$ or after $I_k$. WLOG assume the former, then we can choose $y$ such that its lower bound is equal to $I_1$'s lower bound. Then we would choose $x$ and $y$. Therefore, we can assume that all elements in $A$ contain at least one interval. Let $t$ be the number of $(1,k)$. The rest of the elements should have a form of $(1, i)(i<k)$ or $(j,k)(j>1)$ because of the replacing idea. Furthermore, we know that the number of the former and the latter are both $m-t$ by counting the elements which contain $I_1$ and $I_k$, respectively. Therefore, $2m=|A|=t+2(m-t)=2m-t<2m$, contradiction. By considering all the cases, the claim is proved. This claim means that we can apply an inductive hypothesis by removing two elements in a set. If we do it as $A'=A-\{x,y\}(|A|\geq 2)$, we can say that $n(A', B)\leq 3(m-1)n$. Starting from the base case, we would increase $m$ by 1. It holds since $n(A, B)=n(A',B)+n(\{x,y\},B)\leq3(m-1)+3=3m$ by the inductive hypothesis and the base case. We partially showed the statement if one of the size of the set is $1$. Then we can conclude for an arbitrary situation by $n(A,B)=n(A',B)+n(\{x,y\},B)\leq 3(m-1)n+3n=3mn$ using induction. $\therefore$ We proved the statement by induction and we can get the answer $3\cdot 1011^2$ by substituting $m=n=1011$.
26.05.2022 01:56
CANBANKAN wrote: Let $S$ be the set of intervals in $A$ that are not contained by another interval (if multiple intervals are the same and not strictly contained by a bigger interval, pick an arbitrary one). Then note $S$ satisfies criteria for a $(|S|,1)$-good set and $A\backslash S$ satisfies the criteria for a $(a-|S|, b-1)$-good set. I think we should choose all the big interval that do not intersect with each other as the set S.
26.05.2022 06:38
nice problem
17.09.2023 04:45
Really nice. Here is a non-inductive solution (except for the proof of an auxillary claim) The answer is $3\cdot 1011^2$, which is achievable by making $A$ contain $1011$ copies each of $[0,0.1]$ and $[0.2,1]$, and $B$ contain $1011$ copies each of $[0,0.8]$ and $[0.9,1]$ (these aren't distinct but it's trivial to make them distinct without changing anything). I will now prove this is maximal. The main part of this is is the following claim. Claim 1: We can partition $A$ into at most $1011$ (nonempty) subsets such that each subset contains pairwise disjoint intervals. Proof: We will attempt to greedily construct subsets as follows: for each subset, repeatedly pick the subset with the smallest left endpoint (that isn't already part of a subset) that doesn't overlap any of its current elements, until we cannot. Repeat this until we have $1011$ such subsets. Then, if some interval $I$ is not part of a subset, its left endpoint must belong to some interval in each of the $1011$ subsets. But this means that there are $1012$ elements of $A$ containing some $r \in [0,1]$: contradiction. $\blacksquare$ We also need a second "auxillary" claim. Claim 2: Suppose we have two nonempty sets $S,T$ of pairwise disjoint (closed) intervals. Then there are at most $|S|+|T|-1$ pairs $(x,y)$ with $x \in S$ and $y \in T$ such that $x \cap y \neq \emptyset$. Proof: Induct with the base case of $\min(|S|,|T|)=1$ being obvious. Consider the leftmost intervals of $S$ and $T$ and call them $s$ and $t$ respectively. If $s$ has a right endpoint at most that of $t$, then delete $s$, which removes at most one pair (namely $(s,t)$), and induct down. Otherwise, delete $t$ and induct down. $\blacksquare$ Now perform the partition described in claim 1, and suppose this partitions $A$ into $a \leq 1011$ (nonempty) subsets with sizes $x_1,\ldots,x_a$ and $B$ into $b \leq 1011$ (nonempty) subsets with sizes $y_1,\ldots,y_b$. By summing over pairs of subsets and using claim $2$, it follows that $n(A,B)$ is at most $$\sum_{i=1}^a\sum_{j=1}^b (x_i+y_j-1)=b\sum_{i=1}^a x_i+a\sum_{j=1}^b y_b-ab=2022a+2022b-ab.$$Then, $$2022a+2022b-ab \leq 3\cdot 1011^2 \iff 1011^2 \leq (2022-a)(2022-b),$$which is true since $2022-a,2022-b \geq 1011$. $\blacksquare$ Remark: This solution more or less comes from arriving at the false idea in #2 and trying to fix it. In particular, the counterexample that was given in #3 (which I also found) still obeys claim 1, and we can work backwards and notice that if claim 1 is true then the problem is solved. I think claim 1 is motivated, since it feels intuitively true. Perhaps a helpful visual is to imagine stacking together equal-height "blocks" in a large box of length $1$.