Van egy verseny feladatom, segítene valaki?

Összesen hány ismeretség van a 24 ember között?

(Hány él van az egyszerű gráfban?)

Számomra egyszerűbb komplementer gráfban gondolkodni, ahol a nem-ismerősök között van él, így ebben minden csúcs fokszáma 20. Ebben keresünk maximális teljes részgráfot.

Ezek után tedd föl, hogy van egy k méretű maximális teljes gráfod. Számold meg az éleket ebben a k részgráfban, a maradék 24-k csúcs között (maximum), és a két rész között.

Ha jól csinálod, k<=12 jön ki, ilyet pedig könnyű konstruálni.

"Milyen versenyre kell ez a megoldás?"

KÖMAL januári? Vagy korábbi?

Van itt valakinek KÖMAL előfizetése, vagyis hozzáférése a januári feladatokhoz?

Akkor segítek, ha tudok.

Az ugye ki tudod számolni, hogy hány kapcsolat lesz a 24 ember között.

Szerintem k=13.

Két dolgot kell belátni:

1. Nem létezhet a feltételeknek megfelelő 24 tagú társaság, amiből van olyan 13 tagú alcsoport, aminek a tagjai között nincs ismeretség. Vagyis k=13 mindig elég. Indirekt bizonyításhoz tippek: ha a 13 tagú társasághoz hozzáadsz 1 embert, akkor mennyivel nő a kapcsolatok száma? És ha a hiányzó 11-et egyesével?

2. k=12 nem elég. Bizonyítási tippek: Legyen egy külső és egy belső kör 12-12 emberből. Csak a körök között vannak ismeretségek. Egy-egy körön belül nincsenek.