 |
A B. 4016. feladat (2007. szeptember) |
B. 4016. Egy 12 tagú társaságban bármely 9 ember között van 5 olyan, akik valamennyien ismerik egymást. Bizonyítsuk be, hogy létezik a társaságnak 6 olyan tagja is, akik ismerik egymást.
(5 pont)
A beküldési határidő 2007. október 15-én LEJÁRT.
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'
F 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.
Statisztika:
31 dolgozat érkezett. 5 pontot kapott: Tossenberger Anna. 3 pontot kapott: 1 versenyző. 1 pontot kapott: 1 versenyző. 0 pontot kapott: 27 versenyző. Nem versenyszerű: 1 dolgozat.
A KöMaL 2007. szeptemberi matematika feladatai