Feladat: B.4033 Korcsoport: 16-17 Nehézségi fok: könnyű
Megoldó(k):  Bohus Kinga 
Füzet: 2008/március, 157. oldal  PDF  |  MathML 
Témakör(ök): Logikai feladatok, Indirekt bizonyítási mód, Permutációk, Feladat
Hivatkozás(ok):Feladatok: 2007/november: B.4033

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. Tegyük fel, hogy van olyan táncospár, ahol kettejük magassága között több mint 10 cm a különbség; mondjuk, hogy ilyen az n-edik legmagasabb pár. Amennyiben itt az Fn férfi több mint 10 cm-rel magasabb a Hn hölgynél, akkor Fn felesége magasabb Hn-nél. Mivel azonban az Fn-nél magasabb férfiak (F1,F2,...,Fn-1) is több mint 10 cm-rel haladják meg Hn-et, azért ugyanez az ő feleségükről is elmondható. Tehát legalább n olyan nő van, aki magasabb Hn-nél, így nem lehet ő az n-edik legmagasabb. Ugyanez fordítva elmondható, ha Hn több mint 10 cm-rel lenne magasabb férfi párjánál.

 
II. megoldás. A táncospárok összeállítását hajtsuk végre a következő protokoll szerint. A házaspárokat először hölgy tagjuk magassága szerint sorba állítjuk úgy, hogy a nők a helyiség egyik fala mellett sorakoznak, mindegyikükkel szemben, a terem szemközti fala mentén áll a férje. Utána a férfiak ‐ immár házastársuktól elszakadva ‐ lépésenként rendeződnek sorba: egy-egy adott pillanatban a sorban valahol két, egymás mellett álló férfi helyet cserél, ha magasságuk nagyságviszonya ellentétes a velük szemben álló két hölgy magasságának viszonyával. Ezen a módon, véges sok csere után valóban a kívánt összeállítás jön létre (buborékalgoritmus). Azt mutatjuk meg, hogy a folyamat mindegyik fázisában az egymással éppen szemben álló bármely férfi‐nő pár tagjainak magassága legfeljebb 10 cm-rel tér el egymástól. Kezdetben ez valóban így van; tegyük fel, hogy valamelyik cserénél elromlik. Ez azt jelenti, hogy a csere előtt az A és B magasságú nőkkel szemben az a és b magasságú férfiak álltak, A≥B, a<b, |A-a|≤10, |B-b|≤10, de |A-b|>10 vagy |B-a|>10. Ha például |A-b|>10, akkor A-b>10, vagy b-A>10. Az előbbi esetben A-a>A-b>10, az utóbbiban b-B≥b-A>10, mindkettő ellentmondás, ezért lehetetlen. Ugyanígy jutunk ellentmondásra a |B-a|>10 feltételezésből is.