KöMaL - Mathematical and Physical Journal for Secondary Schools
Hungarian version Information Contest Journal Articles News
Conditions
Entry form to the contest
Problems and solutions
Results of the competition
Problems of the previous years

 

 

Order KöMaL!

tehetseg.hu

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Competitions Portal

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.


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

  • Our web pages are supported by: Ericsson   Google   SzerencsejátĂ©k Zrt.   Emberi ErĹ‘források MinisztĂ©riuma   Emberi ErĹ‘forrás TámogatáskezelĹ‘   OktatáskutatĂł Ă©s FejlesztĹ‘ IntĂ©zet   ELTE   Nemzeti TehetsĂ©g Program