|
Feladat: |
B.4152 |
Korcsoport: 16-17 |
Nehézségi fok: nehéz |
Megoldó(k): |
Ágoston Tamás , Aujeszky Tamás , Backhausz Tibor , Beke Lilla , Blázsik Zoltán , Bodor Bertalan , Damásdi Gábor , Éles András , Fonyó Dávid , Frankl Nóra , Huszár Kristóf , Kiss Mátyás , Kiss Melinda Flóra , Lovas Lia Izabella , Mészáros András , Nagy Donát , Nagy Miklós , Perjési Gábor , Strenner Péter , Varga László , Vuchetich Bálint , Weisz Ágoston , Weisz Gellért |
Füzet: |
2010/január,
24. oldal |
PDF | MathML |
Témakör(ök): |
Feladat, Részhalmazok, Gráfelmélet |
Hivatkozás(ok): | Feladatok: 2009/február: B.4152 |
|
A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. I. megoldás. Tegyük fel, hogy nem igaz az állítás, vagyis minden esetén található az adott halmazok között egy és egy halmaz úgy, hogy , de . Tekintsük az adott halmazokat egy gráf csúcsainak, amelyben minden -re az és halmazokat összekötöttük egy éllel. Ennek az szögpontú, nyilván egyszerű gráfnak pontosan éle van, tehát található benne egy kör, vagyis adott halmazoknak egy olyan sorozata, ahol , és ‐ az indexekkel modulo számolva ‐ minden -re és között halad egy él. A kör irányítását megfelelően választva feltehetjük, hogy , valamely esetén. Ekkor a szám nem eleme a halmaznak, de eleme -nek. Mivel esetén és között már nem az él vezet, ebből , majd ugyanígy , végül ( miatt) adódik. Ez az ellentmondás az állítás igazát bizonyítja.
II. megoldás. A feladat állításánál általánosabbat látunk be: a halmazok számára vonatkozó teljes indukcióval bizonyítjuk, hogy halmazt már darab alkalmas szám előfordulása alapján is meg tudunk különböztetni, azaz létezik olyan szám, amit mindegyikből elhagyva továbbra is különbözőek maradnak: egy halmaz esetén ez nyilván igaz; ha két halmaz van, és csak egyetlen számban különböznek, akkor elég azt a számot megtartani, ha legalább kettőben, akkor mindegy, hogy melyiket. Ezután feltehetjük, hogy halmazunk van, és minden -re számú halmazra igaz az állítás. Vegyünk egy olyan számot, amely nem fordul elő minden részhalmazban, csak darabban. Ekkor az indukciós feltétel alapján ezt a darab részhalmazt pusztán alkalmas szám előfordulása alapján meg lehet egymástól különböztetni, a maradék darab halmazt pedig darab megfelelő szám előfordulása alapján. Bármely két, különböző csoportban levő halmaz a előfordulásában különbözik egymástól. Összességében tehát elég legfeljebb szám előfordulását nézni (lehetnek ugyanis átfedések is, ami tovább csökkenti ezt a számot). |
|