0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ $f$ defined by $f(0)=0,f(a)=1$ for all $a>0$ deals with all pairs with $a,b>0$. It's easy to deal with the others using two more functions. $\endgroup$ Commented Aug 15, 2021 at 9:21
  • $\begingroup$ Right - in the school setting there was a "fair" distribution, I wanted this here too and formulated the question in a wrong way. Will correct. $\endgroup$ Commented Aug 15, 2021 at 12:31

1 Answer 1

Reset to default
6
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Beautiful, thank you! $\endgroup$ Commented Aug 15, 2021 at 18:50
  • 1
    $\begingroup$ For a solution which also works for finite classes of size divisible by $4$, partition the class into $4$ equal size blocks, $B_0$, $B_1$, $B_2$, $B_3$. On the first day, do $B_0 \cup B_1$ and $B_2 \cup B_3$, on the second day do $B_0 \cup B_2$ and $B_1 \cup B_3$ and on the third day do $B_0 \cup B_3$ and $B_1 \cup B_2$. (Perhaps name the blocks Gryffindor, Hufflepuff, Ravenclaw and Slytherin :) ) $\endgroup$ Commented Aug 16, 2021 at 16:58

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.