 |
A B. 5227. feladat (2022. február) |
B. 5227. Adjunk példát olyan \(\displaystyle k\) pozitív egészre és legalább \(\displaystyle k\) csúcsú \(\displaystyle F\) véges fagráfra, amelyben minden csúcs legfeljebb harmadfokú, és \(\displaystyle F\)-nek tetszőleges \(\displaystyle k\) csúcsú összefüggő részgráfját elhagyva a megmaradó gráf legalább \(\displaystyle 2022\) komponensre esik szét.
(Monthly feladat nyomán)
(6 pont)
A beküldési határidő 2022. március 10-én LEJÁRT.
Megoldás. Jelöljük minden \(\displaystyle n \geq 2\) egészre \(\displaystyle F_n\)-nel az \(\displaystyle n\) él mélységű teljes bináris fagráfot. (Ennek a gráfnak a csúcsai a \(\displaystyle 0\)-tól \(\displaystyle n\)-ig számozott szinteken helyezkednek el, az \(\displaystyle i.\) szinten \(\displaystyle 2^i\) darab. Az egy szinten levő csúcsok párokba rendeződnek úgy, hogy egy-egy pár tagjait ugyanazzal az eggyel kisebb szintű csúccsal köti össze él. A \(\displaystyle 0.\) szinten levő csúcsot gyökérpontnak nevezzük. Azt mondjuk, hogy az \(\displaystyle i.\) szinten levő \(\displaystyle v\) csúcsnak leszármazottja a \(\displaystyle j.\) szinten levő \(\displaystyle w\) csúcs, ha \(\displaystyle i < j\), és a \(\displaystyle w\)-ből a gyökérbe vezető egyértelmű út áthalad \(\displaystyle v\)-n, ill. az egyszerűség kedvéért minden csúcs saját maga leszármazottja is.)
Az alábbi ábrán az \(\displaystyle F_3\) fagráf látható.
Az \(\displaystyle F_n\) fagráfban minden csúcs fokszáma legfeljebb 3 (hiszen legfeljebb 1 kisebb szintű, és legfeljebb 2 nagyobb szintű csúccsal lehet összekötve). \(\displaystyle F_n\) csúcsainak számát jelöljük \(\displaystyle V_n\)-nel, értelemszerűen
\(\displaystyle V_n = 1 + 2 + 2^2 + \ldots + 2^n = 2^{n+1} - 1. \)
Legyen továbbá
\(\displaystyle S_n = (2^{n-1}-1) + (2^{n-2}-1) + \ldots + (2^1-1) = 2^{n} - n - 1. \)
Bizonyítani fogjuk a következő tételt, amely \(\displaystyle n \geq 2023\) esetén éppen a feladat állítását adja.
Tétel: Ha \(\displaystyle k = V_n- S_n = 2^n + n\) és \(\displaystyle G\) az \(\displaystyle F_n\) egy \(\displaystyle k\)-csúcsú összefüggő részgráfja, akkor az \(\displaystyle F_n\)-ből \(\displaystyle G\) elhagyásával keletkező gráf (ezt nevezzük \(\displaystyle F_n\setminus G\)-nek) biztosan legalább \(\displaystyle n-1\) összefüggőségi komponensből áll.
A tétel bizonyítását három lemmára bontjuk.
1. lemma: \(\displaystyle G\) biztosan tartalmazza a gyökérpontot.
1. lemma bizonyítása: Ha \(\displaystyle F_n\)-ből elhagynánk a gyökérpontot, akkor két \(\displaystyle \frac{V_n-1}2\) méretű komponensre esne szét. Ha \(\displaystyle G\) nem tartalmazná a gyökérpontot, akkor teljes egészében el kellene férnie valamelyik komponensben, de ez lehetetlen, mivel \(\displaystyle k = 2^n + n > 2^n - 1 = \frac{V_n-1}2\). \(\displaystyle \square\)
2. lemma: \(\displaystyle F_n \setminus G\) minden komponensének csúcsszáma \(\displaystyle 2^i-1\), valamilyen \(\displaystyle i \in \{ 1,2,\ldots,n\}\) esetén.
2. lemma bizonyítása: Tekintsük \(\displaystyle F_n \setminus G\) egy tetszőleges komponensét. Ennek csúcsai közt van egy minimális szintű, ezt jelölje \(\displaystyle u\). (Egynél több minimális szintű nem lehet, mivel azonos szintű csúcsok között csak kisebb szintű csúcsokon át vezet út \(\displaystyle F_n\)-ben.) Ekkor \(\displaystyle u\) egyetlen leszármazottja sem lehet \(\displaystyle G\)-ben, hiszen \(\displaystyle u\) elválasztaná a gyökérponttól (amiről beláttuk, hogy \(\displaystyle G\)-ben van). Ha \(\displaystyle u\) az \(\displaystyle (n-j).\) szinten van (itt \(\displaystyle j \in \{0,1,\ldots,n-1\}\)), akkor a leszármazottainak száma éppen \(\displaystyle 2^0 + 2^1 + \ldots + 2^j = 2^{j+1}-1\). \(\displaystyle \square\)
Tegyük fel, hogy \(\displaystyle G\) elhagyása után \(\displaystyle m\) komponens keletkezik. Ezek csúcsszáma a 2. lemma alapján:
\(\displaystyle 2^{a_1}-1, \quad 2^{a_2}-1, \quad \ldots \quad , \quad 2^{a_m}-1,\)
valamilyen \(\displaystyle a_1,\ldots,a_m \in \{0,1,\ldots,n-1\}\) számokra. Mivel \(\displaystyle G\) elhagyása után \(\displaystyle V_n-k = S_n\) csúcs marad meg a gráfból, tudjuk, hogy:
\(\displaystyle (2^{a_1}-1) + (2^{a_2}-1) + \ldots + (2^{a_m}-1) = S_n.\)
3. lemma: Ha valamilyen \(\displaystyle a_1,a_2\ldots,a_m \in \{ 1,2,\ldots,n-1 \}\) számokra teljesül, hogy
\(\displaystyle (2^{a_1}-1) + (2^{a_2}-1) + \ldots + (2^{a_m}-1) = S_n, \)
akkor \(\displaystyle m \geq n-1\).
3. lemma bizonyítása: Ha \(\displaystyle m \leq n-2\) volna, akkor a lemmában szereplő egyenlet mindkét oldalához \(\displaystyle n\)-t adva felírhatnánk, hogy:
\(\displaystyle 2^{a_1} + 2^{a_2}+ \ldots + 2^{a_m} + \underbrace{2^0 + 2^0 + \ldots + 2^0}_{n-m \text{ db}} = S_n + n - 1 = 2^n - 1.\)
Azaz a \(\displaystyle 2^n-1\) számot úgy állítottuk volna elő \(\displaystyle n\) darab kettőhatvány összegeként, hogy \(\displaystyle 2^0\) összeadandóból legalább \(\displaystyle n-m \geq 2\) darab van. Ekkor két darab \(\displaystyle 2^0\) helyett vehetnénk egy \(\displaystyle 2^1\)-t, úgy pedig már kevesebb, mint \(\displaystyle n\) darab kettőhatvány összegeként állna elő \(\displaystyle 2^n-1\), ami lehetetlen.
(Közismert állítás, hogy a \(\displaystyle 2^n-1\) összegként való előállításához legalább \(\displaystyle n\) darab kettőhatvány szükséges, de a teljesség kedvéért vázoljuk a bizonyítást: feltehető, hogy csupa különböző kettőhatvány szerepel az összegben, mert ha lenne duplán valamilyen \(\displaystyle 2^\ell\)-ből, akkor kettejüket lecserélve egyetlen \(\displaystyle 2^{\ell+1}\)-re csak tovább csökkenne a darabszám változatlan összeg mellett. De \(\displaystyle n\)-nél kevesebb darab, különböző, \(\displaystyle 2^n\)-nél kisebb kettőhatvány összege csak kevesebb lehet, mint \(\displaystyle 2^{n-1}+2^{n-2}+\ldots+2+1 = 2^n-1\).) \(\displaystyle \square\)
Ezzel a tételünket is bebizonyítottuk.
Statisztika:
39 dolgozat érkezett. 6 pontot kapott: Bencsik Dávid, Chrobák Gergő, Duchon Márton, Fazokán Marcell, Fülöp Csilla, Kalocsai Zoltán, Kovács Benedek Noel, Lovas Márton, Melján Dávid Gergő, Mohay Lili Veronika, Móricz Benjámin, Nagy 429 Leila, Németh Márton, Nguyen Kim Dorka, Páhán Anita Dalma, Sági Mihály, Somogyi Dalma, Szanyi Attila, Szemlér Bálint, Tóth 057 Bálint, Varga Boldizsár, Wiener Anna. 5 pontot kapott: Bényei Borisz, Dienes Ervin Fotisz, Domján Olivér, Tarján Bernát, Zömbik Barnabás. 4 pontot kapott: 5 versenyző. 3 pontot kapott: 4 versenyző. 2 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző.
A KöMaL 2022. februári matematika feladatai