Feladat: 1965. évi Matematika OKTV II. forduló 3. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1965/november, 110 - 112. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Teljes indukció módszere, OKTV
Hivatkozás(ok):Feladatok: 1965/november: 1965. évi Matematika OKTV II. forduló 3. feladata

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 6 tárgyat kiválaszthatjuk a következő módon: Válasszunk ki 2 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 k tanulót (k=2, 3, 4, 5 vagy 6) és k-1 tárgyat úgy, hogy a k tanuló közül bármely kettőnek a k-1 tárgy valamelyikéből különböző osztályzata van, akkor egy k+1-edik tanulónak, mondjuk N-nek, ebből a k-1 tárgyból legfeljebb a k tanuló egyikével egyezhetnek meg az érdemjegyei. Ha van ilyen A tanuló, akkor feltétel szerint van olyan tárgy, amelyikből A-nak és N-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 k+1 tanulóhoz k tárgyat a kívánt tulajdonsággal. k=6-ig haladva a 7 tanulóhoz 6 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 6 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, 7-nél, tehát legfeljebb 6. (Ha annál kevesebb, akkor tetszés szerinti tárgyak hozzávételével kiegészíthetjük a számukat 6-ra, ez nem változtat azon, hogy bármely két tanuló bizonyítványa különböző.)
Tegyük fel, hogy az A1 tanulót ábrázoló pontból az A2-t, A3-at, s i. t., Ak-t ábrázoló pontokon keresztül visszajutunk A1-be színes vonalak mentén haladva, és közben az A1-et A2-vel összekötő színű ‐ mondjuk történelmet jelölő ‐ vonalon többször nem kellett áthaladnunk. Ekkor A1 és A2 érdemjegye történelemből különbözik. A2 bizonyítványa A3-é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 A3 jegye megegyezik A2-ével; hasonlóan A4-é (ha k>3) és a többi számba vett tanulóé egészen Ak-ig A2 történelem érdemjegyével egyezik meg. Ezen kívül még Ak és A1 érdemjegyének is egyeznie kellene történelemből, ez azonban nem lehetséges, mert Ak érdemjegye A2-ével egyezik, és az különbözik A1-étől.
A következőt kell még bizonyítanunk: ha egy pontokból (legalább 1-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 AB összekötött pontpárt. Ha ezt az összekötést elhagyjuk, a maradó ábrán nem lehet eljutni A-ból B-be, hiszen különben az eredeti ábrán visszajuthatnánk A-ból A-ba úgy, hogy a BA összekötésen csak egyszer haladunk át. Így azok a pontok a köztük levő összekötésekkel együtt, amelyekbe A-ból B érintése nélkül, illetőleg amelyekbe B-ből A érintése nélkül el lehet jutni, továbbá azok, amelyekbe sem A-ból, sem B-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 A, ill. a B pontból), és nincs közös pontjuk. Ezek mindegyikében kevesebb összekötés van, mint az eredeti ábrában, hiszen az AB ö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 AB összekötéstől eltekintve ‐ legalább 2-vel kevesebb, mint a pontok száma. Hozzávéve ezekhez az AB ö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 k tanuló közül bármelyik kettő bizonyítványa különböző, akkor kiválasztható legfeljebb k-1 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.