Kombinatorika je oblasť matematiky, ktorá študuje otázky o tom, koľko rôznych kombinácií možno za určitých podmienok vytvoriť z daných predmetov. Základy kombinatoriky sú veľmi dôležité pre hodnotenie pravdepodobnosti náhodných udalostí, od r práve tie umožňujú vypočítať zásadne možný počet rôznych scenárov vývoja udalostí.

Základný vzorec kombinatoriky

Nech je k skupín prvkov a i-ta skupina pozostáva z n i prvkov. Z každej skupiny vyberieme jednu položku. Potom celkový počet N spôsobov, ktorými je možné takúto voľbu uskutočniť, je určený pomerom N = n 1 * n 2 * n 3 * ... * n k.

Príklad 1 Vysvetlime si toto pravidlo na jednoduchom príklade. Nech existujú dve skupiny prvkov, prvá skupina pozostáva z n 1 prvkov a druhá - z n 2 prvkov. Koľko rôznych párov prvkov môžete vytvoriť z týchto dvoch skupín, aby ste sa spárovali s jedným prvkom z každej skupiny? Predpokladajme, že sme vzali prvý prvok z prvej skupiny a bez toho, aby sme ho zmenili, prešli všetky možné dvojice, pričom sme zmenili iba prvky z druhej skupiny. Takýchto párov pre tento prvok môže byť n2. Potom vezmeme druhý prvok z prvej skupiny a tiež k nemu vytvoríme všetky možné dvojice. Bude tiež n 2 takýchto párov. Pretože v prvej skupine je len n 1 prvkov, bude možných n 1 * n 2 možností.

Príklad 2 Koľko trojciferných párnych čísel možno poskladať z číslic 0, 1, 2, 3, 4, 5, 6, ak sa čísla môžu opakovať?
Riešenie: n 1 = 6 (keďže ako prvú číslicu môžete vziať ľubovoľnú číslicu od 1, 2, 3, 4, 5, 6), n 2 = 7 (pretože ako druhú číslicu môžete vziať ľubovoľnú číslicu od 0 , 1, 2 , 3, 4, 5, 6), n 3 = 4 (keďže akékoľvek číslo od 0, 2, 4, 6 môže byť brané ako tretia číslica).
Takže, N = n1 * n2 * n3 = 6 * 7 * 4 = 168.

V prípade, keď všetky skupiny pozostávajú z rovnakého počtu prvkov, t.j. n 1 = n 2 = ... n k = n môžeme predpokladať, že každý výber je urobený z tej istej skupiny a prvok po výbere je vrátený do skupiny. Potom sa počet všetkých metód výberu rovná n k. Táto metóda výberu v kombinatorike je tzv odber vzoriek s návratom.

Príklad 3 Koľko zo všetkých štvorciferných čísel možno poskladať z číslic 1, 5, 6, 7, 8?
Riešenie. Pre každú číslicu štvorciferného čísla existuje päť možností, takže N = 5 * 5 * 5 * 5 = 5 4 = 625.

Uvažujme množinu pozostávajúcu z n prvkov. V kombinatorickom vyjadrení sa táto množina tzv všeobecná populácia.

Počet umiestnení n prvkov na m

Definícia 1. Ubytovanie od n prvky podľa m v kombinatorike akékoľvek objednaná sada od m rôzne prvky vybrané z bežnej populácie v n prvkov.

Príklad 4 Rôzne umiestnenia troch prvkov (1, 2, 3) z dvoch budú sady (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2)). Umiestnenia sa môžu navzájom líšiť v prvkoch aj v poradí.

Počet umiestnení v kombinatorike sa označuje ako A n m a vypočíta sa podľa vzorca:

komentár: n! = 1 * 2 * 3 * ... * n (čítaj: "ento-faktoriálne"), navyše sa predpokladá, že 0! = 1.

Príklad 5... Koľko je dvojciferných čísel, v ktorých sú desiatky a jedničky rôzne a nepárne?
Riešenie: odkedy existuje päť nepárnych číslic, a to 1, 3, 5, 7, 9, potom sa táto úloha zredukuje na výber a umiestnenie dvoch z piatich rôznych číslic na dvoch rôznych pozíciách, t.j. špecifikované čísla budú:

Definícia 2. Kombinácia od n prvky podľa m v kombinatorike akékoľvek neusporiadaná sada od m rôzne prvky vybrané z bežnej populácie v n prvkov.

