Hogyan oldanátok meg ezt a feladatot? (Kombinatorika)
A feladat a következőképpen szól:
"Rendezzük nagyság szerint sorrendbe azokat a számokat, amelyek az 1,2,...,9 jegyek mindegyikét pontosan egyszer tartalmazzák. Melyik szám áll a 100.000-dik helyen?"
Úgy próbáltam megoldani, hogy: Az első eset, amikor minden szám a helyén van (azaz az 1-es az első, a 2-es a második helyen, tehát növekvő sorrendben: 1,2,3,4,5,6,7,8,9).
A második eset, amikor - már amennyiben a növekvő sorrend alapján gondolkozunk, a feladat pedig ezt kéri - a kettő legkisebb helyiértéken álló szám cserél helyet, tehát a nyolcas és a kilences. Így lesz 1,2,3,4,5,6,7,8,9 és 1,2,3,4,5,6,7,9,8. Ez két eset, ezt össze kell szorozni az első verzióval, így 1x2=2.
A harmadik verziót ki lehet számolni az előző alapján. Ha az utolsó három számnak nem lesz állandó a helye, akkor a 7,8 és a 9 fog változni. A második esetet kiszámoltuk, hogy két szám kétféle sorrendet vehet fel. Három számból háromféle ((7,8), (8,9), (7,9)) kettős számpárt lehet alkotni, értelem szerüen a maradék egy szám a megmaradt harmadik helyen áll. Az ugye háromféle lehet, tehát: 1x2x3. Nyilvánvaló, hogy 1x2x3=3!
Ebből következik, hogy az összes eset maximuma 9!, ami 362.880>100.000. 8! azomban "csak" 40.320<100.000 tehát mind a kilenc helyiértékkel számolni kell a feladat megoldásakor.
Azt írtam még fel (nem vagyok benne, hogy jó a megfogalmazás, de érteitek, hogy értem), hogy: "a feladat megoldásának algoritmusa az, hogy a legkisebb szám, amely nem marad az eredeti helyén a legkisebb olyan helyiértékre ugyrik, ahol még nem volt. Amikor a 9-es lesz egy adott helyiértéken utána a tőle eggyel nagyobb helyiérték sem marad változatlan a következő lépésben."
Lényeg a lényeg csak ennyit tudtam saját kútfőből összehozni, remélem legalább az alapelgondolás nem hibás.
Örülnék ha valaki le tudná vezetni, hogy mi a 100000.-dik szám.
válasza: válasza:Az elgondolás jó, de rohadt macerás lenne ezt választani. Egyszerűbb lenne fordítva gondolkodni, vagyis ne az utolsó jegyeket nézzük, hanem az első jegyeket.
1-essel kezdődő szám 8!=40.320 szám van. Könnyű rájönni, hogy mindegy, hogy melyik számot írjuk előre, ugyanúgy 8!-sal kell számolnunk, tehát mindegyik kezdődéssel ugyanannyi szám van. Ha leírnánk az összes 1-gyel kezdődő számot, akkor 40.320 számot írnánk le, ha ezután az összes 2-essel kezdődőt, akkor 80.640, ha az összes 3-mal kezdődőt, akkor 120.960 számot írnánk le. Ezek között lenne meg a 100.000 szám, tehát az első helyiértéken a 3-as szerepel.
A 3-assal kezdődő számok előtt 80.640 szám volt, így 19.360 számot kell még leírnunk. Nézzük, hogy hány 31-gyel kezdődő szám van, erre a válasz 7!=5040, a 32-vel, 34-gyel és 35-tel kezdődő számok is ennyien vannak, ha ezeket mind leírjuk, akkor még 20160 számot írunk le, ami meghaladja a 19.360-as darabszámot, tehát a keresett szám 35-tel kezdődik.
A 35-tel kezdődő számokig további 3*5040=15.120 számot írunk le, így még 4240 darab számra van szükségünk. Ha a 351-gyel kezdődő számokat nézzük, akkor belőlük 6!=720 van, ugyanígy a 352-vel, 354-gyel, 356-tal, 357-tel és 358-cal kezdődő számok, ezeket leírva további 4320 számot írunk le, tehát a keresett szám 358-cal kezdődik.
A legnagyobb 357-tel kezdődő számot leírva 3600 számot írunk le, így még 640 számra van szükség. A 3581-gyel kezdődő számok 5!=120-an vannak, így a 640-et a 3589-cel kezdődő számok felírásával érjük el.
A 3587-tel kezdődő számok felírásával további 600 számot írunk fel, így már csak 40 számra van szükségünk. A 35891-gyel kezdődő számok 4!=24-en vannak, így a 35892-vel kezdődő számok felírásával el is jutunk a 100.000. számig, tehát 35892-vel kezdődik a keresett szám.
Ha leírjuk az összes 35891-gyel kezdődő számot, akkor még 16 számra van szükségünk. A 358921-gyel kezdődő számok 3!=6-an vannak, tehát a szám 358927-tel fog kezdődni. A 358926-tal kezdődő számokat felírva még 4 számra van szükségünk.
A 3589261 számmal kezdődő számokból 2!=2 van, így 3589267-tel fog a 100.000. szám kezdődni. Ehhez még a megmaradt 1-est hozzáírjuk, így a 35.892.671-es szám lesz a sorban a százezredik szám.
A számítás menete egyébként roppant mód hasonlít a számrendszerek közti átszámításoknál tapasztaltakhoz. Azt a számítást a következő hozzászólásban leírom.
válasza:Annyi csak a dolgunk, hogy a 100.000-et elosztjuk maradékosan a faktoriálisokkal, majd a kapott maradékot szintén, mindaddig, amíg az eredmény nem lesz 0. Az osztást 8!-sal kezdjük, utána 7!, 6!, és így tovább, egészen 0!=1-ig:
100000 : 8! = 2, marad 19360
19360 : 7! = 3, marad 4240
4240 : 6! = 5, marad 640
640 : 5! = 5, marad 40
40 : 4! = 1, marad 16
16 : 3! = 2, marad 4
4 : 2! = 2, marad 0
0 : 1! = 0, marad 0
0 : 0! = 0, marad 0
Most az eredményeket nézzük. Ahogy a fenti levezetésben láthattuk, a hányados a kiválasztandó szám sorszámát mutatja meg, csak egy kis csavar van a történetben; írjuk fel a számokat növekvő sorrendben 1-9-ig: 1;2;3;4;5;6;7;8;9. A csavar az, hogy a számok sorszámozása nem 1-től, hanem 0-tól kezdődik, vagyis az 1-es szám a "nulladik", a 2-es szám az első, és így tovább. Ennek megfelelően nézzük, hogy a keresett számot hogyan kapjuk: fentről lefelé haladunk a hányadosokkal:
1;2;3;4;5;6;7;8;9, nekünk a "második" szám kell, ami a 3.
1;2;4;5;6;7;8;9, nekünk a "harmadik" szám kell, ami az 5.
1;2;4;6;7;8;9, nekünk az "ötödik" szám kell, ami a 8.
1;2;4;6;7;9, nekünk az "ötödik" szám kell, ami a 9.
1;2;4;6;7, nekünk az "első" szám kell, ami a 2.
1;4;6;7, nekünk a "második" szám kell, ami a 6.
1;4;7, nekünk a "második" szám kell, ami a 7.
1;4, nekünk a "nulladik" szám kell, ami az 1.
4, nekünk a "nulladik" szám kell, ami a 4.
Tehát a keresett szám: 358.926.714 (az előbbi válaszomban a 4-es lemaradt, nem vettem észre, hogy az még van).
Ezzel sikerült megadnunk egy olyan algoritmust, amivel akárhányadik sorszámú szám meghatározható. Értelemszerűen a sorszám az legalább 1, legfeljebb 9!=362.880 egész szám lehet.
Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!