Feladat: 1965. évi Arany Dániel matematikaverseny 2. forduló kezdők (speciális) 3. feladata Korcsoport: 16-17 Nehézségi fok: nehéz
Füzet: 1966/február, 53 - 54. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Konstruktív megoldási módszer, Arany Dániel
Hivatkozás(ok):Feladatok: 1966/február: 1965. évi Arany Dániel matematikaverseny 2. forduló kezdők (speciális) 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.

Bár a szöveg ezt nem állítja, feltesszük, hogy volt versenyző.*

 
I. megoldás. Bármelyik feladatot figyelmen kívül hagyva mindegyik versenyzőhöz csak egy olyan másik versenyző van, aki a maradó négy feladatban ugyanazt az eredményt érte el, mint ő. Ha ugyanis volna kettő, akkor hármuk közt vagy volna kettő, aki a figyelmen kívül hagyott feladatot megoldotta, vagy kettő, aki nem oldotta meg, de akkor ők ketten mind az 5 feladat közül ugyanazokat oldották volna meg (esetleg egyet sem), ez pedig a feltétel szerint nem teljesül.
Az 1. feladatot figyelmen kívül hagyva párokba állíthatjuk a versenyzőket úgy, hogy a párok a maradó 4 feladat közül ugyanazokat oldották meg, az 1.-t pedig egyikük megoldotta, másikuk nem. Így a versenyzők száma kétszerese az első feladatot megoldók számának.
Ha most a 2. feladatot hagyva figyelmen kívül alakítunk párokat, akkor egy az első feladatot megoldó versenyző párja is megoldotta az 1. feladatot, hiszen a 2. feladattól eltekintve azonos eredményt értek el; a 2. feladatot viszont egyikük megoldotta, a másikuk nem . Így az 1. feladatot megoldó versenyzők száma 2-szerese, az összes versenyzőké tehát 4-szerese az 1. és 2. feladatot megoldók számának. Hasonlóan a 3. feladat szerint állítva párokba, egy tanulónak, aki az első két feladatot megoldotta, a párja is megoldotta az első két feladatot, a 3. feladatot pedig egyikük oldotta csak meg, így az első két feladatot megoldókat külön állítottuk párokba, számuk kétszer akkora, az összes versenyzőké tehát 8-szor akkora, mint az első három feladatot megoldók száma. Ugyanígy látható, hogy 16-szor annyi versenyző volt, mint ahányan az első négy feladatot megoldották, és 32-szer annyi, mint amennyi mind az 5 feladatot megoldotta. Ilyen versenyző azonban legfeljebb egy volt, és ha feltettük, hogy volt versenyző, akkor egynek kellett is lennie. Így összesen 32 versenyző volt.
 
II. megoldás. Egy feladat megoldását jelöljük 1-gyel, a meg nem oldását 0-val. Minden versenyző eredményét írjuk fel ilyen módon, a feladatok eredményét a kitűzés sorrendjében tüntetve fel, tehát pl. 10110 azt jelöli, hogy a megfelelő versenyző a 2. és 5. kivételével megoldotta a feladatokat. Számoljuk össze a lehetőségek számát. Az első helyen 0 vagy 1 áll, mindegyik mellett állhat a második helyen 0 vagy 1, tehát az első két helyet 4-féleképpen tölthetjük ki. A harmadik helyet ismét 2-féleképpen tölthetjük ki, és minden újabb feladat figyelembevételével megkétszereződik a lehetséges eredmények száma. Így az öt feladat megoldásában 2⋅2⋅2⋅2⋅2=32-féle eredmény lehetséges, ennél több versenyző sem lehetett tehát, mert az első feltétel szerint nem volt két versenyző, aki pontosan ugyanazokat a feladatokat oldotta volna meg.
Megmutatjuk, hogy ha feltesszük, hogy volt versenyző, akkor 32-nek kellett lennie, tehát minden eredménynek elő kellett fordulnia. Válasszunk ki egy versenyzőt, A-t, jelezze az eredményét az abcde jegysorozat (mindegyik betű 0-t vagy 1-et jelent). Aki például az 1. feladatban tőle különböző eredményt ért el, annak az eredménytáblája 1-a-val kezdődik, ezt rövidebben a¯-sal fogjuk jelölni.* Ekkor minden lehetséges eredmény előáll úgy, hogy az a, b, c, d, e számok közül egyeseket (esetleg egyet sem, vagy mindet is) föléhúzunk, hiszen egy betű és a fölülhúzottja közül az egyik 0, a másik 1. Azt kell tehát belátnunk, hogy minden ilyen módon jelzett eredmény elő is fordul. Eljárást adunk meg, amivel minden eredményhez megtalálhatjuk az éppen azt az eredményt elért versenyzőt. Ezt az a¯bc¯d¯e¯ példáján mutatjuk be: A-hoz található olyan B versenyző, akinek az eredménye A-étól csak az 1. feladatban különbözik, tehát B eredménye a¯bcde A B-től csak a 3. feladatban eltérő versenyző, C eredménye a¯bc¯de; az ettől csak a 4. feladatban eltérő D eredménye a¯bc¯d¯e, végül azé az E versenyzőé, akinek az eredménye D-étől csak az 5. feladatban különbözik a¯bc¯d¯e¯. E tehát a keresett versenyző. B, C, D, E a feladat második feltétele szerint rendre létezik. Hasonlóan látható be bármelyik eredményről, hogy előfordul a versenyzők közt, tehát 32 versenyző vett részt a versenyen.
*A feladat szövege szerint megoldás az is, hogy egy versenyző sem indult, hiszen akkor sem volt két olyan versenyző, aki pontosan ugyanazokat a feladatokat oldotta meg, a másik feltétel pedig csak akkor nem teljesül, ha találunk egy versenyzőt és egy feladatot, hogy a feladatot figyelmen kívül hagyva is a versenyző a többi négy feladatban mindenki mástól különböző eredményt ért el. Ha azonban nincs versenyző, akkor ilyen versenyzőt nem találunk.

*Olvasd: á fölül vonás.