KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 4152. Given n different subsets of the set of numbers 1,2,3,...,n, prove that there exists a number, such that if it is left out of each subset, the remaining subsets will still be different.

(4 points)

Deadline expired on 16 March 2009.


Google Translation (Sorry, the solution is published in Hungarian only.)

Megoldás: Tegyük fel, hogy nem igaz az állítás, vagyis minden 1\lei\len esetén található az adott halmazok között egy Ai és egy Bi halmaz úgy, hogy i\not\in A_i, de Bi=Ai\cup{i}. Tekintsük az adott halmazokat egy gráf csúcsainak, melyben minden i-re az Ai és Bi halmazokat összekötöttünk 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 az adott halmazoknak egy olyan H_1, H_2,\ldots,H_k sorozata, ahol 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 1\lej\len esetén. Ekkor a j szám nem eleme a H1 halmaznak, de eleme H2-nek. Mivel i\ne1 esetén Hi és Hi+1 között már nem az ej él vezet, ebből j\inH3, majd ugyanígy j\in H_4,\ldots,j\in H_k, végül j\inH1 adódik. Ez az ellentmodás bizonyítja, hogy az állítás mégiscsak igaz kellett legyen.


Statistics on problem B. 4152.
55 students sent a solution.
4 points:Á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 points:Énekes Péter, Szabó 124 Zsolt, Tubak Dániel.
2 points:5 students.
1 point:4 students.
0 point:17 students.
Unfair, not evaluated:3 solutions.


  • Problems in Mathematics of KöMaL, February 2009

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley