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 file
Témakör(ök): Feladat, Részhalmazok, Gráfelmélet
Hivatkozás(ok):Feladatok: 2009/február: B.4152

Adott az 1,2,3,...,n számoknak n darab különböző részhalmaza. Bizonyítsuk be, hogy van olyan szám, amelyet minden halmazból elhagyva, a megmaradó halmazok továbbra is különbözőek.

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 1in esetén található az adott halmazok között egy Ai és egy Bi halmaz úgy, hogy iAi, de Bi=Ai{i}. Tekintsük az adott halmazokat egy gráf csúcsainak, amelyben minden i-re az Ai és Bi halmazokat összekötöttük egy ei éllel. Ennek az n szögpontú, nyilván egyszerű gráfnak pontosan n éle van, tehát található benne egy kör, vagyis adott halmazoknak egy olyan H1,H2,...,Hk sorozata, ahol k3, és ‐ az indexekkel modulo k számolva ‐ minden i-re Hi és Hi+1 között halad egy él. A kör irányítását megfelelően választva feltehetjük, hogy H1=Aj, H2=Bj valamely 1jn esetén. Ekkor a j szám nem eleme a H1 halmaznak, de eleme H2-nek. Mivel i1 esetén Hi és Hi+1 között már nem az ej él vezet, ebből jH3, majd ugyanígy jH4,...,jHk, végül (k3 miatt) jH1 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 in halmazt már i-1 darab alkalmas szám előfordulása alapján is meg tudunk különböztetni, azaz létezik n-i+1 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 m3 halmazunk van, és minden i<m-re i számú halmazra igaz az állítás. Vegyünk egy olyan k számot, amely nem fordul elő minden részhalmazban, csak 0<b<m darabban. Ekkor az indukciós feltétel alapján ezt a b darab részhalmazt pusztán b-1 alkalmas szám előfordulása alapján meg lehet egymástól különböztetni, a maradék m-b darab halmazt pedig m-b-1 darab megfelelő szám előfordulása alapján. Bármely két, különböző csoportban levő halmaz a k előfordulásában különbözik egymástól.
Összességében tehát elég legfeljebb
1+(b-1)+(m-b-1)=m-1
szám előfordulását nézni (lehetnek ugyanis átfedések is, ami tovább csökkenti ezt a számot).