Príklad 6... Pre množinu (1, 2, 3) sú kombinácie (1, 2), (1, 3), (2, 3).

Počet kombinácií n prvkov podľa m

Počet kombinácií je označený C n m a vypočíta sa podľa vzorca:

Príklad 7. Koľkými spôsobmi si môže čitateľ vybrať dve knihy zo šiestich dostupných?

Riešenie: Počet spôsobov sa rovná počtu kombinácií šiestich kníh po dvoch, t.j. rovná sa:

Permutácie n prvkov

Definícia 3. Permutácia od n prvky sa nazývajú ľubovoľné objednaná sada tieto prvky.

Príklad 7a. Všetky možné permutácie množiny pozostávajúcej z troch prvkov (1, 2, 3) sú: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) (3, 2, 1), (3, 1, 2).

Počet rôznych permutácií n prvkov sa označí P n a vypočíta sa podľa vzorca P n = n !.

Príklad 8. Koľkými spôsobmi možno sedem kníh od rôznych autorov usporiadať do jedného radu na poličke?

Riešenie: tento problém sa týka počtu permutácií siedmich rôznych kníh. Existuje P 7 = 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 spôsobov usporiadania kníh.

Diskusia. Vidíme, že počet možných kombinácií možno vypočítať podľa rôznych pravidiel (permutácie, kombinácie, umiestnenie) a výsledok bude iný, keďže princíp počítania a samotné vzorce sú odlišné. Pri pozornom pohľade na definície si všimnete, že výsledok závisí od viacerých faktorov súčasne.

Po prvé, z koľkých prvkov môžeme kombinovať ich množiny (aká veľká je všeobecná populácia prvkov).

Po druhé, výsledok závisí od toho, aké veľké sú šablóny.

Nakoniec je dôležité vedieť, či je pre nás poradie položiek v súprave podstatné. Vysvetlime posledný faktor na nasledujúcom príklade.

Príklad 9. Rodičovského stretnutia sa zúčastňuje 20 osôb. Koľko rôznych možností je na zloženie materského výboru, ak by mal zahŕňať 5 ľudí?
Riešenie: V tomto príklade nás nezaujíma poradie mien v zozname komisií. Ak sa v dôsledku toho v jeho zložení objavia tí istí ľudia, potom je to pre nás významovo rovnaká možnosť. Preto môžeme použiť vzorec na výpočet čísla kombinácie z 20 prvkov po 5.

Veci budú iné, ak bude každý člen výboru spočiatku zodpovedný za určitý smer práce. Potom s tou istou výplatnou páskou komisie môže byť v nej 5! možnosti permutácií na tom záleží. Počet rôznych (v zložení aj v oblasti zodpovednosti) možností je v tomto prípade určený počtom umiestnenia z 20 prvkov po 5.

Samotestovacie úlohy
1. Koľko trojciferných párnych čísel možno zostaviť z číslic 0, 1, 2, 3, 4, 5, 6, ak sa čísla môžu opakovať?
Pretože párne číslo na treťom mieste môže byť 0, 2, 4, 6, t.j. štyri cifry. Ktorékoľvek zo siedmich čísel môže byť na druhom mieste. Na prvom mieste môže byť ktorákoľvek zo siedmich číslic okrem nuly, t.j. 6 možností. Výsledok = 4 * 7 * 6 = 168.
2. Koľko je päťciferných čísel, ktoré sa čítajú rovnako zľava doprava a sprava doľava?
Na prvom mieste môže byť akákoľvek iná číslica ako 0, t.j. 9 možností. Na druhom mieste môže byť ľubovoľné číslo, t.j. 10 možností. Akékoľvek číslo od môže byť aj na treťom mieste, t.j. 10 možností. Štvrtá a piata číslica sú preddefinované, zhodujú sa s prvou a druhou, preto je počet takýchto čísel 9 * 10 * 10 = 900.
3. V triede je desať predmetov a päť vyučovacích hodín denne. Koľkými spôsobmi si môžete naplánovať jeden deň?

4. Koľkými spôsobmi možno vybrať 4 delegátov na konferenciu, ak je v skupine 20 ľudí?

