Barátok! Mivel már megvan ez a halott jegyzetfüzetem, egy olyan problémát szeretnék vele feltenni, amellyel tegnap három fizikus, két közgazdász, egy a Műszaki és egy bölcsész szakos küzdött. Az egész agyunkat összetörtük, és folyamatosan különböző eredményeket kapunk. Talán vannak köztetek programozók és matematikai zsenik, ráadásul a probléma általában iskolai és nagyon könnyű, csak nincs képletünk. Mert feladtuk az egzakt tudományokat, helyette valamiért könyveket írunk és képeket rajzolunk. Sajnálom.

Szóval háttértörténet.

Kaptam egy új bankkártyát, és szokásomhoz híven könnyedén kitaláltam a pin kódját. De nem sorban. Mondjuk a pin kód 8794 volt, én pedig a 9748-at hívtam. Vagyis diadalmasan kitalálta az összes számot a megadott négyjegyű szám tartalmazza. Nos, igen, nem csak egy szám, de csak alkatrészei at tűnődött. De a számok mind igazak! MEGJEGYZÉS - Véletlenszerűen cselekedtem, vagyis nem kellett a már ismert számokat a megfelelő sorrendbe raknom, csak a szellemben cselekedtem: itt van négy számomra ismeretlen szám, és úgy gondolom, hogy köztük lehet 9, 7, 4 és 8 lehet, és ezek sorrendje nem fontos. Rögtön kérdeztük magunktól Hány lehetőségem volt(valószínűleg azért, hogy megértsem, milyen klassz, hogy átvettem és kitaláltam). Vagyis hány négy szám kombináció közül kellett választanom? Aztán persze elkezdődött a pokol. Egész este szétrobbant a fejünk, és ennek hatására mindenki egészen más válaszokkal állt elő! El is kezdtem ezeket a kombinációkat sorban írni egy füzetbe, ahogy nőttek, de négyszáznál rájöttem, hogy több mint négyszáz van belőlük (mindenesetre ez cáfolta Thrash fizikus válaszát, aki biztosított róla, hogy négyszáz kombináció volt, de még mindig nem egészen világos) – és feladta.

Megeshet, hogy még egy szuperszám is bekerül a játékba, de nem muszáj. A szavak permutációja vagy kombinációja között főként abban van a különbség, hogy milyen sorrendben helyezzük el a halmazt alkotó elemeket. Ha nem számít, hogy a halmaz elemei milyen sorrendben helyezkednek el, akkor azt mondjuk, hogy kombinációról van szó.

Banán - eper - alma ill. Ha egy halmaz elemeinek sorrendje számít, akkor azt mondjuk, hogy ez egy permutáció. Például ha a széfkulcsot használjuk. Lehetetlen, hogy kinyitható legyen, ha használjuk. Permutációk, amelyekben a halmaz elemei megismétlődhetnek.

Tulajdonképpen, a kérdés lényege. Mennyi a valószínűsége annak, hogy kitaláljuk (bármilyen sorrendben) egy négyjegyű számban található négy számot?

