combinatoricscontest-math
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.
For a given $n$, this answer by r9m provides a tool to improve the upper bound for the left hand side by looking for the set of $\{x_k\}_{k=1}^n$ such that $c(n)=\max\limits_{k \in \{1,2,\cdots,n\}}\{c_k\}$ is minimized. It turned out to more convenient to consider a sequence $\{y_k\}_{k=2}^n$, where $y_{k}=x_k/x_{k-1}$ and $d(n)=2-c(n)$. Below I present the best values of $d(n)$ for small $n$ and the (componentwise almost optimal) sequences $\{y_k\}$ providing them which I found (the decimal fractions below are truncated, not rounded):
n=4 0.738307
2.195696 1.989904 2.218204
n=5 0.696237
2.071728 1.818972 1.821304 2.083424
n=6 0.660482
1.9875 1.7125 1.6625 1.7250 2.0000
n=7 0.632358
1.925 1.660 1.575 1.575 1.655 1.930
n=8 0.611866
1.8912 1.6148 1.5254 1.5012 1.5230 1.6106 1.8896
It suggests that there exists of a general pattern for $\{y_k\}$. Below are graphs for $\{y_k\color{red}{-1}\}$ for $n=20$ (which provides $d(20)\ge 0.4750702$) and $n=100$ (which provides $d(100)\ge 0.3156195$). I remark that the last value is more than twice bigger than $\frac{7\ln 2}{8\ln 100}=\frac{7}{8\log_2 100}=0.1317006\dots$, so I guess that analytic description of the pattern can lead to a proof of a strong inequality. As an aid I provide below the (rounded) sequence $\{y_k-1\}$ for $n=100$.
0.568813293
0.339731947
0.250658592
0.202100545
0.171168765
0.149589419
0.133606711
0.121254158
0.111401006
0.103346372
0.096632292
0.090945372
0.086065313
0.081830815
0.078121791
0.074847124
0.071934277
0.069329774
0.06698533
0.064867893
0.062946908
0.06119601
0.059597855
0.058134021
0.056788616
0.055549986
0.054408614
0.053355081
0.052381164
0.051477808
0.050642813
0.049869636
0.049150712
0.048487213
0.047870011
0.047300624
0.046773765
0.046287301
0.045839285
0.045426464
0.045050178
0.044705127
0.044392893
0.044110562
0.043858542
0.043635059
0.043439437
0.043271504
0.043130179
0.043015646
0.042927185
0.042864435
0.042829168
0.042819848
0.04283657
0.042881058
0.042952044
0.043050421
0.043179212
0.043337126
0.043524287
0.043744926
0.043999354
0.044286068
0.044612369
0.044977226
0.045381648
0.045832647
0.046329917
0.046878054
0.047482742
0.048146738
0.048877411
0.049679262
0.05056174
0.051533042
0.052601587
0.053782408
0.055087981
0.05653489
0.058146492
0.059945903
0.06196218
0.06423862
0.066818627
0.069766721
0.073161067
0.077108166
0.081748879
0.087280503
0.093985299
0.10227286
0.11278736
0.126570241
0.145453179
0.172979978
0.217060498
0.299864157
0.518985805
Let us fix an odd prime $\require{cancel}p$, and let $\bar{a}_n$ be the reduction of $a_n$ modulo $p$, i.e., as members of $\mathbb{Z}/p=\mathbb{F}_p$. There is a standard trick of letting $$ \mathbf{b}_n=\begin{bmatrix}\bar{a}_{n+1}\\\bar{a}_n\end{bmatrix}\in\mathbb{F}_p^2, $$ which converts the second order difference equation into a first-order difference equation (at the cost of having a vector equation rather than a scalar one): $$ \mathbf{b}_{n+1}=T\,\mathbf{b}_n,\quad T:=\begin{bmatrix}k&1\\1 & 0\end{bmatrix},\quad \mathbf{b}_0=\begin{bmatrix}1\\0\end{bmatrix}. $$ So $\mathbf{b}_{n+1}$ depends only on $\mathbf{b}_n$. Note that $\det T=-1$ so $T^{-1}$ exists.
By pigeonhole, there exists $0\leq i<j\leq p^2$ such that $\mathbf{b}_i=\mathbf{b}_j$. Applying $T^{-i}$, you get $\mathbf{b}_{j-i}=\mathbf{b}_0$, and applying $T^n$ gives $\mathbf{b}_{n+j-i}=\mathbf{b}_n$ for all $n$. So $T(p)$ exists and is equal to the minimal period of $(\mathbf{b}_n)_{n\geq 0}$. (This implies existence of $m(p)$, which is clearly $\leq T(p)$ by putting $j=0$ in the definition.)
For (i):
we consider what $\mathbf{b}_{m(p)},\mathbf{b}_{2m(p)},\mathbf{b}_{3m(p)},\dots$ could be. The last coordinate must be $0$, but the first coordinate isn't fixed.
However, we know
Claim: $$a_{km(p)+1}\not\equiv 0\pmod{p}$$ Proof. If $a_{km(p)+1}\equiv 0\pmod{p}$, then $\mathbf{b}_{km(p)}=\mathbf{0}$. Applying $T^{-km(p)}$ gives $\mathbf{b}_0=\mathbf{0}$, contradiction. $\square$
We have:
$T^{m(p)}\mathbf{b}_0=\bar{a}_{m(p)+1}\mathbf{b}_0$, so $$T^{m(p)(p-1)}\mathbf{b}_0=(\bar{a}_{m(p)+1})^{p-1}\mathbf{b}_0=\mathbf{b}_0$$ by Fermat's little theorem, and hence $T(p)\leq m(p)(p-1)$.
For (ii):
If $T(p)=m(p)(p-1)$, then $(\bar{a}_{m(p)+1})^j$ for $j=1,2,\dots,p-1$ are all distinct, i.e., $\mu=\bar{a}_{m(p)+1}$ is a generator of $\mathbb{F}_p^\times$. We have $\{\mu,\mu^2,\dots,\mu^{p-1}\}=\{1,2,\dots,p-1\}$ and so applying Wilson's theorem gives $\prod_{k=1}^{p-1}\mu^k=(p-1)!=-1$.
Hence
\begin{align}\prod_{\substack{1\leq j\leq T(p)-1\\m(p)\nmid j}}\bar{a}_j &=\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\bar{a}_{km(p)+j}\\ &=\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}(\mu^k\bar{a}_j)\\ &=\left(\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\mu^k\right)\left(\prod_{k=1}^{p-1}\prod_{j=1}^{m(p)-1}\bar{a}_j\right)\\ &=\left[\prod_{j=1}^{m(p)-1}\left(\prod_{k=1}^{p-1}\mu^k\right)\right]\cancelto{1}{\color{red}{\left(\prod_{j=1}^{m(p)-1}\bar{a}_j\right)^{p-1}}}\\ &=(-1)^{m(p)-1} \end{align}
as claimed.
Best Answer
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.
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:
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.