Mátrix? Kombinatorika? Valószínűség? Gráfok? Ezek melyikével, avagy valamely más módon oldható meg az alábbi feladat? Nekem valahogy egyik módszerrel sem sikerül.

Egyszerűen azt a legkevesebb csúcsú irányított gráfot kell megrajzolni, amelyikre a fenti állítás igaz lehet. Kétféleképpen lehet irányítani a gráfot; vagy győztes->vesztes, ekkor azt kell megnézni, hogy mindegyik páros tagjaiba mutat él valamelyik pontból, ha pedig vesztes->győztes, akkor azt kell megnézni, hogy mindegyik csúcsba mutat (legalább) két vektor. Érdemesebb az utóbbi jelölést használni, mivel az jobban kezelhetőbb, én az előbbi választottam.

Ha nagyon nincs ötletünk, akkor kezdjünk a legkisebb csúcsú gráftól, és vizsgálódjunk, hogy mi lehet.

A feladat jellegéből adódóan n>=3. A háromcsúcsú gráfnál nem nehéz kitalálni, hogy nem fog teljesülni. A négycsúcsú gráfnál találd ki, hogy mi lehet (csakhogy neked is legyen egy kis munkád a feladattal). Az ötcsúcsú gráfnál könnyű olyat rajzolni, ami megfelel a feltételeknek.

Szerintem adtam elég lökést, hogy be tudd fejezni. Ha mégsem így lenne, kérdezz még, és segítek még.

A tornák egy természetes modellje a digráf, vagy irányított gráf.

A szereplőket (csapatokat) a csúcsok, a meccseket irányított az élek reprezentálják – a győztesből a vesztesbe mutat a nyíl.

A feltétel úgy fog kinézni, hogy olyan teljes, ismeretlen csúcsszámú digráfról van szó, amelyben minden csúcs befoka legalább 2.

A feladat az, hogy keresd meg a legkisebb n számot, amelyre van akkora méretű ilyen típusú teljes digráf.

Mondjuk: adj meg egy ilyen gráfot, és mutasd meg, hogy kisebb gráfra nem teljesülhet.

#1 elárulta, hogy 5-re már van konstrukció, és azt is, hogy n=3-ra a feltétel nem teljesülhet.

n=4-re kell tehát vagy találnod egy ilyen körmérkőzést, vagy megmutatnod hogy n=4 esetén a „hogy bármelyik két csapathoz lehet találni olyan harmadikat, amelyik mindkét előzőt legyőzte” feltétel nem állhat fenn soha.

Kíváncsi lennék az 5-csúcsú megoldásra, akárhogyan rajzolom, nem jön ki.

Fóleg az 1-estől kérdezném.

n<=6-ra ilyen, n=7-re van.

Szerintem n>7-re is van, de ezt nem tudom + nem is kell.

Nagyon egyszerű a megoldás, csak a létező két élfüggetlen Hamilton-kört kell behúzni a gráfba; ha az óramutató járásával megegyezően a csúcsokat A;B;C;D;E betűkkel jelöljük, akkor

az egyik Hamilton-kör: A->B->C->D->E->A

a másik Hamilton-kör: A->C->E->B->D->A

Az él győztes->vesztes felállásban lett irányítva.

Látható, hogy

A;B-t legyőzte E

B;C-t legyőzte A

C;D-t legyőzte B

D;E-t legyőzte C

E;A-t legyőzte D

több páros nincs, így mindegyik párosra jut egy legyőző.

Valóban. Nem volt elég megfontolt a válasz.

Akkor passzolom a kérdést, de csak egy kis időre.