# Finite $k$-set-respecting splitting of $\mathbb{N}$

Motivation. My sons participated in a large football tournament recently; everyone wanted to be in a team with everyone else at least once. Tricky!

Formulation of the question. For any positive integer $$k\in\mathbb{N}$$, let $$\ \binom {\mathbb N} k\$$ denote the collection of $$k$$-element subsets of $$\mathbb{N}.\$$ Let $${\cal I}$$ be the collection of subsets of $$\mathbb{N}$$ that are both infinite and co-infinite (the complement is infinite).

Fix an integer $$k\geq 2$$. Is there a finite family $$\ {\cal S}\subseteq {\cal I}\$$ such that for every $$\ F\in\binom {\mathbb N} k\$$ there is $$T\in{\cal S}\$$ with $$F\subseteq T$$ or $$F\subseteq (\mathbb{N}\setminus T)$$?   If yes, what is the smallest size such a family $${\cal S}$$ can have, in terms of $$k$$?

Note. I originally posted this question for $$k=2$$ and arbitrary subsets of $$\mathbb{N}$$, not just infinite/co-infinite ones. Zach Teitler quickly gave an elegant solution and suggested this generalization. First it seemed $$k=2$$ was solved, but it turns out $$k=2$$ is still unresolved.

• I think $S=\{\{1\},\{2\},\{3\}\}$ works. Nov 20 at 13:28
• Right @ZachTeitler - sorry. Can it be done with sets that are infinite and co-infinite? Will change the question accordingly Nov 20 at 13:30
• Size $|S|=2$ is clearly impossible. How about $|S|=3$ like this: let each $S_i$, $i=1,2,3$, be the set of integers congruent to $0$ or $i$ modulo $4$. Nov 20 at 13:36
• This is a fun question. How far can we generalize, eg, to $k$-team games? Nov 20 at 13:40
• @WlodAA: see meta.mathoverflow.net/questions/5508/… for a fix. Nov 20 at 20:51

For $$k\ge2$$, if we partition $$\mathbb N$$ into $$k+1$$ infinite sets $$S_0,S_1,\dots,S_k$$, then each $$S_i$$ is coinfinite, and every $$k$$-element subset of $$\mathbb N$$ is contained in the complement of some $$S_i$$.
This is best possible: for $$k\ge2$$, given $$k$$ nonempty proper subsets of $$\mathbb N$$, there is a $$k$$-element set which meets all of those sets and their complements. The proof is by induction.
For $$k=2$$, suppose $$S_1$$ and $$S_2$$ are nonempty proper subsets of $$\mathbb N$$. If neither is contained in the other, choose $$x_1\in S_1\setminus S_2$$ and $$x_2\in S_2\setminus S_1$$; if one is contained in the other, say $$S_1\subseteq S_2$$, choose $$x_1\in S_1$$ and $$x_2\in\mathbb N\setminus S_2$$. In either case the set $$\{x_1,x_2\}$$ meets each of the sets $$S_1,S_2,\mathbb N\setminus S_1,\mathbb N\setminus S_2$$.
For the induction step, let $$S_1,\dots,S_k,S_{k+1}$$ be nonempty proper subsets of $$\mathbb N$$, and let $$F=\{x_1,\dots,x_k\}$$ be a $$k$$-element set which meets $$S_i$$ and $$\mathbb N\setminus S_i$$ for $$1\le i\le k$$. Choose $$x_{k+1}\in\mathbb N$$ so that $$x_{k+1}\in S_{k+1}\iff x_1\notin S_{k+1}$$. Then the set $$F\cup\{x_{k+1}\}$$ has at most $$k+1$$ elements and meets $$S_i$$ and $$\mathbb N\setminus S_i$$ for $$1\le i\le k+1$$.
• @SamHopkins I think the "cofinite" bit is a little bug that crept in -- but the elegance of this archetypical bof-solution lies in the following bit (I think): if $F$ has $n$ elements and $S_0,\ldots S_n$ are $n+1$ sets partitioning $\mathbb{N}$, then $F$ cannot intersect all of the $S_i$. So suppose it doesn't intersect $S_j$. Then $F\subseteq (\mathbb{N}\setminus S_j)$. (Apologies for this laudatory speech on bof, but I have seen a lot of answers by him, many of them so simple and to the point like a simple and elegant chess move that still most chess players don't find.) Nov 20 at 20:55