n = C204 = (20!) / (4! * (20-4)!) = (16! * 17 * 18 * 19 * 20) / ((1 * 2 * 3 * 4) * (16! )) = (17 * 18 * 19 * 20) / (1 * 2 * 3 * 4) = 4845.
5. Koľkými spôsobmi je možné zložiť osem rôznych listov do ôsmich rôznych obálok, ak je v každej obálke len jeden list?
Do prvej obálky môžete vložiť 1 z ôsmich listov, do druhej zo siedmich zostávajúcich listov, do tretej zo šiestich atď. n = 8! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40320.
6. Komisia zložená z dvoch matematikov a šiestich ekonómov by mala byť zložená z troch matematikov a desiatich ekonómov. Koľkými spôsobmi sa to dá urobiť?

KOMBINATORIKA

Kombinatorika je oblasť matematiky, ktorá študuje problémy výberu a usporiadania prvkov z určitého základného súboru v súlade s danými pravidlami. Vzorce a princípy kombinatoriky sa používajú v teórii pravdepodobnosti na výpočet pravdepodobnosti náhodných udalostí a podľa toho na získanie zákonov rozdelenia náhodných veličín. To zase umožňuje študovať vzorce hromadných náhodných javov, čo je veľmi dôležité pre správne pochopenie štatistických vzorcov prejavujúcich sa v prírode a technike.

Pravidlá sčítania a násobenia v kombinatorike

Pravidlo súčtu. Ak sa dve akcie A a B navzájom vylučujú a akciu A možno vykonať m spôsobmi a B n spôsobmi, potom ktorúkoľvek z týchto akcií (buď A alebo B) možno vykonať n + m spôsobmi.

Príklad 1

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi možno priradiť jedného sprievodcu?

Riešenie

Do služby môže byť zaradený buď chlapec alebo dievča, t.j. dôstojníkom môže byť ktorýkoľvek zo 16 chlapcov alebo ktorýkoľvek z 10 dievčat.

Podľa súčtového pravidla zistíme, že jedného operátora možno priradiť 16 + 10 = 26 spôsobmi.

Produktové pravidlo. Nech je potrebné vykonať postupne k akcií. Ak je možné prvú akciu vykonať n 1 spôsobmi, druhú akciu n 2 spôsobmi, tretiu n 3 spôsobmi atď. až do k-tej akcie, ktorú možno vykonať nk spôsobmi, potom všetkých k akcií dohromady vykonané:

spôsoby.

Príklad 2

V triede je 16 chlapcov a 10 dievčat. Koľkými spôsobmi možno priradiť dvoch sprievodcov?

Riešenie

Ako prvý strážca môže byť pridelený chlapec alebo dievča. Pretože V triede študuje 16 chlapcov a 10 dievčat, prvého strážnika potom môžete vymenovať 16 + 10 = 26 spôsobmi.

Potom, čo sme si vybrali prvého obsluhujúceho, môžeme si zo zvyšných 25 ľudí vybrať druhého, t.j. Na 25 spôsobov.

Podľa násobiacej vety je možné vybrať dvoch účastníkov 26 * 25 = 650 spôsobmi.

Kombinácie bez opakovania. Kombinácie s opakovaním

Klasickým problémom kombinatoriky je problém počtu kombinácií bez opakovaní, ktorého obsah možno vyjadriť otázkou: koľko spôsoby môcť vybrať m od n rôznych položiek?

Príklad 3

Musíte si vybrať 4 z 10 rôznych kníh dostupných ako darček. Koľkými spôsobmi to môžete urobiť?

Riešenie

Musíme vybrať 4 z 10 kníh a na poradí výberu nezáleží. Preto musíte nájsť počet kombinácií 10 prvkov zo 4:

.

Zvážte problém počtu kombinácií s opakovaniami: existuje r rovnakých objektov každého z n rôznych typov; koľko spôsoby môcť vybrať m () od z nich (n * r) položky?

.

Príklad 4

V cukrárni sa predávali 4 druhy tort: ​​napoleon, eclairs, krehké a lístkové cesto. Koľkými spôsobmi si môžete kúpiť 7 koláčov?

Riešenie

Pretože medzi 7 tortami môžu byť torty rovnakého druhu, počet spôsobov, ako si môžete kúpiť 7 tort, je určený počtom kombinácií s opakovaním od 7 do 4.

.

Umiestnenia bez opakovaní. Umiestnenia s opakovaniami

Klasickým problémom kombinatoriky je problém počtu umiestnení bez opakovaní, ktorého obsah možno vyjadriť otázkou: koľko spôsoby môcť vybrať a miesto na m iný Miesta m od n rôzne položky?

