Skatulyaelv
PermutációkTávolságRendezés
RekurzióIndukcióDiszkrét matematika
Horváth Gábor/Tengely Szabolcs
Tengely Szabolcs
tengely@science.unideb.hu
http://www.math.unideb.hu/~tengely

Tengely Szabolcs

2014.04.11

Diszkrét matematika

1 / 21Skatulyaelv
PermutációkTávolság
Rendezés
RekurzióIndukcióÁttekintés
Skatulyaelv
PermutációkTávolságRendezés
RekurzióIndukcióTengely Szabolcs

2014.04.11

Diszkrét matematika

2 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́t a skatulyaelv!
Az első fontos észrevételhez az úgynevezett skatulyaelv vezet el.
Adott n gyufaszál és m skatulya úgy, hogy n > m. A gyufaszálakatelhelyezzük a skatulyákba. Ekkor létezik olyan skatulya, amelyben
1-nél több gyufaszál található.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

3 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́t a skatulyaelv!
Az első fontos észrevételhez az úgynevezett skatulyaelv vezet el.
Adott n gyufaszál és m skatulya úgy, hogy n > m. A gyufaszálakatelhelyezzük a skatulyákba. Ekkor létezik olyan skatulya, amelyben
1-nél több gyufaszál található.

Tengely Szabolcs

2014.04.11

♦♥

♠

♣

1

1

2

1

Diszkrét matematika

3 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́t a skatulyaelv!
Az első fontos észrevételhez az úgynevezett skatulyaelv vezet el.
Adott n gyufaszál és m skatulya úgy, hogy n > m. A gyufaszálakatelhelyezzük a skatulyákba. Ekkor létezik olyan skatulya, amelyben
1-nél több gyufaszál található.

Tengely Szabolcs

2014.04.11

♦

♥♠

♣

1

1

2

1

0

1

2

2

Diszkrét matematika

3 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́t a skatulyaelv!
Az első fontos észrevételhez az úgynevezett skatulyaelv vezet el.
Adott n gyufaszál és m skatulya úgy, hogy n > m. A gyufaszálakatelhelyezzük a skatulyákba. Ekkor létezik olyan skatulya, amelyben
1-nél több gyufaszál található.

Tengely Szabolcs

2014.04.11

♦

♥♠

♣

1

1

2

10

1

2

2

3

1

0

1

Diszkrét matematika

3 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́t a skatulyaelv!
Az első fontos észrevételhez az úgynevezett skatulyaelv vezet el.
Adott n gyufaszál és m skatulya úgy, hogy n > m. A gyufaszálakatelhelyezzük a skatulyákba. Ekkor létezik olyan skatulya, amelyben
1-nél több gyufaszál található.
♦♥

♠

♣

1

12

1

0

1

2

2

3

10

1

5 lap, 4 szı́n =⇒ skatulyaelv: mindig van legalább 2 azonos szı́nű
lap!
Tengely Szabolcs

2014.04.11

Diszkrét matematika

3 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

A szı́n beazonosı́tása
A skatulyaelv miatt az 5 lap között mindig van legalább 2 azonos
szı́nű.
A segéd az egyiket teszi félre, amit a bűvész meg fog nevezni! Amásikat helyezi legfelülre, ı́gy a bűvész azonnal tudja az ismeretlenlap szı́nét.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

4 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

A szı́n beazonosı́tása
A skatulyaelv miatt az 5 lap között mindig van legalább 2 azonosszı́nű.
A segéd az egyiket teszi félre, amit a bűvész meg fog nevezni! Amásikat helyezi legfelülre, ı́gy a bűvész azonnal tudja az ismeretlenlap szı́nét.
A pakliban 52 lap található, 13 ♦, 13 ♥, 13 ♠ és 13 ♣. A bűvész
már ismeri a lap szı́nét és abból a szı́nből az egyik lap a kezébenvan, ı́gy 12 lehetőség maradt az ismeretlen lapra.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

4 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

A szı́n beazonosı́tása
A skatulyaelv miatt az 5 lap között mindig van legalább 2 azonos
szı́nű.
A segéd az egyiket teszi félre, amit a bűvész meg fog nevezni! Amásikat helyezi legfelülre, ı́gy a bűvész azonnal tudja az ismeretlenlap szı́nét.
A pakliban 52 lap található, 13 ♦, 13 ♥, 13 ♠ és 13 ♣. A bűvészmár ismeri a lap szı́nét és abból a szı́nből az egyik lap a kezébenvan, ı́gy 12 lehetőség maradt az ismeretlen lapra.
A maradék 3 lap segı́tségével kell meghatározni az ismeretlen lap
számát.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

4 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́tenek a permutációkA 3 lap sorrendje adhat további információt!

Tengely Szabolcs