Illetve nem, fogalmazzuk újra (humanista vagyok, bocsánat, bár mindig is volt egy hatalmas gyengeségem a matematikához), hogy egyre világosabb legyen. Hogyan nem ismétlődő 0-tól 9999-ig tartó sorszám-sorozatban található számkombinációk? ( kérjük, ne keverje össze ezt a "hány kombinációt" kérdéssel nem ismétlődő számok"!!! a számok ismételhetők! Úgy értem, 2233 és 3322 ebben az esetben ugyanaz a kombináció!!).

A biztonsági példában a kulcs lehet 8 8 8. Ha tudni akarjuk, hogy ismétléssel hány permutációt érhetünk el, hogy a kulcsot a széfbe helyezzük, akkor figyelembe kell venni, hogy az egyes pozíciókban hány elem helyezhető el. . Ez azt jelenti, hogy a 10 szám közül bármelyiket elhelyezhetjük az első helyre, a 10 szám közül bármelyiket a másodikba, és a 10 szám közül bármelyiket a harmadikba, így van.

Az első helyre 10 szám közül bármelyiket tehetjük 0-tól. A második pozícióhoz tetszőleges számot tehetünk, kivéve azt, amelyik az első pozícióba került, azaz a fennmaradó 9 szám bármelyikét. A kombinációs rendelés módjának meghatározása.

Vagy pontosabban. Tízből négyszer egy számot kell kitalálnom. De nem sorban.

Nos, vagy valami más. Általában azt kell kideríteni, hogy hány lehetőségem volt a számkombinációra, amely a kártya PIN kódját képezte. Segítsetek, jó emberek! Csak kérem, segítsen, ne kezdje el azonnal azt írni, hogy ezekre 9999 lehetőség van(tegnap mindenkinek ez jutott elsőre) mert ez nonszensz – elvégre abban a perspektívában, ami aggaszt bennünket, az 1234-es, a 3421-es, a 4312-es és így tovább egy és ugyanaz! Hát igen, a számok megismételhetők, mert ott van egy pin kód 1111 vagy ott pl 0007. Elképzelhetsz egy autószámot a pin kód helyett. Tegyük fel, mekkora a valószínűsége annak, hogy kitaláljuk az összes egyjegyű számjegyet, amelyek az autó számát alkotják? Vagy a valószínűségelmélet teljes kiküszöböléséhez - hány numerikus kombináció közül kellett egyet választanom?

Meghatározzuk, hogy egy r elemből álló csoportot hányféleképpen rendezhetünk. Végül a következő képletet alkalmazzuk. 8 főből kell egy öttagú bizottságot létrehozni. Hány különböző lehetőség van egy bizottság felállítására? Ez egy kombináció, mert a bizottsági tagok sorrendje nem számít.

Az 1. pozíció a 8 bizottsági tag közül bármelyik lehet. Mivel a bizottság bármely tagja egyszerre csak egy pozícióban lehet, a másik 7 tag közül bármelyik kerülhet a második helyre. A harmadik pozíció csak a fennmaradó 6 tag egyikétől származhat, és így tovább.

Kérem, támassza alá válaszait és érvelését pontos képletekkel, mert tegnap majdnem elvesztettük az eszünket. Előre is nagyon köszönöm mindenkinek!

P.S. Egy okos ember, egy programozó, egy művész és egy feltaláló, nagyon helyesen javasolta a problémákat, így néhány percnyi jó hangulatban voltam: a probléma megoldása a következő: rögeszmés-kényszeres betegsége van, a kezelés a következő: férjhez menni és paradicsomot pucolni. Ha én lennék az ő helyében, nem a „mi a valószínűsége” kérdéssel foglalkoznék jobban, hanem a „kibaszottul odafigyelek ezekre a számokra”?Általában nincs mit hozzáfűzni :)

Meghatározzuk, hogy a bizottság csak 5 tagból áll majd, meghatározzuk, hogy hányféleképpen rendelhetünk 5 elemből álló csoportot. Mivel a bizottság 5 tagból áll, 8 akik ebben a bizottságban szerepelhetnek, muszáj. 8-5 = 3 és kiszámoltuk, hogy ez a 3 megmaradt tag hogyan rendelhető.

Végül alkalmazzuk a képletet. Kérdés: Hányféleképpen rendelhet 16 biliárdlabdát? Ne feledje, hogy minden labda elfoglalhat egy pozíciót, például ha egy 14-es labda jelenik meg az első pozícióban, ez a labda többé nem foglalhat el egy másik pozíciót.

A jelentés forrása nem is lehetne megbízhatóbb. Az iskolai portfólióban négy különböző tantárgyból álló könyvet találunk tetőtől talpig pontos sorrend. portugál, matematika, történelem és földrajz. A jelenlegi sorrendet figyelembe véve hány ilyen könyv gyűjthető össze ebben a pénztárcában?

Az alábbi számológépet úgy tervezték, hogy n x m elemből álló összes kombinációt generáljon.
Az ilyen kombinációk száma az Elements of Combinatorics kalkulátor segítségével számítható ki. Permutációk, elhelyezések, kombinációk.

A generáló algoritmus leírása a számológép alatt.

Algoritmus

