Feladat: 1959. évi Kürschák matematikaverseny 3. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Arató Péter ,  Csanak György ,  Halász Gábor ,  Jeltai Árpád ,  Kóta Gábor ,  Muszély György ,  Szász Domokos 
Füzet: 1960/február, 47 - 49. oldal  PDF  |  MathML 
Témakör(ök): Logikai feladatok, Kombinatorikai leszámolási problémák, Kürschák József (korábban Eötvös Loránd)
Hivatkozás(ok):Feladatok: 1960/február: 1959. évi Kürschák matematikaverseny 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 (Kóta Gábor dolgozata nyomán). Tegyük fel, hogy pl. A és A-né nem találkozott a betegágynál. Ekkor A-né vagy elment, mielőtt férje megérkezett és ez esetben korábban távozott a betegágytól mint két sógornője, hiszen ők találkoztak a betegágynál az A-né távozása után érkező A-val, vagy pedig A-né A távozása után érkezett és ekkor későbben érkezett mint két sógornője, hiszen azoknak A távozása előtt kellett a beteghez érkezniük. Csak úgy lehet tehát, hogy egy asszony nem találkozott a férjével, ha vagy előbb távozott, mint a két sógornője, vagy később érkezett náluk.
Azonban három asszony közül legalább az egyik sem nem érkezett a másik kettő után, sem nem távozott azok távozása előtt, így legalább egynek találkoznia kellett a férjével.

 

II. megoldás. Indirekt úton bizonyítjuk a feladat állítását. Tegyük fel, hogy egyik házaspár sem találkozott a betegágynál. Ez esetben, ha pl. A előbb érkezett A-nénél, akkor el is kellett távoznia felesége érkezése előtt. Viszont találkozott B-nével, tehát B-né előbb érkezett mint A-né. B-nek felesége távozása után kellett érkeznie, csak így találkozhatott A-néval anélkül, hogy feleségével találkozott volna. Ha A a felesége után érkezett a betegágyhoz, akkor fenti meggondolásunkban férj és feleség szerepét mindenütt megcserélve szintén azt nyerjük, hogy férj és feleség a B házaspárból fordított sorrendben kellett, hogy a betegágyhoz érkezzék, mint az A házaspárból.
Ugyanezt a meggondolást megismételve egyrészt az A és C házaspárra, másrészt a B és C házaspárra azt kapjuk, hogy C és C-né fordított sorrendben kellett hogy a betegágyhoz érkezzék, mint A és A-né, de ugyancsak fordított sorrendben, mint B és B-né. Ez azonban már lehetetlen, tehát legalább egy házaspárnak találkoznia kellett a betegágynál.
 

Megjegyzés. A most ismertetett meggondolás alkalmas egy általánosabb tétel bizonyítására is. Hogy ezt könnyebben megfogalmazhassuk, előbb átfogalmazzuk az eredeti feladatot.
A három házaspár elhelyezkedhet egy kerek asztal körül pl. A, B-né, C, A-né, B, C-né sorrendben (C-né másik szomszédja A). Ekkor azt mondhatjuk: a hattagú társaság minden tagja meglátogatott (pl. másnap) egy beteg ismerőst. Mindenki csak egyszer járt ezen a napon a betegágynál és mindenki találkozott ott mind a két előző napi asztalszomszédjával. Ez csak úgy történhetett, hogy valaki házastársával (azaz a vele szemben ülővel) is találkozott.
Ez speciális esete a következő általánosabb tételnek: Egy nap n házaspár beszélgetett egy asztal körül, ahol úgy helyezkedtek el, hogy mindenki éppen házastársával szemben ült. Elhatározták, hogy másnap mindegyikük meglátogatja egy közös ismerősüket, aki beteg. A látogatás során úgy adódott, hogy mindenki találkozott a betegágynál két előző napi asztalszomszédjával és ezen a napon mindenki csak egyszer járt a betegnél. Ekkor valamelyik házaspár találkozott a betegágynál.
Tegyük fel az állítással ellentétben, hogy egyik házaspár sem találkozott, noha a többi feltételek teljesültek. Az asztalszomszédok legyenek sorra A1, A2, ... A2n, A1, itt A1 és An+1, A2 és An+2, ..., An és A2n házastársak. Tegyük fel, hogy a betűzést úgy választottuk, hogy A1 előbb érkezett a betegágyhoz, mint házastársa, An+1 (és feltevésünk szerint el is kellett távoznia An+1 érkezése előtt).
Ekkor A2, aki találkozott A1 gyel, előbb kellett, hogy érkezzék, mint An+1. Így An+2, aki találkozott An+1-gyel, de feltevésünk szerint nem találkozott házastársával, A2-vel, csak A2 távozása után érkezhetett. Hasonlóan An+3-nak A3 távozása után kellett érkeznie és így tovább. Így azonban az n-edik lépésben azt kapjuk, hogy az A2n-nel találkozó A1 csak azután érkezhetnék a betegágyhoz, miután An-nel találkozó házastársa, An+1 eltávozott, holott abból indultunk ki, hogy A1 előbb érkezett mint An+1.
Nem lehet tehát, hogy egyik látogató se találkozzék a betegágynál a házastársával.