2014.04.11

Diszkrét matematika

5 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́tenek a permutációk
A 3 lap sorrendje adhat további információt!

Tengely Szabolcs

2014.04.11

Diszkrét matematika

5 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióSegı́tenek a fa gráfok

2342332444
Tengely Szabolcs

232014.04.11

2, 3

4

2, 3, 42, 4

32, 4, 3

3, 2

4

3, 2, 43, 4

2

3, 4, 24, 2

34, 2, 34, 3

24, 3, 2
Diszkrét matematika

6 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióKevés az információ?!

• Az ismeretlen lap szı́ne ismert.
• 12 lap közül kell tudni kiválasztani.
• A maradék 3 lapot 6 féle sorrendbe állı́thatjuk.
• Nincs elég információ?!

Tengely Szabolcs

2014.04.11

Diszkrét matematika

7 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióKevés az információ?!

• Az ismeretlen lap szı́ne ismert.
• 12 lap közül kell tudni kiválasztani.
• A maradék 3 lapot 6 féle sorrendbe állı́thatjuk.
• Nincs elég információ?!
• A segéd valasztja ki a 2 azonos szı́nű lapból melyik lesz atitkos lap és melyiket látja a bűvész!
• Hogyan használjuk ki ezt a lehetőséget?

Tengely Szabolcs

2014.04.11Diszkrét matematika

7 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA lapok távolsága• A lapokat egy körben

A

helyezzük el:
A, 2, 3, . . . , J, Q, K .

2KQ

3• Lapok távolsága: az
4

J

10

5

9

6
8

Tengely Szabolcsóramutató irányában tettlépések száma.
• Például:

A − 6 távolság 5,
6 − A távolság 8.

7

2014.04.11

Diszkrét matematika

8 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA lapok távolsága• A lapokat egy körbenA

helyezzük el:
A, 2, 3, . . . , J, Q, K .

2KQ3• Lapok távolsága: az
4

J

10

5

96
8

óramutató irányában tettlépések száma.
• Például:

A − 6 távolság 5,6 − A távolság 8.
• Két lap között a távolságok

7minimuma legfeljebb 6.
Tengely Szabolcs

2014.04.11

Diszkrét matematika

8 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA négy lap rendezése• A legfelső lap adja meg a szı́nt és a két azonos szı́nűből az

kerül felülre, amelytől a másik 6-nál nem nagyobb távolságra
helyezkedik el.
• A maradék 3 lapot úgy rendezi a segéd, hogy az megadja akét lap minimális távolságát a körön.
• Megegyezés szükséges a lapok értékét illetően!

Tengely Szabolcs

2014.04.11

Diszkrét matematika

9 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA négy lap rendezése• A legfelső lap adja meg a szı́nt és a két azonos szı́nűből az

kerül felülre, amelytől a másik 6-nál nem nagyobb távolságra
helyezkedik el.
• A maradék 3 lapot úgy rendezi a segéd, hogy az megadja akét lap minimális távolságát a körön.
• Megegyezés szükséges a lapok értékét illetően!

Két természetes választás:•,,,,•,,,,. . .,Tengely Szabolcs

2014.04.11,,,,,,. . .,,,. . .,,,,Diszkrét matematika,,
9 / 21Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA négy lap rendezésePéldák:,,,,Távolságok: ♠3 − ♠10 = 7 és ♠10 − ♠3 = 6, azaz a legfelső lap a♠10 és a maradék 3 lappal a 6-os távolságot kell megadni.
A sorrend a következő: 1 = ♣A < 2 = ♦3 < 3 = ♥8♣A, ♦3, ♥8♣A, ♥8, ♦3♦3, ♣A, ♥8♦3, ♥8, ♣A♥8, ♣A, ♦3♥8, ♦3, ♣A

1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

1
2
3
4
5
6A négy lapot a segéd a következő sorrendbe rakja:♠10, ♥8, ♦3, ♣A.
Tengely Szabolcs

2014.04.11

Diszkrét matematika

10 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció,,,,Távolságok: ♠4 − ♠9 = 5 és ♠9 − ♠4 = 8.
1 = ♣5 < 2 = ♣J < 3 = ♥Q és ♥Q, ♣5, ♣J ⇒ 5
A lapok sorrendje ebben az esetben tehát: ♠4, ♥Q, ♣5, ♣J.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

11 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció,,,,Távolságok: ♠4 − ♠9 = 5 és ♠9 − ♠4 = 8.
1 = ♣5 < 2 = ♣J < 3 = ♥Q és ♥Q, ♣5, ♣J ⇒ 5A lapok sorrendje ebben az esetben tehát: ♠4, ♥Q, ♣5, ♣J.
Adódik egy másik lehetőség is!
Távolságok: ♣5 − ♣J = 6 és ♣J − ♣5 = 7.
1 = ♠4 < 2 = ♠9 < 3 = ♥Q és ♥Q, ♠9, ♠4 ⇒ 6Egy másik lehetséges megoldás: ♣5, ♥Q, ♠9, ♠4.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

