Matek háziban segítség?

Az első feladatot nem tudom hogy táncoljam körül úgy, hogy ne oldjam meg :D Na lássuk...

Azt állítjuk, hogy AKÁRHOGY választunk ki 4 embert, mindig van egy, aki ismerőse a másik háromnak. És mivel az ismeretség oda-vissza értendő, ezért ha van aki mindenkit ismer a négyesben, akkor azt az egyet is mindenki ismeri, tehát akárhogy választunk, mindig mindenki legalább egy további embert ismer. Tehát akárhogy választunk egy embert, a maradék háromban legfeljebb két olyan ember lesz, akit nem ismer. Ez csak úgy lehetséges, ha az egész közösségben mindenkire igaz, hogy legfeljebb két embert nem ismer. A továbbiakban tekintsünk egy amolyan "Nem ismeretségi gráfot", és azt szűkítve próbáljuk megoldani a feladatot. Mivel MINDENKIRE igaz, hogy max 2 embert nem ismer a teljes közösségből, ezért kizárható az, hogy van pl 2 ember, akit senki nem ismer, és letudva. Így legfeljebb körökként képzelhető el, Ahol így szépen láncolódnak végig a nem-ismeretségek. Kezdetnek tegyük fel, hogy ez a gráf egy nagy kör, tehát egy 2 reguláris gráf.

Most bevezetnék pár jelölést, hogy egyszerűbb legyen a dolgom: AsB jelentse azt, hogy A ismeri B-t, AnB, hogy A nem ismeri B-t, és hasonlóan As{B,C} pl azt jelenti, hogy A ismeri B-t és C-t is.

Ez esetben fel tudunk írni egy olyan négyest, ahol AnB BnC CnD és DnA. Ezesetben AsC / CsA és BsD/DsB teljesül, láthatóan nincs egy tag sem, aki ismerné a másik hármat. Ebből arra következtethetünk, hogy a nem-ismerettségi gráfban nem lehet 4 egybefüggő ember, akik nem ismerik egymást, de ezzel még nem zártuk ki, hogy lehet több darab, kevesebb emberből álló lánc.

Most szűkítsünk egy nagyot, tegyük fel, hogy csak párosával vannak nem-ismerettségek, tehát két-két csúcsok vannak összekötve, egymástól izolálva. tehát pl AnB CnD EnF és így tovább.

Ekkor egy olyan négyest tudunk felírni, hogy AnB és CnD, ebből adódóan As{C,D} Bs{C,D} Cs{A,B} és Ds{A,B}. Láthatóan megint nincs egy elem sem, ami mind a három másikkal kapcsolatban állna. Amíg létezik legalább két ilyen izolált pár az egész közösségben, tehát létezik összesen két-két ember akik nem ismerik egymást, addig felírhatóvá válik egy ilyen négyes. Ebből, és a korábbi megállapításból, hogy egyetlen embernek sincs kettőnél több "nem-ismerőse" az következik, hogy az egész közösségben nemhogy van olyan ember, aki mindenkit ismer, de ÖSSZESEN kevesebb mint 4 olyan ember van, aki nem ismer mindenkit. Be lehet bizonyítani, hogy 3 ilyen ember esetén már teljesül a feltétel, de mivela feladat az volt, hogy igazoljuk, létezik olyan, aki mindenkit ismer, elég eddig mennünk.

Elég részletesen, és méylen fejtettem ki a sztorit, rövidebben is le lehet ezt írni természetesen, ez csak egy megoldás a sok lehetséges közül. Vond le a következtetéseket, és írd át, ahogy neked tetszik. A lényeget elmondtam :D