Az A. 836. feladat (2022. november)

A. 836. Minden \(\displaystyle i \in \mathbb{N}\) esetén legyen \(\displaystyle A_i\), \(\displaystyle B_i\) és \(\displaystyle C_i\) három véges és páronként diszjunkt részhalmaza \(\displaystyle \mathbb{N}\)-nek. Tegyük fel, hogy \(\displaystyle \mathbb{N}\) minden, \(\displaystyle A\), \(\displaystyle B\) és \(\displaystyle C\) halmazokból álló partíciójához létezik \(\displaystyle i \in \mathbb{N}\) úgy, hogy \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) és \(\displaystyle C_i \subset C\). Bizonyítsuk be, hogy ekkor létezik véges \(\displaystyle S \subset \mathbb{N}\) is, melyre \(\displaystyle \mathbb{N}\) minden \(\displaystyle A\), \(\displaystyle B\) és \(\displaystyle C\) halmazokból álló partíciójához létezik \(\displaystyle i \in S\) úgy, hogy \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) és \(\displaystyle C_i \subset C\).

Javasolta: Imolay András (Budapest)

(7 pont)

A beküldési határidő 2022. december 12-én LEJÁRT.

Tegyük fel indirekten, hogy minden \(\displaystyle N\) esetén létezik olyan \(\displaystyle A'_N \cup B'_N \cup C'_N=\mathbb{N}\) partíció, hogy nincs olyan \(\displaystyle i \subset \mathbb{N}\), ahol \(\displaystyle i \leq N\) és \(\displaystyle A_i \subset A'_N\), \(\displaystyle B_i \subset B'_N\) és \(\displaystyle C_i \subset C'_N\). Ezen partíciók segítségével olyan \(\displaystyle A \cup B \cup C=\mathbb{N}\) partíciót konstruálunk, amely ellentmond a probléma feltevéseinek.

Minden \(\displaystyle i \in \mathbb{N}\)-re rekurzívan definiálunk egy végtelen \(\displaystyle S_i \subset \mathbb{N}\) halmazt, és eldöntjük, hogy \(\displaystyle i\)-t az \(\displaystyle A\), \(\displaystyle B\) vagy \(\displaystyle C\) halmazba helyezzük. Legyen \(\displaystyle S_1=\mathbb{N}\). Az indukciós lépésben tegyük fel, hogy \(\displaystyle S_i\)-t már definiáltuk valamilyen \(\displaystyle i \in \mathbb{N}\) esetén. Mivel \(\displaystyle S_i\) végtelen, így a \(\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\}\) halmazok közül legalább az egyik végtelen, mivel ezek a halmazok partícionálják \(\displaystyle S_i\)-t. Válasszuk ki az egyik végtelen halmazt, legyen \(\displaystyle S_{i+1}\) ez a halmaz, és legyen \(\displaystyle i \in A\), ha az első halmazt választottuk, \(\displaystyle i \in B\), ha a másodikat, és \(\displaystyle i \in C\), ha az utolsót. Ezzel meghatároztuk az \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\) partíciót.

Tegyük fel, hogy van egy \(\displaystyle i \in \mathbb{N}\) melyre \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\) és \(\displaystyle C_i \subset C\). Legyen \(\displaystyle N \in \mathbb{N}\) nagyobb, mint az \(\displaystyle A_i \cup B_i \cup C_i\) véges halmaz összes eleme. Legyen \(\displaystyle j \in S_N\) úgy, hogy \(\displaystyle j>i\). Ilyen \(\displaystyle j\) létezik, mivel \(\displaystyle S_N\) végtelen halmaz. Jelölje \(\displaystyle [N]\) az \(\displaystyle \{1,2, \ldots , N-1\}\) halmazt. Az \(\displaystyle A\), \(\displaystyle B\), \(\displaystyle C\) és \(\displaystyle S_N\) halmazok definíciójából tudjuk, hogy \(\displaystyle A \cap [N]=A'_j \cap [N]\), \(\displaystyle B \cap [N]=B'_j \cap [N]\) és \(\displaystyle C \cap [N]=C'_j \cap [N]\). Mivel \(\displaystyle A_i \cup B_i \cup C_i \subset [N]\) és \(\displaystyle A_i \subset A\), \(\displaystyle B_i \subset B\), \(\displaystyle C_i \subset C\), ezért \(\displaystyle A_i \subset A'_j\), \(\displaystyle B_i \subset B'_j\) és \(\displaystyle C_i \subset C'_j\), de ez ellentmond a \(\displaystyle A'_j\), \(\displaystyle B'_j\), \(\displaystyle C'_j\) partíció definíciójának, amivel a bizonyítást befejeztük.

Megjegyzés: Nem nehéz belátni, hogy a feladat ekvivalens azzal a topológiai állítással, hogy a \(\displaystyle \{0,1,2\}^\mathbb{N}\) topológikus tér kompakt.

Statisztika:

7 dolgozat érkezett.
7 pontot kapott:	Németh Márton, Seres-Szabó Márton.
5 pontot kapott:	1 versenyző.
4 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2022. novemberi matematika feladatai