11 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA megfejtés menete
A bűvész megkapja a következő 4 lapot:,,,• Ekkor a bűvész már ismeri a szı́nt: ♦.
• ♥2, ♣7, ♦6 ⇒ 1, 3, 2 ⇒ 2.
• 2 lépést kell tenni a ♦J lapról.
• Az ismeretlen lap: ♦K .

Tengely Szabolcs

2014.04.11

Diszkrét matematika

12 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióA segéd a következő lapokat adja a bűvésznek:,,,• Ekkor a bűvész már ismeri a szı́nt: ♦.
• ♦J, ♣7, ♥2 ⇒ 3, 2, 1 ⇒ 6.
• 6 lépést kell tenni a ♦K lapról.
• Az ismeretlen lap: ♦6.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

13 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióHanoi tornyai
Edouard Lucas 1883-ban kitalált egy matematikai puzzle játékot.
Adott 3 rúd, az elsőn n db korong. Az összes korongot a harmadikrúdra át kell pakolni úgy, hogy közben:• egy lépésben csak egy korongot szabad áthelyezni,• minden lépésnél csak a rúdon legfelül lévő korong mozgatható,• nagyobb korongot kisebbre helyezni tilos.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

14 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
IndukcióPéldákAz n = 1 eset egyszerű, az első rúdról áthelyezzük a korongot aharmadikra, azaz egy lépésben kész a megoldás. Az n = 2 esetben:

Tengely Szabolcs2014.04.11

Diszkrét matematika

15 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Minimum lépésszámJelölje Tn az n korong esetében a legkisebb lépésszámot, amivel a
probléma megoldható. Az előzőek alapján: T0 = 0, T1 = 1 és
T2 = 3. Megmutatjuk, hogy
Tn ≤ 2Tn−1 + 1.
Megoldás: az A rúdról a felső n − 1 korongot Tn−1 lépésben áttudjuk mozgatni a B rúdra. A legnagyobb korongot áthelyezzük aC rúdra. A B rúdon lévő n − 1 korongot pedig Tn−1 lépésbenáthelyezzük a C rúdra. Azaz létezik megoldás legfeljebb 2Tn−1 + 1lépésben.

Tengely Szabolcs

2014.04.11

Diszkrét matematika

16 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Minimum lépésszámMás stratégiát követve a legnagyobb korong átmozgatásához A-ról
C -be az n − 1 kisebb korongot át kell helyezni A-ról a B rúdra. Ezt
legjobb esetben Tn−1 lépésben tudjuk megtenni. A legnagyobb
korong A-ról C -be mozgatása után a kisebb korongokat a B-ről
C -re kell átpakolni, amihez legalább Tn−1 lépés szükséges. Innen
Tn ≥ 2Tn−1 + 1.
A két egyenlőtlenségből pedig
Tn = 2Tn−1 + 1adódik.
Tengely Szabolcs

2014.04.11

Diszkrét matematika

17 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Megoldás n = 3 esetében

Tengely Szabolcs

2014.04.11

Diszkrét matematika

18 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Megoldás n = 3 esetében

Tengely Szabolcs

2014.04.11

Diszkrét matematika

19 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Megoldás n = 3 esetében

Az alábbi táblázatban találhatóak Tn értékei kis n esetébenn0123Tengely Szabolcs

Tn01372014.04.11n4567

Tn15
3163127n891011

Tn
255
511
1023
2047

Diszkrét matematika

20 / 21

Skatulyaelv
PermutációkTávolságRendezésRekurzió
Indukció

Formula Tn -re
A táblázat alapján azt sejtjük, hogy
Tn = 2n − 1.
Ezt indukcióval igazolhatjuk. Az állı́tás n = 0 esetében igaz,
T0 = 0 és a formula alapján T0 = 20 − 1 = 0. Hasonlóan n = 1esetében tudjuk, hogy T1 = 1, a formula szerint pedig
T1 = 21 − 1 = 1. Feltesszük, hogy az állı́tást már sikerült igazolni
valamilyen k egészre, azaz Tk = 2k − 1. Megmutatjuk, hogy
Tk+1 = 2k+1 + 1. A rekurzı́v definició miatt Tk+1 = 2Tk + 1.
Kihasználva az indukciós feltételt
Tk+1 = 2(2k − 1) + 1 = 2k+1 − 1.
Így az állı́tás igaz minden n ≥ 0 egész esetében.
Tengely Szabolcs

2014.04.11

Diszkrét matematika

21 / 21