Kezdőlap


Feladat:	F.2051	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	1976/szeptember, 30. oldal		PDF \| MathML
Témakör(ök):	Fagráfok, erdők, faváz, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok megoldásai: 1977/január: F.2051

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Úthálózatot akarunk építeni $51$ tábor, $T_{1}, T_{2}, ..., T_{51}$ között a következő feltételek mellett:

a) minden út két tábort kössön össze, és közben más tábort nem érinthet;
b) az úthálózat mentén bármely táborból bármely táborba el lehessen jutni, de csak egyféleképpen.

Elő szeretnénk írni azt is, hogy az egyes táborokból hány út induljon ki. Ismeretes, hogy ha az úthálózat eleget tesz az a) és b) feltételeknek, akkor

\begin{matrix} u_{1} + u_{2} + ... + u_{51} = 100, \end{matrix}

(1)

ahol

u_{i}

T_{1}

táborból induló utak száma

(i = 1, 2, ...,51)

. Igaz-e, hogy ha az

u_{1}, u_{2} ..., u_{51}

, pozitív egész számokra teljesül (1), akkor van olyan úthálózat, amelyben

T_{i}

-ből

u_{i}

út indul

(i = 1, 2, ...,51)