Hány bőrt lehet lehúzni egy problémáról? (II.)
Tarcsay Tamás
2006/06/16 12:57
544 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Egy bőrt már lehúztunk, lássuk a következőt!

Hány bőrt lehet lehúzni egy problémáról? (I.)

A K(n) meghatározásához vezethet olyan út is, hogy néhány konkrét, nem túl nagy n-re meghatározzuk az értékét. Ezt megtehetjük úgy, hogy megadjuk azokat a permutációkat, amelyekben egyik szám sem annyiadik, amennyi az értéke. Például:

Ha n=2, akkor egyetlen "jó" permutáció van: 21.

Ha n=3, a "jó" permutációk száma K(3)=2: 231, 312.

Ha n=4, a "jó" permutációk száma K(4)=9, ezek a következők:

Ha n=5, a "jó" permutációk száma, K(5)=44:
Ha szisztematikusan keressük a "jó" permutációkat, egy újabb rekurziót sejthetünk meg a K(n)-re, sejtésünket erősíthetik az 1. táblázatban található adatok is. A sejtés így szól:
A sejtés igazolása egy teljes indukció jellegű bizonyítással történhet.

Az 1, 2, ..., n, (n+1), (n+2) számok "jó" permutációinak halmazát két osztályra bontjuk.

Az A osztályba azok a permutációk vannak, amelyek a következőképpen jönnek létre:
Tekintjük az 1, 2, ..., (n+1) elemek "jó" permutációit, majd e permutációk egy elemét kicseréljük az (n+2)-vel. Nyilvánvaló, hogy ilyen módon az 1, 2, ..., n, (n+1), (n+2) számok "jó" permutációit kapjuk.
Minden korábbi "jó" permutációból (n+1) új "jó" permutációt kapunk, tehát az A osztály számossága: (n+1)K(n+1).

A B osztályba tartozzanak azok a permutációk, amelyeket úgy kapunk, hogy az 1, 2, ..., (n+1) elemek azon ismétlés nélküli permutációiból indulunk ki, amelyekben pontosan egy elem van a helyén, és ezt az elemet cseréljük ki az (n+2)-vel. Nyilvánvaló, hogy ilyen módon is az 1, 2, ..., n, (n+1), (n+2) számok "jó" permutációit kapjuk.

A kiindulásul választott permutáció halmaz számossága K(n)(n+1), és minden ilyen permutációból 1 új permutációt kapunk, tehát a B osztály számossága K(n)(n+1).

Megmutatható, hogy az A és a B osztályok diszjunktak és egyesítésük a vizsgált permutációk halmaza. A sejtésünket igazoltuk.

(Megjegyezzük, hogy az itt vázolt bizonyítást Bérczi Gergely adta gimnazista korában.)
Ezzel a rekurzióval gyorsabban számolhatunk újabb K(n) értékeket, az első táblázat könnyebben bővíthető tovább.

Tarcsay Tamás

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek