Motivation. My eldest son starts school tomorrow. His class is split in two groups of $10$ students each. From time to time, the groups are rearranged. I wondered how many rearrangements are needed until every student has been in the same group with every other student at least once. This led to a more general question.
Question. $f: \omega \to \{0,1\}$ is said to be fair if the preimages $f^{-1}(\{0\})$ and $f^{-1}(\{1\})$ are both infinite. Is there a positive integer $n$ and fair functions $f_i: \omega \to \{0,1\}$ for $i \in \{0,\ldots,n-1\}$ with the following property?
For all $a,b\in \omega$ there is $i \in \{0,\ldots,n-1\}$ such that $f_i(a) = f_i(b)$.
If yes, how small can $n$ be?
Best Answer
Let $n=3$ and partition $\omega$ into three infinite sets, $X_0, X_1, X_2$. The functions $f_0,f_1,f_2$ defined by $$f_i(x) = \begin{cases} 1 & \mbox{if $x$ belongs to } X_i \\ 0 & \mbox{otherwise} \end{cases}$$ are fair functions, and for all $a, b \in \omega$ there is $i \in \{0,1,2\}$ such that $f_i(a) = f_i(b) = 0.$
On the other hand, this is impossible when $n=2$. If $f_0,f_1$ are any two fair functions from $\omega$ to $\{0,1\}$, assume without loss of generality that $f_0(0) = f_1(0) = 0$ and let $a,b \in \omega$ be such that $f_0(a)=1$ and $f_1(b)=1$. There must be $i \in \{0,1\}$ such that $f_i(a)=f_i(b)$. However, if $i=0$ then we have $f_0(b) = f_1(b) = 1$ so there is no $j \in \{0,1\}$ with $f_j(0) = f_j(b)$, while if $i=1$ then we have $f_0(a) = f_1(a) = 1$ so there is no $j \in \{0,1\}$ with $f_j(0) = f_j(a)$.