Kezdőlap


Cím:	Ló és lovasa, avagy a párbaállítás módszere
Szerző(k):	Róka Sándor
Füzet:	1996/január, 1 - 3. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

,,Néha számlálás nélkül is meg tudjuk állapítani, hogy két véges halmaznak ugyanannyi eleme van-e. Pl. egy olyan gyerek, aki csak 20-ig tud számlálni, meg tudja állapítani, hogy az ablak alatt ugyanannyi katona haladt el, mint ahány ló, ha látja, hogy egy katona sem ment gyalog, és egy ló sem ment anélkül, hogy katona ne ülne a hátán (és természetesen egy lovon sem ült egynél több katona, és egy katona sem ült egynél több lovon), akkor is, ha a katonák, ill. lovak száma több, mint 20.''¹
A megszámlálásnak azt a módját, amikor a lovakat kell megszámolni, és tudom, hogy ugyanannyi lovas van, mint ahány ló, s ezért a lovasokat számolom meg, jól mutatja Halmos Pál következő példája.²

1. feladat. Tekintsünk egy

1025

teniszjátékosból álló társaságot. Képzeljük el, hogy a társaság bajnokságot szervez a következő rendszer szerint. A játékosokat párokba sorolják, egy embernek természetesen nem jut pár. Az egyes párok mérkőznek, a vesztesek kiesnek. A második fordulóban a győztesek vehetnek részt, és az első fordulóban pár nélkül maradt játékos. A második forduló párosítását ugyanúgy készítjük el, mint az elsőét, ismét kisorsolnak egy játékost, aki ebből a fordulóból játék nélkül jut tovább. Ezt azután így folytatjuk, amíg mindenki ki nem esik, az utolsó mérkőzés győztese lesz a bajnok. A bajnok tehát nem vert meg mindenkit, de minden játékos kikapott valakitől,

...

, aki kikapott a bajnoktól. A kérdés: összesen hány mérkőzésre került sor?

A megoldást sok úton kereshetjük, és már a lehető legprimitívebb meggondolás is célhoz vezet. Az első fordulóban 512 mérkőzést játszottak, a másodikban 256-ot, majd 128, 64, 32, 16, 8, 4, 2, 1, 1 mérkőzést. Ezeket összeadva gyorsan megvan az eredmény: 1024.
Van olyan megoldás is, amelyhez nincs szükség számolásra, kísérletekre, sőt még számokra sem, csak puszta gondolkodásra. A gondolatmenet: minden mérkőzésnek egy győztese és egy vesztese van. A vesztes nem vehet részt a további fordulókban. Minden játékos, a bajnok kivételével, pontosan egyszer veszít. Így ugyanannyi mérkőzés van, ahány vesztes, azaz a mérkőzések száma eggyel kisebb a játékosokénál. Ha a játékosok száma 1025, a megoldás 1024, ha 1000, akkor 999. Nyilvánvaló, hogy ez az egyszerű gondolatmenet a játékosok számától függetlenül, teljes általánosságban szolgálja a feladat megoldását.
Ahogyan Halmos hozzáfűzi: ,,itt csillan fel egy piciny darabja az igazi matematikának''.
1966-ban a TV ,,Ki miben tudós?'' versenyének döntőjében szerepelt a következő feladat:

2. feladat. Egy

n

oldalú konvex sokszög belsejében nincs olyan pont, amelyen a sokszög kettőnél több átlója halad át. Hány metszéspontja van a sokszög átlóinak a sokszög belsejében?

A megoldás dallama hasonló az előbbihez. A sokszög bármely négy csúcsa egy konvex négyszöget határoz meg, a négyszög átlóinak metszéspontja pedig megad egy metszéspontot a keresettek közül. Egy metszéspont és négy csúcs ily módon történő párbaállítása kölcsönösen egyértelmű: annyi metszéspont van, ahányféle módon ki tudunk választani 4-et az

n

csúcs közül, azaz

(\binom{n}{4})

3. feladat. Mutassuk meg, hogy egy

n

elemű halmaz részhalmazainak száma

2^{n}

Az állítás igazolható teljes indukcióval, vagy úgy is, hogy felhasználjuk az

