velmi velmi tvrdy kombinacny problem !!!?

V kancelárii v rôznych časoch počas dňa dáva šéf sekretárke list na zadanie textu, zakaždým, keď dá list na hromadu v schránke sekretárky. Keď je čas, sekretárka vezme vrchné písmeno z hromady a napíše ho. Počas dňa je možné napísať deväť písmen a šéf ich doručí v poradí 1, 2, 3, 4, 5, 6, 7, 8, 9.

Pri odchode na obed sekretárka oznámi kolegovi, že písmeno 8 už bolo zadané na stroji, ale o rannom písaní na stroji nič iné nehovorí. Kolega si kladie otázku, ktoré z deviatich písmen zostáva na písanie po obede a v akom poradí sa budú písať. Na základe vyššie uvedených informácií, koľko takýchto objednávok na písanie po obede je možných? (To, že už nemusíte písať žiadne písmená, je jednou z možností.)

3 odpovede

• BinhObľúbená odpoveď

  máme teda 8 možných scenárov

  scenár č. 1: To ráno napísala iba 1 písmeno (písmeno č. 8).

  máme teda 7combination0 = 1 možné poradie (na zásobníku zostávajú písmená 7 6 5 4 3 2 1)

  poznámka: 7 = # písmená vylučujú 8. písmeno, 0 = # písmená, ktoré ráno napísala tiež s 8. písmenom

  pretože šéf môže odhodiť 9. písmeno kedykoľvek po obede, 9. písmeno môže byť navrchu alebo niekde v strede alebo v dolnej časti stohu.

  takže musíme vynásobiť 8combination1 na 1 možné poradie (8 = # z celkového počtu písmen, 1 = 9. písmeno)

  je to teda 8 * 1 = 8 objednávok pre 1. scenár

  scenár č. 2: To ráno napísala iba 2 písmená (písmeno č. 8 a 1 zo 7 ďalších písmen).

  7kombinácia1 = 7

  musíme vynásobiť 8combination1, aby sme vzali do úvahy 9. písmeno

  je to teda 7kombinácia1 * 7kombinácia1 = 49 objednávok pre 2. scenár

  scenár č. 3: To ráno napísala iba 3 písmená (písmeno č. 8 a 2 zo 7 ďalších písmen).

  7kombinácia2 = 21

  je to teda 7kombinácia2 * 6kombinácia1 = 126 objednávok pre 3. scenár

  scenár č. 4: To ráno napísala iba 4 písmená (písmeno č. 8 a 3 zo 7 ďalších písmen).

  7kombinácia3 = 35

  je to teda 7kombinácia3 * 5kombinácia1 = 175 objednávok pre 4. scenár

  scenár č. 5: To ráno napísala iba 5 písmen (písmeno č. 8 a 4 zo 7 ďalších písmen).

  7kombinácia4 = 35

  je to teda 7kombinácia4 * 4kombinácia1 = 140 objednávok pre 5. scenár

  scenár č. 6: To ráno napísala iba 6 písmen (písmeno 8 a 5 zo 7 ďalších písmen).

  7kombinácia5 = 21

  je to teda 7kombinácia5 * 3kombinácia1 = 63 objednávok pre 6. scenár

  scenár č. 7: To ráno napísala iba 7 písmen (písmeno 8 a 6 zo 7 ďalších písmen).

  7kombinácia6 = 7

  je to teda 7kombinácia6 * 2kombinácia1 = 14 objednávok pre 7. scenár

  scenár č. 8: To ráno napísala iba všetkých 8 písmen.

  7kombinácia7 = 1

  sen o zosnulej babičke význam

  je to teda 7kombinácia7 * 1kombinácia1 = 1 objednávka pre 8. scenár

  Potom pridajte všetky možné scenáre, ktoré získate

  8 + 49 + 126 + 175 + 140 + 63 + 14 + 1 = 576 takýchto objednávok po obede je možné.

  Mannnn ... to je veľa možných príkazov, je naštvané, že druhá sekretárka to urob mentálne, ako sa čuduje, ak to dokáže mentálne, asi chce získať lepšiu prácu ako sekretárka: P

• Apratim r

  V čase obeda nech je na hromade k písmená k, kde 0 â ?? ¤ k â ?? ¤ n = 7. (Takže sekretárka už vyťukala (n + 1) -tú, t. J. 8.)

  Každá z C (n, k) možných k-zbierok písmen môže byť napísaná iba v 1 (tj. Klesajúcom) poradí, ale šéf môže vkĺznuť do (n + 2) -tej v ktoromkoľvek z 1 spôsobov k + 1 .

  Takže pomocou Lemmy, ktorá sa ukázala nižšie, je celkový počet objednávok na obed po obede

  _ (k = 0 = n) (k + 1) C (n, k) = (n + 2) 2ⁿ⁻Â1 = 9 · 2⁶ = 576.

  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  Lema: Pre n â ?? ¥ 1, â ???? _ (k = 0 â ???? n) (k + 1) C (n, k) = (n + 2) 2ⁿ⁻¹.

  Dôkaz o lemme: Nech f (x) = (1 + x) ⁿ = â ???? _ (k = 0 â ???? n) C (n, k) x ^ k.

  Potom x f (x) = x (1 + x) ⁿ = â ???? _ (k = 0 â ???? n) C (n, k) x ^ (k + 1), takže

  (xf (x)) '= (1 + (n + 1) x) (1 + x) ⁿ⁻¹ = â ???? _ (k = 0 â ???? n) (k + 1) C (n, k) x ^ k.

  Teraz nastavte x = 1. â ????

• ?

  Pozrime sa, či to môžeme zjednodušiť jedným pozorovaním: Po zadaní ľubovoľného písmena musia byť všetky písmená, ktoré zostali na hromádke, ktorú chcete zadať, napísané v zostupnom číselnom poradí. Ak bolo písmeno 8 jediné, ktoré bolo napísané pred obedom, ostatné sú na hromádke zhora nadol v poradí

  7, 6, 5, 4, 3, 2, 1

  a jedinou otázkou je, či niektorá z nich chýba (už napísaná).

  Každé písmeno môže byť na hromádke v čase obeda alebo nie. Pre každú existujú iba dve možnosti a poznáme poradie všetkých, ktoré tam sú. Takže existujú

  2 ^ 7 = 128 možných stavov pre týchto sedem písmen.

  A čo list 9? Nevieme, či je to zadané, alebo či sa to prejaví neskôr, a ak áno, v akej polohe na zásobníku. Takže pre každý možný stoh písmen 1 - 7 je počet pozícií v poradí, v akom sa budú písať písmená 9, počet písmen 1 - 7 plus dve, pretože písmeno 9 sa môže zvýšiť

  - po zadaní ktoréhokoľvek z nich,

  sen o upratovaní domu

  - pred napísaním ktoréhokoľvek z nich, alebo -

  - vôbec nie, ak bola zadaná aj pred obedom.

  Musíme teda vziať našich 128 možných stohov písmen 1-7 a prepočítať ich podľa počtu písmen v stohu.

  Zostáva 7 písmen: 1 spôsob, ktorý sa môže stať, krát 9 možností pre písmeno 9 = 9 objednávok na písanie

  6 vľavo: 7 spôsobov * 8 pozícií s písmenom 9 = 56

  5 vľavo: 7C5 = 21 spôsobov * 7 = 147

  Zostávajú 4: 7C4 = 35 spôsobov * 6 = 210

  Zostávajú 3: 35 * 5 = 175

  2 vľavo: 21 * 3 = 63

  Zostáva 1: 7 * 2 = 14

  0 vľavo: 2

  Upozorňujeme, že ak nezostane žiadne z písmen 1 - 7, stále existujú dva možné príkazy na písanie po obede, podľa toho, či je písmeno 9 tiež hotové alebo ešte len príde.

  Pridaním týchto dostaneme

  56 + 147 + 210 + 175 + 63 + 14 + 2 = je možné iba 667 objednávok po obede.