A B. 4152. feladat (2009. február)

B. 4152. Adott az $1, 2, 3, \ldots, 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.

(4 pont)

A beküldési határidő 2009. március 16-án LEJÁRT.

Megoldás: Tegyük fel, hogy nem igaz az állítás, vagyis minden 1 $\le$ i $\le$ n esetén található az adott halmazok között egy A_i és egy B_i halmaz úgy, hogy $i\not\in A_i$ , de B_i=A_i $\cup$ {i}. Tekintsük az adott halmazokat egy gráf csúcsainak, melyben minden i-re az A_i és B_i halmazokat összekötöttünk egy e_i éllel. Ennek az n szögpontú, nyilván egyszerű gráfnak pontosan n éle van, tehát található benne egy kör, vagyis az adott halmazoknak egy olyan $H_1, H_2,\ldots,H_k$ sorozata, ahol az indexekkel modulo k számolva, minden i-re H_i és H_i+1 között halad egy él. A kör irányítását megfelelően választva feltehetjük, hogy H₁=A_j, H₂=B_j valamely 1 $\le$ j $\le$ n esetén. Ekkor a j szám nem eleme a H₁ halmaznak, de eleme H₂-nek. Mivel i $\ne$ 1 esetén H_i és H_i+1 között már nem az e_j él vezet, ebből j $\in$ H₃, majd ugyanígy $j\in H_4,\ldots,j\in H_k$ , végül j $\in$ H₁ adódik. Ez az ellentmodás bizonyítja, hogy az állítás mégiscsak igaz kellett legyen.

Statisztika:

54 dolgozat érkezett.

4 pontot kapott: Á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 902 Melinda Flóra, Kiss 991 Mátyás, Lovas Lia Izabella, Mészáros András, Nagy 111 Miklós, Nagy 648 Donát, Perjési Gábor, Strenner Péter, Varga 171 László, Vuchetich Bálint, Weisz Ágoston, Weisz Gellért.

3 pontot kapott: Énekes Péter, Szabó 124 Zsolt, Tubak Dániel.

2 pontot kapott: 5 versenyző.

1 pontot kapott: 3 versenyző.

0 pontot kapott: 17 versenyző.

Nem versenyszerű: 3 dolgozat.

A KöMaL 2009. februári matematika feladatai

54 dolgozat érkezett.
4 pontot kapott:	Á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 902 Melinda Flóra, Kiss 991 Mátyás, Lovas Lia Izabella, Mészáros András, Nagy 111 Miklós, Nagy 648 Donát, Perjési Gábor, Strenner Péter, Varga 171 László, Vuchetich Bálint, Weisz Ágoston, Weisz Gellért.
3 pontot kapott:	Énekes Péter, Szabó 124 Zsolt, Tubak Dániel.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	17 versenyző.
Nem versenyszerű:	3 dolgozat.

Már regisztráltál?
Új vendég vagy?