Alapfogalmak és a skatulya-elv

Definíció — Halmaz (alapfogalom)

Valami vagy eleme egy halmaznak, vagy nem (annak nincs értelme, hogy hányszor eleme). Egy halmazban nem számít a sorrend. Jelölése: \(\{\}\).

Definíció — Multihalmaz

Egy elem hányszor van benne a halmazban (multiplicitás). Ha \(m\)-szer van benne, akkor \(m\)-szeres elem, vagy az elem multiplicitása \(m\). A multihalmazban nem számít az elemek sorrendje. Jelölése: \(\{\{\dots\}\}\).

Definíció — Rendezett n-es

Olyan elemösszesség, ahol:

• számít az elemek sorrendje (ezt kerek zárójellel jelöljük: \((\dots)\));
• \(n\) elemet tartalmaz;
• egy elem szerepelhet többször is.

Definíció — Függvény

Legyenek \(A, B \neq \emptyset\) halmazok. Ekkor az \(f: A \to B\) függvény esetén minden \(a \in A\) elemnek pontosan egy \(f(a) \in B\) képe van.

Definíció — Injektív, szürjektív, bijektív

Legyenek \(A \neq \emptyset\) és \(B \neq \emptyset\) halmazok, valamint \(f: A \to B\) egy függvény.

• \(f\) injektív, ha különböző \(A\)-beli elemek képe különböző: \(a_1 \neq a_2 \implies f(a_1) \neq f(a_2)\)
• \(f\) szürjektív, ha minden \(B\)-beli elem előáll valamely \(A\)-beli elem képeként: \(\forall b \in B, \exists a \in A : f(a) = b\)
• \(f\) bijektív, ha egyszerre injektív és szürjektív (kölcsönösen egyértelmű ráképezés).

Állítás

Ha \(A \neq \emptyset\) és \(B \neq \emptyset\) véges halmazok, és létezik közöttük egy \(f: A \to B\) bijektív függvény, akkor \(|A| = |B|\).

Definíció — Reláció

Legyen \(A \neq \emptyset\) halmaz. Ezen egy reláció az elemek közötti kapcsolatot írja le, amely bármely elempár esetén vagy fennáll, vagy nem áll fenn.

Emlékeztető — Relációk alaptulajdonságai

Legyen \(R\) egy reláció az \(A \neq \emptyset\) halmazon:

• Reflexív: \(\forall a \in A : aRa\). (Pl.: \(=, \ge, \mid, \cong\); de a \(<\) nem az.)
• Szimmetrikus: \(aRb \implies bRa\). (Pl.: \(=, \cong\); de a \(<, \ge, \mid\) nem az.)
• Tranzitív: \(aRb \land bRc \implies aRc\). (Pl.: \(=, <, \ge, \mid, \cong\).)

Definíció — Ekvivalenciareláció

Az \(R\) reláció ekvivalenciareláció, ha egyszerre reflexív, szimmetrikus és tranzitív.

Állítás

Ha \(A \neq \emptyset\) és \(R\) egy ekvivalenciareláció \(A\)-n, akkor \(R\) egy osztályozást hoz létre \(A\)-n.

Definíció — Osztályozás / Partíció

Nemüres részhalmazok rendszere, melyek páronként diszjunktak, és uniójuk az \(A\) halmaz. (Másképpen: nemüres részhalmazok rendszere úgy, hogy \(A\) minden eleme pontosan egy részhalmazba tartozik.)

Tétel — Skatulya-elv (Pigeonhole Principle)

Legyen \(n, k \in \mathbb{N}\). Ha \(n\) db halmaz uniójának elemszáma \(\ge k \cdot n + 1\), akkor valamelyik halmaz elemszáma \(\ge k + 1\).

Bizonyítás — indirekt

Tegyük fel, hogy mindegyik halmaz elemszáma \(\le k\). Ekkor az \(n\) db halmaz uniójának elemszáma legfeljebb \(n \cdot k\) lehetne, ami ellentmond annak, hogy az unió elemszáma \(\ge k \cdot n + 1\).

Állítás

Legyen \(n \in \mathbb{N}\). Bárhogyan választunk ki \(n+1\) db számot az \(1, 2, \dots, 2n\) számok közül, biztosan lesz köztük két olyan, melyek lnko-ja 1 (azaz relatív prímek).

Bizonyítás

Készítsünk \(n\) db skatulyát az egymást követő párokból:

\[ \{1, 2\}, \{3, 4\}, \dots, \{2n-1, 2n\} \quad (n \text{ db skatulya}) \]

A kiválasztott elemek száma \(n+1\). A skatulya-elv szerint valamelyik skatulyából 2 elemet választottunk ki. Ezek szomszédos egész számok (\(m\) és \(m+1\)). Ha \(d\) közös osztójuk:

\[ \left. \begin{aligned} d \mid m \\ d \mid m+1 \end{aligned} \right\} \implies d \mid (m+1) - m \implies d \mid 1 \implies d = 1. \]

Tehát a két kiválasztott szám valóban relatív prím.

Állítás

Legyen \(n \in \mathbb{N}\). Bárhogyan választunk ki \(n+1\) db számot az \(1, 2, \dots, 2n\) számok közül, biztosan lesz köztük két olyan, hogy a kisebbik osztója a nagyobbnak.

Bizonyítás

Minden pozitív egész szám egyértelműen felírható \(2^l \cdot m\) alakban, ahol \(l \in \mathbb{N} \cup \{0\}\) és \(m\) pozitív páratlan szám. Például: \(12 = 2^2 \cdot 3\), \(16 = 2^4 \cdot 1\), \(19 = 2^0 \cdot 19\).

Az \(1, 2, \dots, 2n\) számok esetén a páratlan rész (\(m\)) csak az \(1, 3, \dots, 2n-1\) számok egyike lehet. Ez összesen \(n\) féle páratlan szám. Alkossunk \(n\) db skatulyát a páratlan rész szerint — pl. \(n = 10\) esetén a skatulyák: az 1-es páratlan részhez \(1, 2, 4, 8, 16\) tartozik, a 3-ashoz \(3, 6, 12\), az 5-öshöz \(5, 10, 20\), a 7-eshez \(7, 14\), a 9-eshez \(9, 18\), a \(11, 13, 15, 17, 19\) páratlan részekhez pedig önmaguk.

Mivel \(n\) db skatulyánk van és \(n+1\) db számot választunk ki, a skatulya-elv miatt van olyan skatulya, amiből legalább 2-t választottunk. Ezek azonos \(m\) páratlan résszel rendelkeznek: \(x = 2^{l_1} \cdot m\) és \(y = 2^{l_2} \cdot m\). Ha \(l_1 < l_2\), akkor \(x \mid y\), azaz a kisebbik osztója a nagyobbnak.

Állítás

Bárhogyan színezzük ki a sík pontjait két színnel, biztosan lesz két azonos színű pont, melyek távolsága éppen 1.

Bizonyítás

Vegyünk egy 1 oldalú szabályos háromszöget. Ennek 3 csúcsa van, és 2 szín áll rendelkezésre. A skatulya-elv szerint a 3 csúcs között van 2 azonos színű. Mivel a háromszög minden oldala 1 egységnyi, ezért a két azonos színű csúcs távolsága pontosan 1.

Megjegyzés — Hadwiger–Nelson-probléma

• Ha a színek száma 3 vagy 4, az állítás továbbra is igaz marad (pl. 3 színnél a Moser-orsó konstrukcióval bizonyítható).
• Ha a színek száma 7 vagy több, akkor az állítás nem igaz (létezik jó színezés).
• 5 vagy 6 szín esetén a kérdés még nyitott!