A kombinációk lexikográfiai sorrendben jönnek létre. Az algoritmus a halmaz elemeinek ordinális indexeivel dolgozik.
Tekintsük az algoritmust egy példán keresztül.
A bemutatás megkönnyítése érdekében vegyünk egy öt elemből álló halmazt, amelyek indexei 1-gyel kezdődnek, nevezetesen 1 2 3 4 5.
Minden m = 3 méretű kombinációt elő kell állítani.
Először a megadott m méret első kombinációja inicializálódik - indexek növekvő sorrendben
1 2 3
Ezután az utolsó elemet ellenőrizzük, azaz i = 3. Ha értéke kisebb, mint n - m + i, akkor 1-gyel növeljük.
1 2 4
Az utolsó elemet ismét ellenőrzi, és ismét növeli.
1 2 5
Most az elem értéke egyenlő a lehetséges maximális értékkel: n - m + i = 5 - 3 + 3 = 5, az előző i = 2 elemet ellenőrizzük.
Ha értéke kisebb, mint n - m + i, akkor 1-gyel növekszik, és minden utána következő elemnél az érték megegyezik az előző elem értékével plusz 1-gyel.
1 (2+1)3 (3+1)4 = 1 3 4
Ezután ismét ellenőrizzük, hogy i = 3.
1 3 5
Ezután ellenőrizze, hogy i = 2.
1 4 5
Ezután jön az i = 1 fordulat.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
És tovább,
2 3 5
2 4 5
3 4 5 - az utolsó kombináció, mivel minden eleme egyenlő n - m + i.

Gondolkodjunk el ezen a problémán. A portfólióba kerülő első könyv kiválasztásánál 4 lehetőségünk van, mert még nem helyeztünk el könyvet, négy könyv közül választhatunk: Portugál, Matematika, Történelem és Földrajz.

Ha egy portugál könyvvel kezdjük a gyűjtést, akkor a következő könyv kiválasztásánál 3 lehetőségünk van: matematika, történelem és földrajz. Ha a történelemkönyvet választjuk ki a kupac második könyveként, a harmadik könyv számára már csak két lehetőségünk van: a matematika és a földrajz.

A kombinatorika a matematikának egy olyan ága, amely azt a kérdést vizsgálja, hogy adott objektumokból bizonyos feltételek mellett hány különböző kombináció készíthető. A kombinatorika alapjai nagyon fontosak a véletlenszerű események valószínűségének becsléséhez, mert lehetővé teszik az alapvetően lehetséges szám kiszámítását különféle lehetőségeket események fejlesztése.

Alapvető kombinatorikai képlet

Legyen k elemcsoport, és i-edik csoport n i elemből áll. Minden csoportból válasszunk egy elemet. Ekkor az N=n 1 *n 2 *n 3 *...*n k összefüggés határozza meg, hogy egy ilyen választási módot összesen N hány módon lehet meghozni.

1. példa Magyarázzuk meg ezt a szabályt egy egyszerű példával. Legyen két elemcsoport, az első csoport n 1 elemből áll, a második pedig n 2 elemből áll. Hány különböző elempár készíthető ebből a két csoportból úgy, hogy a pár minden csoportból egy elemet tartalmazzon? Tegyük fel, hogy az első csoportból vettük az első elemet, és anélkül, hogy megváltoztattuk volna, végigmentünk minden lehetséges páron, és csak a második csoport elemeit változtattuk meg. Ehhez az elemhez n 2 ilyen pár tartozik. Ezután az első csoportból vesszük a második elemet, és készítsünk hozzá minden lehetséges párt. Lesz n 2 ilyen pár is. Mivel az első csoportban csak n 1 elem van, ezért n 1 *n 2 lehetőség lesz.

2. példa Hány háromjegyű páros szám készíthető a 0, 1, 2, 3, 4, 5, 6 számjegyekből, ha a számjegyek ismételhetők?
Megoldás: n 1 \u003d 6 (mivel az 1, 2, 3, 4, 5, 6 bármelyik számjegyét veheti első számjegynek), n 2 \u003d 7 (mivel a 0-tól bármely számjegyet felveheti második számjegyként, 1 , 2, 3, 4, 5, 6), n 3 \u003d 4 (mivel a 0, 2, 4, 6 bármelyik számjegyét felveheti harmadik számjegyként).
Tehát N=n 1 *n 2 *n 3 =6*7*4=168.