Príklad 5.

Niektoré noviny majú 12 strán. Na stránky týchto novín je potrebné umiestniť štyri fotografie. Koľkými spôsobmi to môžete urobiť, ak žiadna strana novín nesmie obsahovať viac ako jednu fotografiu?

Riešenie.

V tejto úlohe fotografie len nevyberáme, ale umiestňujeme ich na určité strany novín, pričom každá strana novín by nemala obsahovať viac ako jednu fotografiu. Problém sa teda redukuje na klasický problém určenia počtu umiestnení bez opakovania 12 prvkov, každý so 4 prvkami:

Takto možno 4 fotografie na 12 stranách usporiadať 11880 spôsobmi.

Taktiež klasickým problémom kombinatoriky je problém počtu umiestnení s opakovaním, ktorého obsah možno vyjadriť otázkou: koľko spôsoby môcť vybhostiteľ a miesto na m iný Miesta m od n položiek,Smedzi ktorý existuje rovnaký?

Príklad 6.

Chlapcovi ostali zo sady na spoločenskú hru známky s číslami 1, 3 a 7. Rozhodol sa, že pomocou týchto známok dá päťciferné čísla na všetky knihy – zostaví katalóg. Koľko rôznych päťciferných čísel dokáže chlapec vytvoriť?

Permutácie bez opakovaní. Permutácie s opakovaniami

Klasickým problémom kombinatoriky je problém počtu permutácií bez opakovania, ktorého obsah možno vyjadriť otázkou: koľko spôsoby môcť miesto n rôzne položky na n rôzne Miesta?

Príklad 7.

Koľko štvorpísmenových „slov“ možno vytvoriť z písmen slova „manželstvo“?

Riešenie

Všeobecnú populáciu tvoria 4 písmená slova „manželstvo“ (b, p, a, k). Počet „slov“ je určený permutáciami týchto 4 písmen, tzn.

Pre prípad, že medzi vybranými n prvkami sú identické prvky (výber s návratom), problém s počtom permutácií s opakovaniami možno vyjadriť otázkou: koľkými spôsobmi možno preusporiadať n položiek umiestnených na n rôznych miestach, ak medzi n položkami existuje k rôznych typov (k< n), т. е. есть одинаковые предметы.

Príklad 8.

Koľko rôznych kombinácií písmen môžete vytvoriť z písmen slova "Mississippi"?

Riešenie

Obsahuje 1 písmeno „m“, 4 písmená „i“, 3 písmená „c“ a 1 písmeno „p“, spolu 9 písmen. Preto je počet permutácií s opakovaniami

POZADIE SEKCIE "KOMBINATORIKA"

Všetkých N prvkov a žiadny sa neopakuje, potom ide o problém počtu permutácií. Riešenie sa dá nájsť jednoducho. Ktorýkoľvek z N prvkov môže byť na prvom mieste v rade, preto existuje N variantov. Na druhom mieste - ktokoľvek, okrem toho, ktorý už bol použitý na prvé miesto. Preto pre každý z už nájdených N variantov existuje (N - 1) variantov druhého miesta a celkový počet kombinácií sa stáva N * (N - 1).
To isté možno zopakovať pre zvyšok prvkov série. Na úplne posledné miesto ostáva už len jediná možnosť – posledný zostávajúci prvok. Pri predposlednom sú dve možnosti a tak ďalej.
Preto sa pre rad N neopakujúcich sa prvkov možných permutácií rovná súčinu všetkých celých čísel od 1 do N. Tento súčin sa nazýva faktoriál čísla N a označuje sa N! (číta sa „en faktorial“).

V predchádzajúcom prípade sa počet možných prvkov a počet miest v riadku zhodovali a ich počet bol rovný N. Je však možná situácia, keď je miest v rade menej, ako je možných prvkov. Inými slovami, počet prvkov vo vzorke sa rovná nejakému číslu M a M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Najprv môže byť potrebné spočítať celkový počet možných spôsobov, ktorými možno usporiadať do radu M prvkov z N. Takéto metódy sa nazývajú umiestnenia.
Po druhé, výskumníka môže zaujímať počet spôsobov, akými možno vybrať M prvkov z N. V tomto prípade už nie je dôležité poradie prvkov, ale akékoľvek dve možnosti sa musia od seba líšiť aspoň o jeden prvok. . Takéto metódy sa nazývajú kombinácie.

