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. Érdemes a feladatot általánosan igazolni. Legyen a feladat az, hogy tábor között akarunk úthálózatot építeni. Előírunk pozitív egész számokat úgy, hogy Megmutatjuk, hogy van olyan úthálózat, ami eleget tesz az a) és b) feltételnek, és a táborból út indul ki . A kitűzött feladat az -hez tartozó speciális esete az általános feladatnak. Az állítást -re vonatkozó teljes indukcióval igazoljuk. -re az állítás igaz, mert ekkor csak az számokat írhatjuk elő, és a -et -vel összekötő egyetlen útból álló úthálózat eleget tesz az a) és b) feltételeknek. Tegyük fel, hogy -re igaz az állítás és mutassuk meg, hogy ebből következik, hogy -re is fennáll. Legyenek tetszőleges pozitív egész számok, úgy hogy az összegük legyen. Akkor van közöttük olyan, amelyik , mert ha mindegyik -nél nagyobb, akkor mindegyik legalább , tehát összegük legalább , ami nem lehet. Van köztük olyan is, ami -nél nagyobb, mert ha mindegyik lenne, akkor összegük lenne, ami mellett -nél kisebb. Válasszunk ki egy számot és egy -et. Az , számok közül hagyjuk el -t és helyett írjunk -et. Így pozitív egész számot kapunk, amelyeknek összege . Az indukciós feltevés szerint ezekhez van az a) és b) feltételeknek eleget tevő úthálózat. Adjunk meg egy ilyent és ezt egészítsük ki a táborból a -be vezető egyetlen úttal. Az tábort összekötő, így kapott úthálózat nyilvánvalóan teljesíti azt a feltételt, hogy -ből út indul ki . Eleget tesz az a) feltételnek is, mert egy ennek megfelelő úthálózatot egészítettünk ki egyetlen olyan úttal, amelyik két tábort köt össze és más tábort nem érint. Úthálózatunk eleget tesz a b) feltételnek is, mert bármely két -tól különböző tábort választunk is ki, az egyikből a másikba pontosan egyféleképpen lehetett eljutni, s ezen a -ból -be vezető út felvétele nyilván nem változtat. -ból is pontosan egyféleképpen juthatunk el bármely másik táborba úgy, hogy -ból először -be megyünk és, ‐ ha a másik kiválasztott tábor nem , akkor ‐ -ből a másik táborba vezető egyetlen útvonalon megyünk tovább.
Megjegyzés. Ha a táborokat pontokkal szemléltetjük, az összekötő utakat pedig a pontokat összekötő vonalakkal, akkor egy gráfot kapunk. A feladat a) és b) feltételeinek eleget tevő gráfokat a gráfelméletben fáknak nevezik. Erről a témáról Rényi Alfréd most megjelent "Napló az információelméletről'' című kötetében érdekes cikk található a 164‐185. oldalakon "A fák matematikai elmélete'' címmel. |