Abban az esetben, ha minden csoport ugyanannyi elemből áll, pl. n 1 =n 2 =...n k =n feltételezhetjük, hogy minden választás ugyanabból a csoportból történik, és az elem a választás után visszatér a csoportba. Ekkor az összes választási mód száma egyenlő n k -vel. Ezt a választási módot a kombinatorikában ún mintákat visszaküldeni.

3. példa Hány négyjegyű szám készíthető az 1, 5, 6, 7, 8 számokból?
Megoldás. Egy négyjegyű szám minden számjegyére öt lehetőség van, tehát N=5*5*5*5=5 4 =625.

Tekintsünk egy n elemből álló halmazt. Ezt a halmazt a kombinatorikában ún Általános népesség.

Elhelyezések száma n elemből m-re

1. definíció. Szállás tól n elemek által m a kombinatorikában bármely megrendelt készlet tól től m az általános lakosságból kiválasztott különféle elemek n elemeket.

4. példa Három elem (1, 2, 3) különböző elrendezései kettesével (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) lesznek halmazok. , 2). Az elhelyezések eltérhetnek egymástól mind elemekben, mind sorrendjükben.

A kombinatorikákban az elhelyezések számát A n m jelöli, és a következő képlettel számítjuk ki:

Megjegyzés: n!=1*2*3*...*n (értsd: "en faktoriális"), ráadásul feltételezzük, hogy 0!=1.

5. példa. Hány olyan kétjegyű szám van, amelyben a tízes számjegy és az egységszámjegy különböző és páratlan?
Megoldás: mert öt páratlan számjegy van, nevezetesen 1, 3, 5, 7, 9, akkor ez a probléma az öt különböző számjegy közül kettő kiválasztására és két különböző pozícióba helyezésére redukálódik, azaz. a megadott számok a következők lesznek:

Definíció 2. Kombináció tól től n elemek által m a kombinatorikában bármely rendezetlen készlet tól től m az általános lakosságból kiválasztott különféle elemek n elemeket.

6. példa. Az (1, 2, 3) halmazhoz a kombinációk: (1, 2), (1, 3), (2, 3).

n elem kombinációinak száma m-rel

A kombinációk számát C n m jelöli, és a következő képlettel számítjuk ki:

7. példa Hányféleképpen választhat ki az olvasó a hat könyv közül kettőt?

Megoldás: Az utak száma megegyezik hat könyv kombinációinak számával kettővel, azaz. egyenlő:

n elem permutációi

Definíció 3. Permutáció tól től n elemeket tetszőlegesnek nevezzük megrendelt készlet ezeket az elemeket.

7a. példa. A három elemből (1, 2, 3) álló halmaz összes lehetséges permutációja: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

Az n elem különböző permutációinak számát P n jelöljük, és a P n =n! képlettel számítjuk ki.

8. példa Hányféleképpen lehet egy polcon egymás után hét könyvet elhelyezni különböző szerzőktől?

Megoldás: ez a probléma hét különböző könyv permutációinak számáról szól. P 7 =7!=1*2*3*4*5*6*7=5040 módja van a könyvek elrendezésének.

Vita. Azt látjuk, hogy a lehetséges kombinációk számát különböző szabályok szerint (permutációk, kombinációk, elhelyezések) lehet kiszámítani, és az eredmény más lesz, mert a számolás elve és maguk a képletek különböznek. Ha közelebbről megvizsgáljuk a definíciókat, láthatjuk, hogy az eredmény egyszerre több tényezőtől is függ.

Először is, hány elemből tudjuk kombinálni a halmazukat (mekkora az általános elemsokaság).

Másodszor, az eredmény attól függ, hogy milyen méretű elemkészletekre van szükségünk.

Végül fontos tudni, hogy a halmazban az elemek sorrendje jelentős-e számunkra. Magyarázzuk meg az utolsó tényezőt a következő példával.

