Define the mexth of \(k\) sets as the \(k\)th smallest positive integer that none of them contain, if it exists. Does there exist a family \(\mathcal F\) of sets of positive integers such that for any nonempty finite subset \(\mathcal G\) of \(\mathcal F\), the mexth of \(\mathcal G\) exists, and for any positive integer \(n\), there is exactly one nonempty finite subset \(\mathcal G\) of \(\mathcal F\) such that \(n\) is the mexth of \(\mathcal G\). Proposed by Espen Slettnes
Problem
Source: ELMO Shortlist 2023 C5
Tags: Elmo, combinatorics
30.06.2023 19:13
02.07.2023 21:26
31.12.2023 22:05
The answer is yes. By taking the complement it suffices to exhibit a family of sets of positive integers such that the $k$-th smallest number in the intersection of $k$ sets (taken across all positive integers $k$) exists and spans all positive integers. We construct a family $\{S_0,S_1,\ldots\}$ as follows. On each interval $[2^i,2^{i+1})$ (in increasing order of $i$), add $\{2^i,\ldots,2^{i+1}-1\}$ to $S_i$. Then for all $0 \leq j<i$, duplicate $S_j$ by shifting it up $2^i$ (so $x+2^i$ gets added to $S_j$ if $x \in S_j$ already) and add $2^i$. For concreteness, \begin{align*} S_0&=\{1,2,3,4,5,6,\ldots\},\\ S_1&=\{2,3,4,6,7,8,\ldots\},\\ S_2&=\{4,5,6,7,8,12,\ldots\},\\ \vdots \end{align*}By induction, it is easy to prove that the $k$-th smallest number in the intersection of $k$ sets $S_{i_1},\ldots,S_{i_k}$ is $2^{i_1}+\cdots+2^{i_k}$, finishing the problem by uniqueness of the binary representation. $\blacksquare$