At most how many $42$-element subsets of $\{1,2,\dots,2018\}$ are such that, for any two, one consists of the $42$ smallest elements of their union? Here is a problem based on a problem from Kurdhak Jozsef Hungarian mathematical olympiad 2016. This problem is easier than that, and I hope there exist an easier solution for this problem than the olympiad problem’s solution.

At most how many $42$-element subsets can we select from $\{1,2,\dots,2018\}$ such that for any two selected subsets, one of the subsets consists of the $42$ smallest elements of their union?

Note that in the original problem, the numbers $42,2018$ are not given.
 A: 
Claim.  Let $n$ and $k$ be arbitrary positive integers such that $n\geq k$.  Let $\mathcal{S}$ denote the set of all $k$-subsets of $[n]:=\{1,2,\ldots,n\}$.  Suppose that $\mathcal{C}$ is a subcollection of $\mathcal{S}$ such that, for any $A,B\in\mathcal{C}$, either $A$ or $B$ is composed by the $k$ smallest elements of $A\cup B$.  Then, $$|\mathcal{C}|\leq n-k+1$$ and the inequality is sharp.

It is easy to see that the inequality is sharp.  The subfamily
$$\big\{\{1,2,\ldots,k-2,k-1,j\}\,\big|\,j\in\{k,k+1,k+2,\ldots,n\}\big\}$$
satisfies the requirement, and it contains $n-k+1$ sets.
Partially order $\mathcal{S}$ by decreeing that, for $A,B\in \mathcal{S}$, $A\leq B$ if $A$ consists of the $k$ smallest elements of $A\cup B$.  It is easy to see that $\leq$ is indeed an order relation.  The question is to determine the size $s$ of the largest chain in $\mathcal{S}$.  We know from the previous paragraph that $s\geq n-k+1$.
By Mirsky's Theorem, $s$ equals the smallest number of antichains in $\mathcal{S}$ which form a partition of $\mathcal{S}$.  Hence, if we can exhibit $n-k+1$ antichains that partition $\mathcal{S}$, then we will have proven that $s=n-k+1$.
For $j=k,k+1,k+2,\ldots,n$, let $\mathcal{A}_j$ denote the subset of $\mathcal{S}$ consisting of sets $A$ such that the maximum element of $A$ is $j$.  It is easy to see that $\mathcal{A}_j$ is an antichain.  Furthermore, the sets $\mathcal{A}_k,\mathcal{A}_{k+1},\mathcal{A}_{k+2},\ldots,\mathcal{A}_{n}$ form a partition of $\mathcal{S}$.  The proof is now complete.
In particular, for the problem at hand, $n=2018$ and $k=42$.  Therefore, the largest possible collection of $42$-subsets of $\{1,2,\ldots,2018\}$ with the desired property has $$2018-42+1=1977$$ elements.


Generalization.  Let $n$, $m$, and $k$ be arbitrary positive integers such that $n\geq m\geq k$.  Let $\mathcal{S}$ denote the set of all $m$-subsets of $[n]:=\{1,2,\ldots,n\}$.  Suppose that $\mathcal{C}$ is a subcollection of $\mathcal{S}$ such that, for any $A,B\in\mathcal{C}$, either $A$ or $B$ contains the $k$ smallest elements of $A\cup B$.  Then, $$|\mathcal{C}|\leq \binom{n-k+1}{m-k+1}$$ and the inequality is sharp.

I decided to give a proof of the generalization above, since the proof here does not extend from the proof above in a very straightforward manner.   First of all, the inequality is sharp because the family
$$\Big\{\{1,2,\ldots,k-1\}\cup X\,\Big|\,X\subseteq\{k,k+1,k+2,\ldots,n\}\text{ and }|X|=m-k+1\Big\}$$
fulfills the requirement.  
Write $\mathcal{T}$ for the family of all subsets of $[n]$ with $m-k$ elements.  Equip $\mathcal{T}$ with any total order $\preceq$.  Next, we define a partial order $\leq$ on $\mathcal{S}$ as follows.  Let $A$ and $B$ be arbitrary elements of $\mathcal{S}$.  We say that $A\leq B$ if both conditions below are satisfied:


*

*$A$ contains the smallest $k$ elements $t_1,t_2,\ldots,t_k$ in $A\cup B$, and

*either $|A\setminus Z|<|B\setminus Z|$, where $Z:=\{t_1,t_2,\ldots,t_k\}$, or $|A\setminus Z|=|B\setminus Z|=m-k$ and $(A\setminus Z)\preceq (B\setminus Z)$.


It is not difficult to show that $\leq$ is indeed a partial order on $\mathcal{S}$.
The rest goes as before.  We only need to find $\displaystyle\binom{n-k+1}{m-k+1}$ antichains in $\mathcal{S}$  that form a partition of $\mathcal{S}$.  Let $\mathcal{F}$ denote the family of $(m-k+1)$-element subsets of $\{k,k+1,k+2,\ldots,n\}$.  For each $F\in\mathcal{F}$, define $\mathcal{A}_F$ to be the subcollection of $\mathcal{S}$ consisting of sets whose $m-k+1$ largest elements belong to $F$.  Then, the subcollections $\mathcal{A}_F$ for $F\in\mathcal{F}$ are antichains that partition $\mathcal{S}$, and Mirsky's Theorem finishes the proof.