9. példa A szülői értekezleten 20 fő vesz részt. Hány különböző lehetőség van a szülői bizottság összetételére, ha 5 főből kell állnia?
Megoldás: Ebben a példában nem vagyunk kíváncsiak a bizottsági listán szereplő nevek sorrendjére. Ha ennek eredményeként ugyanazok az emberek jelennek meg az összetételében, akkor számunkra ez ugyanaz a lehetőség. Ezért használhatjuk a képletet a szám kiszámításához kombinációk 20 elemből 5.

A helyzet más lesz, ha a bizottság minden tagja kezdetben egy bizonyos munkaterületért felelős. Akkor a bizottság azonos bérszámfejtésével 5 is lehetséges benne! lehetőségek permutációk az számít. A különböző (összetételben és felelősségi körben egyaránt) lehetőségek számát ebben az esetben a szám határozza meg. elhelyezések 20 elemből 5.

Önellenőrzési feladatok
1. Hány háromjegyű páros szám készíthető a 0, 1, 2, 3, 4, 5, 6 számokból, ha a számok ismételhetők?

2. Hány olyan ötjegyű szám van, amely ugyanúgy olvasható balról jobbra és jobbról balra?

3. Tíz tantárgy van az osztályban és napi öt óra. Hányféleképpen lehet beosztani egy napra?

4. Hányféleképpen lehet 4 küldöttet kiválasztani a konferenciára, ha 20 fő van a csoportban?

5. Hányféleképpen helyezhető nyolc különböző levél nyolc különböző borítékba, ha minden borítékba csak egy betű van?

6. Három matematikusból és tíz közgazdászból két matematikusból és hat közgazdászból álló bizottságot kell készíteni. Hányféleképpen lehet ezt megtenni?

Barátok! Mivel már megvan ez a halott jegyzetfüzetem, egy olyan problémát szeretnék vele feltenni, amellyel tegnap három fizikus, két közgazdász, egy a Műszaki és egy bölcsész szakos küzdött. Az egész agyunkat összetörtük, és folyamatosan különböző eredményeket kapunk. Talán vannak köztetek programozók és matematikai zsenik, ráadásul a probléma általában iskolai és nagyon könnyű, csak nincs képletünk. Mert feladtuk az egzakt tudományokat, helyette valamiért könyveket írunk és képeket rajzolunk. Sajnálom.

Szóval háttértörténet.

Kaptam egy új bankkártyát, és szokásomhoz híven könnyedén kitaláltam a pin kódját. De nem sorban. Mondjuk a pin kód 8794 volt, én pedig a 9748-at hívtam. Vagyis diadalmasan kitalálta az összes számot a megadott négyjegyű szám tartalmazza. Nos, igen, nem csak egy szám, de csak alkatrészei at tűnődött. De a számok mind igazak! MEGJEGYZÉS - Véletlenszerűen cselekedtem, vagyis nem kellett a már ismert számokat a megfelelő sorrendbe raknom, csak a szellemben cselekedtem: itt van négy számomra ismeretlen szám, és úgy gondolom, hogy köztük lehet 9, 7, 4 és 8 lehet, és ezek sorrendje nem fontos. Rögtön kérdeztük magunktól Hány lehetőségem volt(valószínűleg azért, hogy megértsem, milyen klassz, hogy átvettem és kitaláltam). Vagyis hány négy szám kombináció közül kellett választanom? Aztán persze elkezdődött a pokol. Egész este szétrobbant a fejünk, és a végén mindenki abszolút kijött különböző változatok válasz! El is kezdtem ezeket a kombinációkat sorban írni egy füzetbe, ahogy nőttek, de négyszáznál rájöttem, hogy több mint négyszáz van belőlük (mindenesetre ez cáfolta Thrash fizikus válaszát, aki biztosított róla, hogy négyszáz kombináció volt, de még mindig nem egészen világos) – és feladta.

Tulajdonképpen, a kérdés lényege. Mennyi a valószínűsége annak, hogy kitaláljuk (bármilyen sorrendben) egy négyjegyű számban található négy számot?

