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

apehman

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

B. 4016. In every group of 9 out of a company of 12 people, there are 5 people who pairwise know each other. Prove that there are 6 members of the company who pairwise know each other, too.

(5 points)

Deadline expired on 15 October 2007.


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

Megoldás: Tekintsünk egy G gráfot, melynek csúcsai a társaság tagjai, két csúcs pedig akkor van összekötve, ha a nekik megfelelő tagok nem ismerik egymást. A feltétel szerint bármely 9 csúcs között van 5 független (vagyis 5 olyan csúcs, hogy semelyik kettő között nem megy él), és azt kell igazolnunk, hogy található a gráfban 6 elemű független ponthalmaz is. Ha van G-nek olyan v csúcsa, amelynek legfeljebb 2 szomszédja van, akkor tekintsünk egy olyan 9 elemű ponthalmazt, amely sem v-t, sem annak szomszédait nem tartalmazza. Ebben található 5 független pont, melyekhez v-t hozzávéve 6 elemű független halmazt kapunk.

Feltehetjük tehát, hogy G-ben minden csúcs foka legalább 3. Ha G-ben nincs páratlan kör, akkor G páros gráf, melyben valamelyik osztálynak legalább 6 pontja van, azok pedig függetlenek. Feltehetjük tehát még azt is, hogy G-ben van páratlan kör, a legrövidebb ilyen kör pontjainak száma legyen m, Cm pedig legyen egy m hosszú kör. Ha m>3 és v nem pontja a körnek, akkor Cm-nek legfeljebb két másodszomszédos csúcsával lehet összekötve, máskülönben keletkezne a gráfban m-nél rövidebb páratlan hosszú kör. Valóban, ha p és q két nem másodszomszédos csúcsa Cm-nek, és mindkettő v-vel össze van kötve, akkor Cm mentén valamelyik irányban p-t q-val egy (m-2)-nél kevesebb élből álló páratlan hosszú út köti össze, melyet a pv és qv élekkel kiegészítve m-nél rövidebb páratlan kört kapunk.

Az előzőek alapján m=11 nem lehetséges, mert az egyetlen kimaradó pont Cm-nek legalább 3 pontjával össze lenne kötve. 9 hosszú kör nem lehet a gráfban, mert abból nem tudunk 5 független pontot kiválasztani. Ha m=7 és a maradék 5 pont között nem megy él, akkor ezek mindegyike C7-nek legalább 3 pontjával össze van kötve, ami ellentmondás. Ha pedig az 5 pont között találnánk egy E élet, akkor C7 és E csúcsai összesen 9 pontot adnának. Ha F egy független halmaz ezen a 9 ponton, akkor E-ből legfeljebb 1, C7-ből pedig legfeljebb 3 pontot tartalmazhat, ami ellentmond a feladat feltételének. Tehát m=5, vagy m=3.

Ha m=5 és a maradék 7 pont független, akkor készen vagyunk. Ha közülük kettő össze van kötve egy E éllel, akkor tekintsük a maradék 5 pontot. Ezeken nem találhatunk egy E' élet, mert akkor C5, E és E' 9 csúcsán csak 4 elemű független halmaz lehetne. A maradék 5 pont tehát egy 5 elemű F független ponthalmazt alkot. Ha E mindkét végpontjából vezetne él F-be, akkor vagy kapnánk egy háromszöget (ha ugyanabba a csúcsba vezettek), ami ellentmond az m=5 feltevésnek, vagy keletkezne C5 csúcsain kívül egy 3 élből álló P út, de akkor C5 és P összesen 9 csúcsából megintcsak legfeljebb 4 elemű független halmazt tudnánk kiválasztani. Az E él valamelyik végpontjából tehát nem vezet él F-be. Ezt a pontot F-hez hozzávéve 6 elemű független halmazt kapunk.

Tegyük fel végül, hogy m=3. Ha van 7 elemű független halmaz, akkor készen vagyunk, ha nincs, akkor találunk egy E és egy E' élet is úgy, hogy C3-nak, E-nek és E'-nek nincs közös csúcsa. Ha ezt még egy E'' éllel ki tudnánk egészíteni, akkor az így kapott 9 ponton nem találnánk 5 függetlent, tehát a maradék 5 pont egy F független halmazt alkot. Ha E-nek, vagy E'-nek valamelyik csúcsa nincs F-fel összekötve, akkor azt F-hez hozzávéve már megkapjuk a keresett 6 független pontot. Más eset viszont nem lehetséges, mert ha az m=5 esethez hasonló módon E és E' közül valamelyiket, mondjuk E'-t, két F-beli ponttal egy 3 élből álló P úttá ki tudnánk egészíteni, akkor Cm, E és P csúcsai olyan 9 elemű halmazt alkotnának, amelyben nincs 5 elemű független részhalmaz. Ha pedig E-t és E'-t is egy-egy Ev, E'v' háromszöggé tudnánk csak kiegészíteni alkalmas v,v'\inF nem feltétlenül különböző pontokkal, akkor a C3, Ev, E'v' háromszögeknek együttesen legalább 8 pontja lenne, melyek között nincs 3-nál több független. A v=v' esetben ezt még egy tetszőleges ponttal kiegészítve már 9 olyan pontot kapnánk, melyek között nem lenne 5 független.


Statistics on problem B. 4016.
31 students sent a solution.
5 points:Tossenberger Anna.
3 points:1 student.
1 point:1 student.
0 point:27 students.
Unfair, not evaluated:1 solution.


  • Problems in Mathematics of KöMaL, September 2007

  • Támogatóink:   Ericsson   Google   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