Na nájdenie počtu umiestnení na M prvkoch z N sa možno uchýliť k rovnakým úvahám ako v prípade permutácií. Na prvom mieste tu stále môže byť N prvkov, na druhom (N - 1) atď. Ale na poslednom mieste sa počet možných možností nerovná jednej, ale (N - M + 1), pretože po dokončení umiestnenia budú stále (N - M) nevyužité prvky.
Počet umiestnení nad M prvkami od N sa teda rovná súčinu všetkých celých čísel od (N - M + 1) po N, alebo, čo je rovnaké, podielu N! / (N - M)!.

Je zrejmé, že počet kombinácií prvkov M z N bude menší ako počet umiestnení. Pre každú možnú kombináciu existuje M! možné umiestnenia v závislosti od poradia prvkov tejto kombinácie. Preto, aby ste našli toto číslo, musíte vydeliť počet umiestnení M prvkov z N číslom N!. Inými slovami, počet kombinácií M prvkov z N sa rovná N! / (M! * (N - M)!).

Priatelia! Keďže mám tento mŕtvy zápisník, spýtam sa ho na problém, s ktorým včera zápasili traja fyzici, dvaja ekonómovia, jedna Polytechnická univerzita a jeden humanista. Zlomili sme si celý mozog a neustále dostávame rôzne výsledky. Možno sú medzi vami programátori a matematickí géniovia, okrem toho, úloha je vo všeobecnosti školská a veľmi ľahká, jednoducho neodvodíme vzorec. Pretože sme prestali študovať exaktné vedy a namiesto toho z nejakého dôvodu píšeme knihy a kreslíme obrázky. Prepáč.

Takže pozadie.

Dostal som novú bankovú kartu a ako obvykle som ľahko uhádol jej PIN kód. Ale nie v rade. Povedzme, že kód PIN bol 8794 a nazval som ho 9748. To znamená, že triumfujem uhádol všetky čísla ktoré boli obsiahnuté v tomto štvorcifernom čísle. no áno, nie samotné číslo, ale len tak jeho zložky majúčudoval sa. Ale všetky čísla sú správne! POZNÁMKA - Konal som náhodne, to znamená, že som nemusel usporiadať už známe čísla v správnom poradí, konal som len v duchu: tu sú štyri mne neznáme čísla a verím, že medzi nimi môžu byť 9, 7, 4 a 8 a ich poradie nie je dôležité. Hneď sme sa čudovali koľko možností som vôbec mal(asi aby som pochopil, aké je to super, že som to len zobral a uhádol). To znamená, z koľkých kombinácií štyroch čísel som si musel vybrať? A potom, prirodzene, začalo peklo. Celý večer nám explodovali hlavy a v dôsledku toho mal každý úplne iné odpovede! Dokonca som si všetky tieto kombinácie začal zapisovať do zošita za sebou, ako pribúdali, ale pri štyroch stovkách som si uvedomil, že ich je viac ako štyristo (v každom prípade to vyvrátilo odpoveď fyzika Thresha, ktorý ubezpečil mi, že tam bolo štyristo kombinácií, ale stále to nebolo úplne jednoznačné) - a vzdal som sa.

Vlastne, podstatu otázky. Aká je pravdepodobnosť uhádnutia (v akomkoľvek poradí) štyroch čísel obsiahnutých v štvorcifernom čísle?