Illetve nem, fogalmazzuk újra (humanista vagyok, bocsánat, bár mindig is volt egy hatalmas gyengeségem a matematikához), hogy egyre világosabb legyen. Hogyan nem ismétlődő 0-tól 9999-ig tartó sorszám-sorozatban található számkombinációk? ( kérjük, ne keverje össze ezt a "hány kombinációt" kérdéssel nem ismétlődő számok"!!! a számok ismételhetők! Úgy értem, 2233 és 3322 ebben az esetben ugyanaz a kombináció!!).

Vagy pontosabban. Tízből négyszer egy számot kell kitalálnom. De nem sorban.

Nos, vagy valami más. Általában azt kell kideríteni, hogy hány lehetőségem volt a számkombinációra, amely a kártya PIN kódját képezte. Segítsetek, jó emberek! Csak kérem, segítsen, ne kezdje el azonnal azt írni, hogy ezekre 9999 lehetőség van(tegnap mindenkinek ez jutott elsőre) mert ez nonszensz – elvégre abban a perspektívában, ami aggaszt bennünket, az 1234-es, a 3421-es, a 4312-es és így tovább egy és ugyanaz! Hát igen, a számok megismételhetők, mert ott van egy pin kód 1111 vagy ott pl 0007. Elképzelhetsz egy autószámot a pin kód helyett. Tegyük fel, mekkora a valószínűsége annak, hogy kitaláljuk az összes egyjegyű számjegyet, amelyek az autó számát alkotják? Vagy a valószínűségelmélet teljes kiküszöböléséhez - hány numerikus kombináció közül kellett egyet választanom?

Kérem, támassza alá válaszait és érvelését pontos képletekkel, mert tegnap majdnem elvesztettük az eszünket. Előre is nagyon köszönöm mindenkinek!

P.S. Egy okos ember, programozó, művész és feltaláló, nagyon helyesen javasolta a helyes döntés problémákat, adva néhány percnyi jó hangulatot: " a probléma megoldása a következő: rögeszmés-kényszeres betegsége van, a kezelés a következő: férjhez menni és paradicsomot pucolni. Ha én lennék az ő helyében, nem a „mi a valószínűsége” kérdéssel foglalkoznék jobban, hanem a „kibaszottul odafigyelek ezekre a számokra”?Általában nincs mit hozzáfűzni :)

Az alábbi számológépet úgy tervezték, hogy n x m elemből álló összes kombinációt generáljon.
Az ilyen kombinációk száma az Elements of Combinatorics kalkulátor segítségével számítható ki. Permutációk, elhelyezések, kombinációk.

A generáló algoritmus leírása a számológép alatt.

Algoritmus

A kombinációk lexikográfiai sorrendben jönnek létre. Az algoritmus a halmaz elemeinek ordinális indexeivel dolgozik.
Tekintsük az algoritmust egy példán keresztül.
A bemutatás megkönnyítése érdekében vegyünk egy öt elemből álló halmazt, amelyek indexei 1-gyel kezdődnek, nevezetesen 1 2 3 4 5.
Minden m = 3 méretű kombinációt elő kell állítani.
Először a megadott m méret első kombinációja inicializálódik - indexek növekvő sorrendben
1 2 3
Ezután az utolsó elemet ellenőrizzük, azaz i = 3. Ha értéke kisebb, mint n - m + i, akkor 1-gyel növeljük.
1 2 4
Az utolsó elemet ismét ellenőrzi, és ismét növeli.
1 2 5
Most az elem értéke egyenlő a lehetséges maximális értékkel: n - m + i = 5 - 3 + 3 = 5, az előző i = 2 elemet ellenőrizzük.
Ha értéke kisebb, mint n - m + i, akkor 1-gyel növekszik, és minden utána következő elemnél az érték megegyezik az előző elem értékével plusz 1-gyel.
1 (2+1)3 (3+1)4 = 1 3 4
Ezután ismét ellenőrizzük, hogy i = 3.
1 3 5
Ezután ellenőrizze, hogy i = 2.
1 4 5
Ezután jön az i = 1 fordulat.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
És tovább,
2 3 5
2 4 5
3 4 5 - az utolsó kombináció, mivel minden eleme egyenlő n - m + i.

Annak ellenére, hogy a PIN-kódok fontos szerepet játszanak a világ infrastruktúrájában, még nem végeztek tudományos kutatást arról, hogyan választják ki az emberek a PIN-kódokat.

A Cambridge-i Egyetem kutatói, Sören Preibusch és Ross Anderson úgy orvosolták a helyzetet, hogy közzétették a világ első kvantitatív elemzését a 4 számjegyű banki PIN-kód kitalálásának nehézségeiről.

A nem banki forrásokból származó jelszókiszivárogtatásra vonatkozó adatok és online felmérések alapján a kutatók azt találták, hogy a felhasználók sokkal komolyabban veszik a PIN-kódok kiválasztását, mint a weboldalak jelszavainak megválasztását: a legtöbb kód szinte véletlenszerű számkészletet tartalmaz. A kezdeti adatok között azonban vannak olyanok is egyszerű kombinációk, és születésnapok – vagyis némi szerencsével a támadó egyszerűen kitalálja az áhított kódot.

A vizsgálat kiindulópontja a RockYou adatbázisból (1,7 millió) származó 4 számjegyű jelszósorozatból és a zárprogramból származó 200 ezer PIN kódból álló adatbázis volt. iPhone képernyő(Az alapot Daniel Amitay alkalmazásfejlesztő biztosította). Az adatokra épített grafikonok érdekes mintákat mutatnak – dátumokat, éveket, ismétlődő számokat, sőt 69-re végződő PIN-kódokat is. E megfigyelések alapján a tudósok felépítettek egy lineáris regressziós modellt, amely 25 tényező függvényében becsüli meg az egyes PIN-kódok népszerűségét, mint pl. hogy a kód dátum-e DDMM formátumban, növekvő sorrend-e, és így tovább. Ezeknek az általános feltételeknek a PIN kódok 79%-a és 93%-a megfelel az egyes készletekben.

Így a felhasználók néhány egyszerű tényező alapján választanak négyjegyű kódokat. Ha így választanánk ki a banki PIN kódokat, akkor mindössze három próbálkozással 8-9%-uk lenne kitalálható! De persze az emberek sokkal figyelmesebbek a bankkódokra. Valós banki adatok nagy halmazának hiányában a kutatók több mint 1300 embert kérdeztek meg, hogy felmérjék, miben térnek el a valós PIN-kódok a már figyelembe vettektől. Tekintettel a vizsgálat sajátosságaira, a válaszadókat nem magukról a kódokról kérdeztük, hanem csak a fenti tényezők valamelyikének (növekedés, DDMM formátum, stb.) való megfelelésükről.

Kiderült, hogy az emberek valóban sokkal körültekintőbbek a banki PIN-kódok kiválasztásánál. A válaszadók hozzávetőleg negyede használ egy bank által generált véletlenszerű PIN-kódot. Több mint egyharmaduk régi telefonszám, diákigazolvány vagy más véletlenszerű számkészlet segítségével választja ki PIN-kódját. Az eredmények szerint a kártyabirtokosok 64%-a használ ál-véletlen PIN kódot, ami jóval több, mint a korábbi, nem banki kódokkal végzett kísérletek 23-27%-a. További 5% használ számmintát (pl. 4545), 9% pedig a billentyűzetmintát (pl. 2684). Általánosságban elmondható, hogy egy támadó hat próbálkozással (három ATM-mel és három fizetési terminállal) kevesebb mint 2%-os eséllyel találja ki valaki más kártya PIN kódját.

Tényező	Példa	ringat téged	iPhone	Interjú
Dátumok
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
mmé	0683	0.67	0.20	0.94
ÉÉÉÉ	1984	33.39	7.12	4.95
Teljes		58.57	24.51	22.76
Billentyűzet minta
összefüggő	6351	1.52	4.99	-
négyzet	1425	0.01	0.58	-
sarkok	9713	0.19	1.06	-
kereszt	8246	0.17	0.88	-
átlós vonal	1590	0.10	1.36	-
vízszintes vonal	5987	0.34	1.42	-
szó	5683	0.70	8.39	-
függőleges vonal	8520	0.06	4.28	-
Teljes		3.09	22.97	8.96
digitális minta
69-re végződik	6869	0.35	0.57	-
csak a számok 0-3	2000	3.49	2.72	-
csak a számok 0-6	5155	4.66	5.96	-
visszatérő párok	2525	2.31	4.11	-
ugyanazok a számjegyek	6666	0.40	6.67	-
csökkenő sorrendben	3210	0.13	0.29	-
növekvő sorrendben	4567	3.83	4.52	-
Teljes		15.16	24.85	4.60
Véletlen számkészlet		23.17	27.67	63.68

Minden rendben is lenne, de sajnos a válaszadók jelentős része (23%) randevú formájában választ PIN kódot - közel harmaduk pedig a születési dátumát használja. Ez jelentősen változtat a helyzeten, mert szinte minden (99%) válaszadó azt válaszolta, hogy a pénztárcájában tartja bankkártyák különböző személyi igazolványok, amelyekre ez a dátum van nyomtatva. Ha a támadó ismeri a kártyabirtokos születésnapját, akkor hozzáértő megközelítéssel a PIN-kód kitalálásának valószínűsége 9%-ra emelkedik.

A 100 legnépszerűbb PIN-kód

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. A gyakorlatban persze sokkal könnyebb a támadónak kémkedni a PIN-kód után, mint kitalálni. De megvédheti magát a kukucskálástól is - még úgy tűnik, reménytelen helyzetben is:

Mind az N elem, és egyik sem ismétlődik, akkor ez a permutációk számának problémája. A megoldás egyszerűen megtalálható. Az N elem bármelyike ​​elfoglalhatja az első helyet a sorban, így N opciót kapunk. A második helyen - bármely, kivéve azt, amelyet már használtak az első helyen. Ezért a már megtalált N opció mindegyikéhez van (N - 1) második hely opció, és a kombinációk teljes száma N*(N - 1) lesz.
Ugyanez megismételhető a sorozat többi elemére is. A legutolsó helyre már csak egy lehetőség maradt - az utolsó megmaradt elem. Az utolsó előtti - két lehetőség, és így tovább.
Ezért N számú nem ismétlődő elem sorozata esetén a lehetséges permutációk egyenlők az 1-től N-ig terjedő összes egész szám szorzatával. Ezt a szorzatot N faktoriálisának nevezzük, és N-vel jelöljük! (Olvassa el: "en faktorial").

Az előző esetben a lehetséges elemek száma és a helyek száma a sorozatban egybeesett, és számuk egyenlő volt N-vel. De lehetséges az a helyzet, hogy a sorozatban kevesebb hely van, mint amennyi lehetséges elem. Más szóval, a mintában lévő elemek száma megegyezik valamilyen M és M számmal< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Először is szükség lehet a teljes összeg megszámlálására lehetséges módjai, amely N-ből M elem sorozatba rendezhető. Az ilyen módszereket elhelyezéseknek nevezzük.
Másodszor, a kutatót érdekelheti, hogy hány módon választható ki M elem N közül. Ebben az esetben az elemek sorrendje már nem fontos, de bármelyik két lehetőségnek legalább egy elemben el kell térnie egymástól. . Az ilyen módszereket kombinációknak nevezzük.

Ahhoz, hogy megtaláljuk az N-ből M elem elhelyezéseinek számát, ugyanazt az érvelést használhatjuk, mint a permutációk esetében. Az első helyen még mindig lehet N elem, a másodikban (N - 1), és így tovább. De az utolsó helyen a szám lehetőségek nem 1, hanem (N - M + 1), mert az allokáció befejeztével továbbra is marad (N - M) nem használt elem.
Így az M elem feletti elhelyezések száma N-ből egyenlő az (N - M + 1)-től N-ig terjedő összes egész szám szorzatával, vagy ennek megfelelően az N!/(N - M)! hányadosával.

Nyilvánvaló, hogy az N-ből származó M elem kombinációinak száma kevesebb lesz, mint az elhelyezések száma. Minden lehetséges kombinációhoz tartozik egy M! lehetséges elhelyezések e kombináció elemeinek sorrendjétől függően. Ezért ennek a számnak a megtalálásához el kell osztania az N-ből származó M elem feletti elhelyezések számát N-vel!. Más szóval, az N-ből származó M elem kombinációinak száma N!/(M!*(N - M)!).