\begin{matrix} (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + ... + (\binom{n}{n}) = 2^{n} \end{matrix}

összefüggést. Elegáns útja a bizonyításnak a következő: ha az

n

-elemű halmaz

{a_{1}, a_{2}, ..., a_{n}}

, úgy ennek egy részhalmazát egyértelműen kijelöli egy

n

hosszúságú 0‐1 sorozat. Ha a sorozatban a

k

-dik helyen

1

-es áll, akkor

a_{k}

eleme a részhalmaznak, ha pedig

0

áll a

k

-adik helyen, akkor nem. Így a részhalmazok száma ugyanannyi, mint az

n

hosszú 0‐1 sorozatok száma:

2^{n}

4. feladat. Mutassuk meg, hogy az

1

2

...

10^{k}

számokban előforduló számjegyek száma egyenlő az

1

2

...

10^{k + 1}

számokban levő

0

-k számával.

Az első sorozatból tetszőleges számot választva, annak valamely számjegye után beszúrunk egy nullát. Ez a megfeleltetés kölcsönösen egyértelmű az első sorozatbeli számok számjegyei és a második sorozatbeli számok

0

számjegyei között.

Ha látjuk, hogy mindegyik lovon egy huszár ül, és néhány huszár gyalog sétál, akkor nyilván a huszárok száma nagyobb a lovak számánál. Egyenlőtlenséget is tudunk a párbaállítás módszerével igazolni.
Lássuk a következő feladatot!

5. feladat. Jelölje

T_{n}

egy

n

elemű halmaz különböző partícióinak (diszjunkt osztályokra bontásainak) számát. Bizonyítsuk be, hogy fennáll a

T_{n} \leq n!

egyenlőtlenség.

Legyen az

n

-elemű halmaz

{1, 2, 3, ..., n}

. Tekintsük a halmaz egy partícióját, és minden részhalmazban az elemeket rendezzük nagyság szerint csökkenő sorrendbe, majd ezeket a sorozatokat első elemük szerint növekedve írjuk egymás után. Például, ha

n = 6

és az egyik partíció

{1, 5}

{2, 3}

{4, 6}

, úgy ehhez a

3 2 5 1 6 4

sorozat tartozik. Ily módon megadhatjuk az

n

elem egy permutációját, különböző partíciókhoz különböző permutációkat. Vagy olyan permutáció is, amelyhez nem tartozik partíció, pl.:

3 2 6 4 5 1

. (Gondoljuk meg, miért?)
Megjegyzés. Az

n

-elemű halmaz partícióinak számát a

T_{n}

Bell-féle szám jelöli.

6. feladat. Az

1 < a_{1} < a_{2} < ... < a_{k} \leq n

természetes számokra igaz, hogy egyik

a_{i}

sem osztója a többi szorzatának. Mutassuk meg, hogy

k \leq π (n)

, ahol

π (n)

a prímszámok száma

n

-ig.

Azt kell észrevenni, hogy minden

a_{i}

-hez tudunk olyan

p_{j}

prímet rendelni, amelyre

p_{j}^{α_{j}} ∣ a_{i}

, de

p_{j}^{α_{j}} ∤ a_{1} \cdot a_{2} \cdot ... \cdot a_{i - 1} \cdot a_{i + i} \cdot ... \cdot a_{k}

. Különböző

a_{i}

-khez különböző

p_{j}

-k tartoznak.

,,Az olyan ötlet, amely csak egyszer használható, csak trükk. Ha többször is fel lehet használni, módszer lesz belőle'' (Pólya György). A párbaállítás olyan ötlet, amelyet többször is fel lehet használni. Gyakorlásul álljon itt néhány feladat, amelyek megoldásánál lehet alkalmazni a párbaállítás módszerét.

1. Hány részre osztják a teret a kocka lapsíkjai?

2. Szabályos tetraéder minden élén át síkot fektetünk, amely két egybevágó részre osztja a tetraédert. Így hány részre bontottuk fel a tetraédert?

3. Egy

6 \times 10

-es négyzetrácsos papírt a berajzolt rácsegyenesek mentén két részre vágunk, majd az egyik darabot ismét csak rácsegyenesek mentén két részre vágjuk és így tovább: minden alkalommal valamelyik darabot két részre vágjuk. Hányszor vágunk, mire a papirost

1 \times 1

-es négyzetekre szabdaljuk? A vagdosást többféleképpen is végezhetjük. Vajon mindig ugyanannyi lesz a vágások száma?

4. Egy

n

oldalú konvex sokszög átlói legfeljebb hány háromszöget fognak közre a háromszög belsejében?

5. Egy

6 \times 10

-es négyzetrácsban hány téglalapot lehet úgy kijelölni, hogy oldalaik rácsegyenesek legyenek?

6. Egy

27

db egybevágó kis kockából kirakott

3 \times 3 \times 3

-as kockában hány olyan téglatest jelölhető ki, amely ezen kis kockákból áll?

7. Hány olyan ötjegyű szám van, amelyben a számjegyek nemcsökkenő sorrendben követik egymást?

8. A

3

számot négy különböző módon bontjuk fel pozitív egészek összegére:

3

;

2 + 1

;

1 + 2

, valamint

1 + 1 + 1

. Az összeadásban a tagok sorrendje lényeges, így az

1 + 2

és a

2 + 1

különböző felbontásnak számít. Hány különböző módon bonthatjuk fel az

n

természetes számot?
Ez a KöMaL-ban F. 2273. sorszámú feladatként lett kitűzve, megoldása a lap 1981. márciusi számában a 106. oldalon olvasható.

9. Mutassuk meg, hogy egy

n

(

n > 1

) elemű halmaz részhalmazaiból legfeljebb

2^{n - 1}

választható úgy ki, hogy közülük bármely kettőnek legyen közös eleme!

10. Mutassuk meg, ha egy

n

elemű halmaznak kiválasztottuk

m

db részhalmazát úgy, hogy bármely két részhalmaz metszete üres, akkor

m \leq n

11. Mutassuk meg, ha egy

n

elemű halmaznak kiválasztottuk

m

db részhalmazát úgy, hogy bármely két részhalmaz uniója kiadja az alaphalmazt, akkor

m \leq n

12. Mutassuk meg, ha egy

n

elemű halmaznak kiválasztottuk

m

db részhalmazát úgy, hogy ezek egyike sem részhalmaza valamely másik kettő uniójának, akkor

m \leq n

Róka Sándor

¹Kalmár László: A matematika alapjai (egyetemi jegyzet), I. kötet, 9. oldal.

²Halmos Pál: A matematika művészete, Természet Világa, 1976/7, 299‐303. oldalak.