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. I. megoldás. A kívánt tárgyat kiválaszthatjuk a következő módon: Válasszunk ki tanulót és egy tárgyat, amelyikből különböző jegyet kaptak. A feladat feltétele szerint ilyen tárgy van. Ezután egyenként veszünk hozzájuk a többi tanulókból, és választunk ki egy-egy tantárgyat. Ha kiválasztottunk már tanulót (, , , vagy ) és tárgyat úgy, hogy a tanuló közül bármely kettőnek a tárgy valamelyikéből különböző osztályzata van, akkor egy -edik tanulónak, mondjuk -nek, ebből a tárgyból legfeljebb a tanuló egyikével egyezhetnek meg az érdemjegyei. Ha van ilyen tanuló, akkor feltétel szerint van olyan tárgy, amelyikből -nak és -nek különböző osztályzata van, kiválasztunk egyet. Ha ilyen tanuló nincs, akkor újabb tárgy kiválasztására nincs is szükség, de hozzávehetünk tetszés szerint egyet a már kiválasztottakhoz és kaptunk a tanulóhoz tárgyat a kívánt tulajdonsággal. -ig haladva a tanulóhoz tárgyat választunk így ki a feladat állításának megfelelően.
II. megoldás. Vegyünk egy tárgyat. Ha ezt elhagyva a többi közül is található bármely két tanulóhoz olyan, amelyikből a két tanuló osztályzata különböző, akkor a kivett tárgyat hagyjuk el. Ezt ismételjük a maradó tárgyakkal, amíg lehet. Megmutatjuk, hogy legfeljebb tárgyat kell megtartanunk. Az hogy egy tárgy sem hagyható el, azt jelenti, hogy még egy tárgyat figyelmen kívül hagyva van olyan pár a diákok közt, akiknek a bizonyítványa a többi megtartott tárgyban megegyezik. Jelöljük a tanulókat egy-egy ponttal, a tárgyakhoz pedig válasszunk egy-egy színt. Egy-egy tárgy színével kössük össze azokat a diákpárokat ábrázoló pontpárokat, akiknek a bizonyítványa egyedül ennek a tárgynak az osztályzatában különbözik. Ekkor mindegyik tárgy színével össze van kötve legalább egy pontpár, egy pontpár viszont legfeljebb egy színnel van összekötve. Megmutatjuk, hogy ha egy pontból elindulunk, és színes vonal mentén haladva ponttól pontig, visszaérünk a kiinduló pontba, és valamilyen színű összekötésen áthaladunk, akkor legalább még egyszer kellett ilyen színű összekötésen haladnunk. Így ha minden színű összekötésből csak egyet tartunk meg, akkor a maradó vonalrendszerben már egyik pontból sem juthatunk vissza ugyanoda a megmaradt vonalak mentén haladva, hacsaknem ugyanazokon a vonalakon megyünk oda és vissza. Megmutatjuk másrészt, hogy ha az utolsó tulajdonság teljesül, akkor kevesebb pontpár van összekötve, mint ahány pont van. Ezzel a feladat állítása bizonyítást nyer, mert a megtartott összekötő vonalak száma megegyezik a használt színek, vagyis a megtartott tantárgyak számával, és ez az utolsó állítás szerint kevesebb a pontok, vagyis a tanulók számánál, -nél, tehát legfeljebb . (Ha annál kevesebb, akkor tetszés szerinti tárgyak hozzávételével kiegészíthetjük a számukat -ra, ez nem változtat azon, hogy bármely két tanuló bizonyítványa különböző.) Tegyük fel, hogy az tanulót ábrázoló pontból az -t, -at, s i. t., -t ábrázoló pontokon keresztül visszajutunk -be színes vonalak mentén haladva, és közben az -et -vel összekötő színű ‐ mondjuk történelmet jelölő ‐ vonalon többször nem kellett áthaladnunk. Ekkor és érdemjegye történelemből különbözik. bizonyítványa -étól csak egy tárgy érdemjegyében különbözik, mert össze vannak kötve színes vonallal, és ez a tárgy nem a történelem, így történelemből jegye megegyezik -ével; hasonlóan -é (ha ) és a többi számba vett tanulóé egészen -ig történelem érdemjegyével egyezik meg. Ezen kívül még és érdemjegyének is egyeznie kellene történelemből, ez azonban nem lehetséges, mert érdemjegye -ével egyezik, és az különbözik -étől. A következőt kell még bizonyítanunk: ha egy pontokból (legalább -ből) és bizonyos pontpárokat összekötő vonalakból álló ábrán (megengedjük azt is, hogy egy pontpár se legyen összekötve) semelyik pontból indulva sem lehet ugyanoda visszajutni, hacsak nem ugyanazon az úton megyünk oda és vissza, akkor kevesebb pontpár van összekötve, mint a pontok száma. Ezt az összekötött pontpárok számára vonatkozó teljes indukcióval bizonyítjuk. Ha egy pontpár sincs összekötve, akkor az állítás nyilvánvalóan helyes. Legyen most egy a feltételeknek megfelelő ábránk, amiben van összekötött pontpár, és tegyük fel, hogy igaz az állítás minden olyan ábrára, amiben kevesebb pontpár van összekötve. Válasszunk ki egy összekötött pontpárt. Ha ezt az összekötést elhagyjuk, a maradó ábrán nem lehet eljutni -ból -be, hiszen különben az eredeti ábrán visszajuthatnánk -ból -ba úgy, hogy a összekötésen csak egyszer haladunk át. Így azok a pontok a köztük levő összekötésekkel együtt, amelyekbe -ból érintése nélkül, illetőleg amelyekbe -ből érintése nélkül el lehet jutni, továbbá azok, amelyekbe sem -ból, sem -ből nem lehet eljutni (ha vannak ilyenek), egy-egy a feltételnek megfelelő ábrát alkotnak (az előbbi kettő állhat esetleg egyedül az , ill. a pontból), és nincs közös pontjuk. Ezek mindegyikében kevesebb összekötés van, mint az eredeti ábrában, hiszen az összekötés egyikben sem szerepel. Így feltevésünk szerint mindegyik részben kevesebb pontpár van összekötve, mint a pontok száma, tehát az egész ábrában ‐ az összekötéstől eltekintve ‐ legalább -vel kevesebb, mint a pontok száma. Hozzávéve ezekhez az összekötést, még mindig kevesebb az összekötések száma, mint a pontoké. Ezzel az indukción bizonyítást befejeztük, s így a feladat állítása is bizonyítást nyert.
Megjegyzés. Mind a két megoldás általánosan azt adta, hogy ha tanuló közül bármelyik kettő bizonyítványa különböző, akkor kiválasztható legfeljebb tantárgy úgy, hogy csak az ezekből kapott érdemjegyeket nézve is bármelyik két tanuló bizonyítványa különbözik.
|