Problem A. 836. (November 2022)
A. 836. For every \(\displaystyle i \in \mathbb{N}\) let \(\displaystyle A_i\), \(\displaystyle B_i\) and \(\displaystyle C_i\) be three finite and pairwise disjoint subsets of \(\displaystyle \mathbb{N}\). Suppose that for every partition of \(\displaystyle \mathbb{N}\) consisting of sets \(\displaystyle A\), \(\displaystyle B\) and \(\displaystyle C\) there exists \(\displaystyle i\in \mathbb{N}\) such that \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) and \(\displaystyle C_i \subset C\). Prove that there also exists a finite \(\displaystyle S\subset \mathbb{N}\) such that for every partition of \(\displaystyle \mathbb{N}\) consisting of sets \(\displaystyle A\), \(\displaystyle B\) and \(\displaystyle C\) there exists \(\displaystyle i\in S\) such that \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) and \(\displaystyle C_i \subset C\).
Submitted by András Imolay, Budapest
(7 pont)
Deadline expired on December 12, 2022.
Assume by contradiction that for all \(\displaystyle N\) there exists a partition \(\displaystyle A'_N \cup B'_N \cup C'_N=\mathbb{N}\) such that there is no \(\displaystyle i \subset \mathbb{N}\) with \(\displaystyle i \leq N\) and \(\displaystyle A_i \subset A'_N\), \(\displaystyle B_i \subset B'_N\) and \(\displaystyle C_i \subset C'_N\). Using these partitions we construct a partition \(\displaystyle A \cup B \cup C=\mathbb{N}\) which contradicts the assumption of the problem.
For each \(\displaystyle i \in \mathbb{N}\) we recursively define an infinite set \(\displaystyle S_i \subset \mathbb{N}\) and we decide whether we put \(\displaystyle i\) into \(\displaystyle A\), \(\displaystyle B\) or \(\displaystyle C\). Let \(\displaystyle S_1=\mathbb{N}\). Now assume that we have \(\displaystyle S_i\) for some \(\displaystyle i \in \mathbb{N}\). As \(\displaystyle S_i\) is infinite, at least one of the sets \(\displaystyle \{j \in S_i \ : \ i \in A'_j\}\), \(\displaystyle \{j \in S_i \ : \ i \in B'_j\}\), \(\displaystyle \{j \in S_i \ : \ i \in C'_j\}\) are infinite, as these sets partition \(\displaystyle S_i\). Choose one of these sets which is infinite, let \(\displaystyle S_{i+1}\) be this set, and let \(\displaystyle i \in A\) if we chose the first set, \(\displaystyle i \in B\) if chose the second set and \(\displaystyle i \in C\) if we chose the last set. With this we defined the partition \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\).
Assume that there is an \(\displaystyle i \in \mathbb{N}\) with \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) and \(\displaystyle C_i \subset C\). Let \(\displaystyle N \in \mathbb{N}\) be a larger number than all elements of the finite set \(\displaystyle A_i \cup B_i \cup C_i\). Let \(\displaystyle j \in S_N\) such that \(\displaystyle j>i\). Such \(\displaystyle j\) exists, as \(\displaystyle S_N\) is an infinite set. Let \(\displaystyle [N]\) denote the set \(\displaystyle \{1,2, \ldots , N-1\}\). By the definition of \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\) and \(\displaystyle S_N\), we know that \(\displaystyle A \cap [N]=A'_j \cap [N]\), \(\displaystyle B \cap [N]=B'_j \cap [N]\) and \(\displaystyle C \cap [N]=C'_j \cap [N]\). As \(\displaystyle A_i \cup B_i \cup C_i \subset [N]\) and \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\), \(\displaystyle C_i \subset C\), we have \(\displaystyle A_i \subset A'_j\), \(\displaystyle B_i \subset B'_j\) and \(\displaystyle C_i \subset C'_j\), but this contradicts the definition of the partition \(\displaystyle A'_j\), \(\displaystyle B'_j\), \(\displaystyle C'_j\), which finishes the proof.
Remark: It is not hard to see that the problem statement is equivalent with the fact in topology that the topological space \(\displaystyle \{0,1,2\}^\mathbb{N}\) is compact.
Statistics:
7 students sent a solution. 7 points: Németh Márton, Seres-Szabó Márton. 5 points: 1 student. 4 points: 1 student. 2 points: 1 student. 0 point: 2 students.
Problems in Mathematics of KöMaL, November 2022