Alebo nie, preformulujeme (som humanista, prepáčte, hoci som mal vždy veľkú slabosť na matematiku), aby to bolo čoraz jasnejšie. koľko neopakujúce sa kombinácie čísel sú obsiahnuté v radoch radových čísel od 0 do 9999? ( nemýľte si to prosím s otázkou „koľko kombinácií neopakujúce sačíslice "!!! čísla sa môžu opakovať! 2233 a 3322 sú v tomto prípade rovnaké kombinácie!!).

Alebo konkrétnejšie. Musím štyrikrát uhádnuť jedno číslo z desiatich. Ale nie v rade.

No, alebo niečo iné. Vo všeobecnosti musíte zistiť, koľko možností som mal pre číselnú kombináciu, z ktorej bol vytvorený PIN kód karty. Pomoc, dobrí ľudia! Len, prosím, pomôžte, nezačnite hneď písať, že týchto 9999 možností je(včera to každému napadlo ako prvé), lebo to je nezmysel - veď z perspektívy, ktorá nás znepokojuje, je číslo 1234, číslo 3421, číslo 4312 atď. rovnaký! Áno, čísla sa môžu opakovať, pretože je tam PIN kód 1111 alebo tam napríklad 0007. Namiesto PIN kódu môžete uviesť číslo auta. Povedzme, aká je pravdepodobnosť uhádnutia všetkých jednotlivých číslic, ktoré tvoria číslo auta? Alebo, aby som úplne odstránil teóriu pravdepodobnosti – koľko číselných kombinácií som si musel vybrať?

Prosím, podporte svoje odpovede a úvahy nejakými presnými vzorcami, pretože včera sme sa včera skoro zbláznili. Vopred veľmi pekne ďakujem!

P.S. Jeden šikovný človek, programátor, umelec a vynálezca, práve veľmi správne navrhol správne riešenie problému, vďaka čomu som mal pár minút skvelej nálady: " riešenie problému je toto: má obsedantno-kompulzívnu poruchu, liečba je nasledovná: vydať sa a túliť sa k paradajkám. Viac by ma na jej mieste znepokojovala nie otázka „aká je pravdepodobnosť“, ale otázka „venujem pozornosť všetkým týmto číslam“? Vo všeobecnosti ani nie je čo dodať :)

Nižšie uvedená kalkulačka je navrhnutá tak, aby generovala všetky kombinácie n až m prvkov.
Počet takýchto kombinácií možno vypočítať pomocou kalkulačky kombinatorických prvkov. Permutácie, umiestnenie, kombinácie.

Popis algoritmu generovania pod kalkulačkou.

Algoritmus

Kombinácie sú generované v lexikografickom poradí. Algoritmus pracuje s ordinálnymi indexmi prvkov množiny.
Zoberme si príklad algoritmu.
Pre jednoduchosť uvažujme množinu piatich prvkov, ktorých indexy začínajú 1, konkrétne 1 2 3 4 5.
Je potrebné vygenerovať všetky kombinácie veľkosti m = 3.
Najprv sa inicializuje prvá kombinácia danej veľkosti m - indexy vo vzostupnom poradí
1 2 3
Ďalej sa kontroluje posledný prvok, to znamená i = 3. Ak je jeho hodnota menšia ako n - m + i, potom sa zvýši o 1.
1 2 4
Posledný prvok sa znova skontroluje a znova sa zvýši.
1 2 5
Teraz sa hodnota prvku rovná maximálnemu možnému: n - m + i = 5 - 3 + 3 = 5, skontroluje sa predchádzajúci prvok s i = 2.
Ak je jeho hodnota menšia ako n - m + i, potom sa zvýši o 1 a pre všetky nasledujúce prvky sa hodnota rovná hodnote predchádzajúceho prvku plus 1.
1 (2+1)3 (3+1)4 = 1 3 4
Potom je tu opäť kontrola pre i = 3.
1 3 5
Potom - skontrolujte, či je i = 2.
1 4 5
Potom príde obrat i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
A ďalej,
2 3 5
2 4 5
3 4 5 - posledná kombinácia, pretože všetky jej prvky sa rovnajú n - m + i.

Napriek dôležitej úlohe, ktorú PIN kódy zohrávajú vo svetovej infraštruktúre, neprebehol žiadny akademický výskum o tom, ako si ľudia v skutočnosti vyberajú PIN.

Výskumníci z University of Cambridge Sören Preibusch a Ross Anderson napravili situáciu prvou kvantitatívnou analýzou obtiažnosti uhádnutia 4-miestneho bankového PIN kódu na svete.

Pomocou údajov o únikoch hesiel z nebankových zdrojov a online dotazníkov vedci zistili, že výber PIN kódov je pre používateľov oveľa závažnejší ako výber hesiel pre webové stránky: väčšina kódov obsahuje takmer náhodnú množinu čísel. Medzi počiatočnými údajmi sú však jednoduché kombinácie aj narodeniny - to znamená, že s trochou šťastia môže útočník jednoducho uhádnuť požadovaný kód.

Východiskovým bodom výskumu bol súbor 4-ciferných sekvencií v heslách z databázy RockYou (1,7 milióna) a databáza 200-tisíc PIN kódov z programu uzamknutia obrazovky iPhone (databázu poskytol vývojár aplikácie Daniel Amitay). Na základe týchto údajov sa v grafoch objavujú zaujímavé vzory – dátumy, roky, opakujúce sa čísla a dokonca aj PIN kódy končiace na 69. Na základe týchto pozorovaní vedci vytvorili lineárny regresný model, ktorý odhaduje popularitu každého PIN kódu v závislosti od 25 faktorov, napríklad či je kód dátumom DDMM, či ide o vzostupnú postupnosť atď. Tieto všeobecné podmienky spĺňa 79 % a 93 % PIN kódov v každej zo súprav.

Používatelia si teda vyberajú 4-miestne kódy na základe niekoľkých jednoduchých faktorov. Ak by boli bankové PIN-kódy zvolené týmto spôsobom, 8-9% z nich by sa dalo uhádnuť len na tri pokusy! Ľudia sú však, samozrejme, oveľa pozornejší voči kódom bánk. Vzhľadom na to, že neexistuje žiadny veľký súbor skutočných bankových údajov, výskumníci vypočuli viac ako 1 300 ľudí, aby posúdili, ako sa skutočné PIN kódy líšia od tých, ktoré už boli preskúmané. S prihliadnutím na špecifiká štúdie neboli respondenti požiadaní o samotné kódy, ale iba o ich zhodu s ktorýmkoľvek z vyššie uvedených faktorov (zvýšenie, formát DDMM atď.).

Ukázalo sa, že ľudia sú pri výbere bankových PIN kódov skutočne oveľa opatrnejší. Približne štvrtina opýtaných používa náhodný PIN vygenerovaný bankou. Viac ako tretina si vyberá svoj PIN pomocou starého telefónneho čísla, študentského identifikačného čísla alebo inej sady čísel, ktorá vyzerá náhodne. Podľa získaných výsledkov používa pseudonáhodný PIN kód 64 % držiteľov kariet, čo je oveľa viac ako 23 – 27 % v predchádzajúcich experimentoch s nebankovými kódmi. Ďalších 5 % používa číselný vzor (napríklad 4545) a 9 % uprednostňuje vzor klávesnice (napríklad 2684). Vo všeobecnosti platí, že útočník so šiestimi pokusmi (tri s bankomatom a tri s platobným terminálom) má menej ako 2% šancu uhádnuť PIN cudzej karty.

Faktor	Príklad	RockYou	iPhone	Prieskum
Termíny
DDMM	2311	5.26	1.38	3.07
DMRR	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
MMYY	0683	0.67	0.20	0.94
YYYY	1984	33.39	7.12	4.95
Celkom		58.57	24.51	22.76
Vzor klávesnice
priľahlé	6351	1.52	4.99	-
námestie	1425	0.01	0.58	-
rohy	9713	0.19	1.06	-
kríž	8246	0.17	0.88	-
diagonálna čiara	1590	0.10	1.36	-
horizontálna čiara	5987	0.34	1.42	-
slovo	5683	0.70	8.39	-
vertikálna čiara	8520	0.06	4.28	-
Celkom		3.09	22.97	8.96
Digitálny vzor
končí o 69	6869	0.35	0.57	-
iba čísla 0-3	2000	3.49	2.72	-
iba čísla 0-6	5155	4.66	5.96	-
opakujúce sa dvojice	2525	2.31	4.11	-
rovnaké čísla	6666	0.40	6.67	-
zostupná postupnosť	3210	0.13	0.29	-
zvyšujúca sa postupnosť	4567	3.83	4.52	-
Celkom		15.16	24.85	4.60
Náhodná množina čísel		23.17	27.67	63.68

Všetko by bolo v poriadku, ale, žiaľ, značná časť opýtaných (23 %) volí PIN-kód v podobe dátumu a takmer tretina z nich používa dátum narodenia. To je veľký rozdiel, keďže takmer všetci (99 %) opýtaní odpovedali, že rôzne preukazy totožnosti s týmto dátumom uchovávajú v peňaženkách s bankovými kartami. Ak útočník pozná dátum narodenia držiteľa karty, potom pri správnom prístupe pravdepodobnosť uhádnutia PIN stúpa až na 9 %.

100 najpopulárnejších PIN kódov

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-1103, 1110-1112, 1123, 1201-1203, 1210-1212, 1234, 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

P.S. V praxi je, samozrejme, pre útočníka oveľa jednoduchšie špehovať váš PIN, ako ho uhádnuť. Ale môžete sa tiež chrániť pred nahliadnutím - dokonca, zdá sa, v beznádejnej situácii: