Найзууд аа! Энэ үхсэн дэвтэр надад байгаа болохоор өчигдөр гурван физикч, хоёр эдийн засагч, нэг Политехникийн нэг, нэг хүмүүнлэгийн ухааны нэг хүний ​​тулгарсан асуудлыг асууж байна. Бид тархиа бүхэлд нь эвдэж, бид байнга өөр үр дүнд хүрдэг. Магадгүй та нарын дунд программистууд, математикийн суутнууд байгаа байх, үүнээс гадна асуудал нь ерөнхийдөө сургуулийнх бөгөөд маш амархан, бидэнд томъёо алга. Яагаад гэвэл нарийн шинжлэх ухааныг орхиод оронд нь яагаад ч юм ном бичиж, зураг зурдаг болсон. Уучлаарай.

Тэгэхээр, арын түүх.

Надад шинэ банкны карт өгсөн бөгөөд би ердийнхөөрөө түүний пин кодыг ямар ч хүчин чармайлтгүйгээр тааварлав. Гэхдээ дараалан биш. Пин код нь 8794 байсан гэж бодъё, би 9748 руу залгасан. Өөрөөр хэлбэл би ялалт байгуулсан. бүх тоог таасанөгөгдсөн дөрвөн оронтой тоонд агуулагдсан. За, тийм ээ, зүгээр нэг тоо биш, гэхдээ энгийнээр түүний бүрэлдэхүүн хэсгүүдгэж гайхсан. Гэхдээ бүх тоо үнэн! ТАЙЛБАР - Би санамсаргүй байдлаар үйлдэл хийсэн, өөрөөр хэлбэл би аль хэдийн мэдэгдэж байсан тоонуудыг зөв дарааллаар оруулах шаардлагагүй, би зүгээр л сүнсээр ажилласан: энд миний мэдэхгүй дөрвөн тоо байгаа бөгөөд тэдний дунд байж магадгүй гэж би итгэж байна. 9, 7, 4, 8 байх ба тэдгээрийн дараалал чухал биш.Бид тэр даруй өөрөөсөө асуув Надад хэдэн сонголт байсан(ямар дажгүй юм бэ гэдгийг ойлгохын тулд аваад тааж байсан байх). Өөрөөр хэлбэл, би дөрвөн тооны хэдэн хослолыг сонгох ёстой байсан бэ? Тэгээд мэдээж там эхэлсэн. Оройн турш бидний толгой дэлбэрч, үүний үр дүнд бүгд өөр өөр хариултыг гаргаж ирэв! Би бүр эдгээр бүх хослолыг дэвтэр дээрээ дараалан бичиж эхэлсэн боловч дөрвөн зуугаар нь дөрвөн зуу гаруй нь байгааг ойлгосон (ямар ч байсан энэ нь физикч Трешийн хариултыг няцаасан. дөрвөн зуун хослол байсан гэж надад хэлсэн, гэхдээ энэ нь тийм ч тодорхой биш байна) - тэгээд бууж өгсөн.

Супер тоо ч гэсэн тоглоомонд орох тохиолдол гарч болох ч ингэх шаардлагагүй. Үгсийн орлуулалт эсвэл хослолын ялгаа нь үндсэндээ олонлогийг бүрдүүлэгч элементүүдийг байрлуулах дарааллаар юм. Хэрэв олонлогийн элементүүдийг байрлуулах дараалал хамаагүй бол бид үүнийг хослол гэж хэлэх болно.

Банана - гүзээлзгэнэ - алим эсвэл. Хэрэв олонлогийн элементүүдийн дараалал чухал бол бид үүнийг солих гэж хэлдэг. Жишээлбэл, хэрэв бид аюулгүй түлхүүрийг ашигладаг бол. Ашиглах юм бол нээх боломжгүй. Олонлогийн элементүүдийг давтахыг зөвшөөрдөг сэлгэлтүүд.

Үнэндээ, асуултын мөн чанар.Дөрвөн оронтой тоонд агуулагдах дөрвөн тоог (ямар ч дарааллаар) таамаглах магадлал хэд вэ?

Үгүй ээ, (би хүмүүнлэг, уучлаарай, математикийн хувьд үргэлж асар их сул талтай байсан ч) үүнийг илүү тодорхой, ойлгомжтой болгохын тулд дахин томъёолъё. Хэрхэн давтагдахгүй 0-ээс 9999 хүртэлх дарааллын тооны цувралд агуулагдах тооны хослолууд? ( Үүнийг "хэчнээн хослолтой вэ" гэсэн асуулттай андуурч болохгүй давтагдахгүйтоо"!!! тоог давтаж болно! Энэ тохиолдолд 2233 ба 3322 нь ижил хослол юм!).

Аюулгүй байдлын жишээн дээр түлхүүр нь 8 8 8 байж болно. Хэрэв бид түлхүүрийг сейфэнд оруулахын тулд хэдэн удаа солигдох боломжтойг мэдэхийг хүсвэл байрлал тус бүрт хэдэн элемент байрлуулж болохыг анхаарч үзэх хэрэгтэй. . Энэ нь бид эхний байрлалд 10 тооны аль нэгийг, хоёрдугаарт 10 тооны аль нэгийг, гуравдугаарт 10 тооны аль нэгийг байрлуулж болно гэсэн үг юм.

Эхний байрлалд бид 0-ээс 10 хүртэлх тооны аль нэгийг тавьж болно. Хоёрдахь байрлалд бид эхний байрлалд байрлуулсан тооноос өөр ямар ч тоог, өөрөөр хэлбэл үлдсэн 9 тооны аль нэгийг тавьж болно. Хэрхэн хослуулан захиалахыг тодорхойлох.

Эсвэл бүр тодруулбал. Би араваас нэг тоог дөрвөн удаа таах хэрэгтэй. Гэхдээ дараалан биш.

За, эсвэл өөр зүйл. Ерөнхийдөө картын пин кодыг бүрдүүлсэн тоон хослолын хэдэн сонголт байгааг олж мэдэх хэрэгтэй. Туслаач, сайн хүмүүс ээ! Зүгээр л туслаарай, эдгээрийн хувьд 9999 сонголт байна гэж шууд бичиж эхлэх хэрэггүй(өчигдөр энэ нь бүгдийн толгойд орж ирсэн) Учир нь энэ бол утгагүй зүйл - эцэст нь бидний санаа зовдог хэтийн төлөвийн хувьд 1234 тоо, 3421 тоо, 4312 тоо гэх мэт. нэг бөгөөд адилхан! За, тийм ээ, тоонууд давтаж болно, учир нь пин код 1111 эсвэл тэнд жишээ нь 0007. Та пин кодын оронд машины дугаарыг төсөөлж болно. Машины дугаарыг бүрдүүлдэг бүх нэг оронтой тоог таах магадлал хэд вэ гэж бодъё? Эсвэл магадлалын онолыг бүрмөсөн устгахын тулд би хэдэн тоон хослолоос нэгийг нь сонгох ёстой байсан бэ?

Бид r элементийн бүлгийг хэдэн аргаар захиалж болохыг тодорхойлдог. Эцэст нь бид дараах томъёог хэрэглэнэ. Таван хүний ​​бүрэлдэхүүнтэй хороо байгуулахад 8 хүн байна. Хороо байгуулах боломж хэр олон байна вэ? Хорооны гишүүдийн дараалал хамаагүй учраас хосолсон хэрэг.

1-р албан тушаал нь хорооны 8 гишүүний аль нэг нь байж болно. Хорооны аль ч гишүүн нэг удаад зөвхөн нэг албан тушаалд ажиллах боломжтой тул бусад 7 гишүүний аль нь ч хоёрдугаар байранд орж болно. Гурав дахь албан тушаал нь зөвхөн үлдсэн 6 гишүүний нэгээс л гарч болно, гэх мэт.

Өчигдөр бид ухаан алдах шахсан тул хариулт, үндэслэлээ тодорхой томъёогоор нөөцөлнө үү. Бүгдэд нь урьдчилж маш их баярлалаа!

P.S. Нэг ухаалаг хүн, программист, зураач, зохион бүтээгч зүгээр л асуудлыг маш зөв санал болгож, надад хэдэн минутын сайхан сэтгэлийг өгсөн: " Асуудлын шийдэл нь энэ юм: тэр хий үзэгдэлтэй-компульсив эмгэгтэй, эмчилгээ нь: гэрлэж, улаан лооль цац. Хэрэв би түүний оронд байсан бол "магадлал хэд вэ" гэсэн асуулт биш, харин "би энэ бүх тоонд анхаарлаа хандуулж байна уу" гэсэн асуултад илүү санаа тавих байсан.Ерөнхийдөө нэмэх зүйл алга :)

Хороо нь зөвхөн 5 гишүүнээс бүрдэх болно гэдгийг бид зааж өгсөн бөгөөд бид 5 элементийн бүлгийг хэдэн аргаар захиалж болохыг тодорхойлдог. Хороо нь энэ хороонд байж болох 5 гишүүнтэй 8 хүнтэй бүрэлдэж байгаа учраас бид заавал байх ёстой. 8-5 = 3 бөгөөд бид үлдсэн 3 гишүүнийг хэрхэн захиалж болохыг тооцоолсон.

Эцэст нь томъёогоо хэрэгжүүлье. Асуулт: Та 16 бильярдын бөмбөгийг хэдэн янзаар захиалж болох вэ? Бөмбөг бүр нэг байрлалд байж болно гэдгийг санаарай, жишээлбэл, эхний байрлалд 14 бөмбөг гарч ирвэл энэ бөмбөг өөр байрлалыг эзлэх боломжгүй болно.

Мэдээллийн эх сурвалж илүү найдвартай байж чадахгүй. Сургуулийн багцад бид дээрээс доошоо овоолсон өөр өөр сэдвээр дөрвөн ном байна яг дараалал. Португал хэл, математик, түүх, газарзүй. Одоогийн дарааллыг оруулаад энэ хэтэвчинд ийм хэдэн ном цуглуулж болох вэ?

Доорх тооцоолуур нь n х m элементийн бүх хослолыг үүсгэх зориулалттай.
Ийм хослолын тоог "Комбинаторикийн элементүүд" тооцоолуур ашиглан тооцоолж болно. Сэлгээ, байршил, хослолууд.

Тооцоологч дор үүсгэх алгоритмын тайлбар.

Алгоритм

Холболтыг үг хэллэгийн дарааллаар үүсгэдэг. Алгоритм нь олонлогийн элементүүдийн дарааллын индексүүдтэй ажилладаг.
Алгоритмыг жишээгээр авч үзье.
Илтгэлд хялбар болгохын тулд индексүүд нь 1-ээр эхэлдэг таван элементийн багцыг авч үзье, тухайлбал 1 2 3 4 5.
m = 3 хэмжээтэй бүх хослолыг үүсгэх шаардлагатай.
Нэгдүгээрт, өгөгдсөн хэмжээтэй m-ийн эхний хослолыг эхлүүлсэн - өсөх дарааллаар индексүүд
1 2 3
Дараа нь сүүлчийн элементийг шалгана, өөрөөр хэлбэл i = 3. Хэрэв түүний утга n - m + i-ээс бага бол 1-ээр нэмэгдэнэ.
1 2 4
Сүүлийн элементийг дахин шалгаж, дахин нэмэгдүүлнэ.
1 2 5
Одоо элементийн утга нь хамгийн их боломжтой тэнцүү байна: n - m + i = 5 - 3 + 3 = 5, i = 2-тай өмнөх элементийг шалгана.
Хэрэв түүний утга нь n - m + i-ээс бага бол 1-ээр нэмэгдэх ба түүнийг дагаж байгаа бүх элементийн хувьд өмнөх элементийн утга 1-тэй тэнцүү байна.
1 (2+1)3 (3+1)4 = 1 3 4
Дараа нь бид i = 3 байгаа эсэхийг дахин шалгана.
1 3 5
Дараа нь - i = 2 байгаа эсэхийг шалгана уу.
1 4 5
Дараа нь i = 1 эргэлт ирнэ.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Мөн цаашлаад,
2 3 5
2 4 5
3 4 5 - сүүлчийн хослол, учир нь түүний бүх элементүүд нь n - m + i-тэй тэнцүү байна.

Энэ асуудлын талаар бодож үзье. Багцад байршуулах эхний номыг сонгохдоо бидэнд 4 боломж байгаа ба үүнд хараахан ном байрлуулаагүй байгаа тул Португал хэл, Математик, Түүх, Газарзүй гэсэн дөрвөн номноос сонгох боломжтой.

Хэрэв бид түүврээ португал номоор эхлүүлбэл түүн дээр байрлуулах дараагийн номоо сонгохдоо математик, түүх, газарзүй гэсэн 3 боломж байна. Хэрэв бид түүхийн номыг овоолгын хоёр дахь номоор сонговол гурав дахь номонд математик, газарзүй гэсэн хоёрхон боломж байна.

Комбинаторик бол өгөгдсөн объектуудаас тодорхой нөхцлийн дагуу хэдэн өөр хослол хийж болох тухай асуултуудыг судалдаг математикийн салбар юм. Комбинаторикийн үндэс нь санамсаргүй тохиолдлын магадлалыг тооцоолоход маш чухал, учир нь Тэд үндсэн боломжит тоог тооцоолох боломжийг бидэнд олгодог янз бүрийн сонголтуудүйл явдлын хөгжил.

Комбинаторикийн үндсэн томъёо

k бүлэг элемент байг, ба i-р бүлэг n i элементээс бүрдэнэ. Бүлэг бүрээс нэг элемент сонгоцгооё. Тэгвэл ийм сонголт хийх боломжтой N аргын нийт тоог N=n 1 *n 2 *n 3 *...*n k хамаарлаар тодорхойлно.

Жишээ 1Энэ дүрмийг энгийн жишээгээр тайлбарлая. Хоёр бүлэг элемент байг, эхний бүлэг нь n 1 элементээс, хоёр дахь нь n 2 элементээс бүрдэнэ. Энэ хоёр бүлгээс хэдэн өөр хос элемент хийж болох бөгөөд энэ хос нь бүлэг тус бүрээс нэг элементийг агуулж болох вэ? Бид эхний бүлгээс эхний элементийг авч, түүнийг өөрчлөхгүйгээр зөвхөн хоёр дахь бүлгийн элементүүдийг өөрчилсөн бүх боломжит хосуудыг дамжууллаа гэж бодъё. Энэ элементийн хувьд ийм хос n 2 байна. Дараа нь бид эхний бүлгээс хоёр дахь элементийг авч, түүнд тохирох бүх хосыг хийнэ. Мөн n 2 ийм хос байх болно. Эхний бүлэгт зөвхөн n 1 элемент байгаа тул n 1 *n 2 боломжит сонголт байх болно.

Жишээ 2 0, 1, 2, 3, 4, 5, 6 гэсэн цифрүүдийг давтаж чадвал гурван оронтой хэдэн тэгш тоо гаргаж болох вэ?
Шийдэл: n 1 \u003d 6 (1, 2, 3, 4, 5, 6-аас ямар ч цифрийг эхний орон болгон авч болно), n 2 \u003d 7 (0-ээс ямар ч цифрийг хоёр дахь цифр болгон авч болно, 1). , 2, 3, 4, 5, 6), n 3 \u003d 4 (учир нь та 0, 2, 4, 6-аас ямар ч цифрийг гурав дахь орон болгон авч болно).
Тэгэхээр N=n 1 *n 2 *n 3 =6*7*4=168.

Бүх бүлгүүд ижил тооны элементүүдээс бүрдэх тохиолдолд, өөрөөр хэлбэл. n 1 =n 2 =...n k =n сонголт бүрийг нэг бүлгээс хийсэн гэж үзэж болох ба элемент нь сонголтын дараа бүлэгт буцаж ирдэг. Дараа нь сонгох бүх аргын тоо n k-тэй тэнцүү байна. Комбинаторикт ийм сонголт хийх аргыг нэрлэдэг дээжийг буцаах.

Жишээ 3 1, 5, 6, 7, 8 тоонуудаас дөрвөн оронтой хэдэн тоо гаргаж болох вэ?
Шийдэл.Дөрвөн оронтой тооны цифр бүрийн таван боломж байгаа тул N=5*5*5*5=5 4 =625.

n элементээс бүрдэх олонлогийг авч үзье. Комбинаторик дахь энэ олонлогийг нэрлэдэг нийт хүн ам.

n элементээс m-ээр байршуулах тоо

Тодорхойлолт 1.-аас байр nэлементүүд мкомбинаторикт дурын гэж нэрлэдэг захиалсан багц-аас мдахь нийт хүн амын дундаас сонгосон янз бүрийн элементүүд nэлементүүд.

Жишээ 4Гурван элементийн (1, 2, 3) хоёр, хоёрын өөр өөр зохицуулалт нь (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) олонлог болно. , 2). Байрлуулалт нь элементүүд болон дарааллаар нь бие биенээсээ ялгаатай байж болно.

Комбинаторик дахь байршлын тоог A n m-ээр тэмдэглэж, дараах томъёогоор тооцоолно.

Сэтгэгдэл: n!=1*2*3*...*n (унш: "en factorial"), үүнээс гадна 0!=1 гэж үздэг.

Жишээ 5. Аравтын орон ба нэгжийн орон нь өөр, сондгой байх хэдэн хоёр оронтой тоо байдаг вэ?
Шийдэл:учир нь 1, 3, 5, 7, 9 гэх мэт таван сондгой цифр байгаа бол энэ асуудал нь таван өөр цифрээс хоёрыг нь сонгож, хоёр өөр байрлалд байрлуулахад хүргэдэг, өөрөөр хэлбэл. өгөгдсөн тоонууд нь:

Тодорхойлолт 2. Хослол-аас nэлементүүд мкомбинаторикт дурын гэж нэрлэдэг захиалгагүй багц-аас мдахь нийт хүн амын дундаас сонгосон янз бүрийн элементүүд nэлементүүд.

Жишээ 6. (1, 2, 3) багцын хувьд (1, 2), (1, 3), (2, 3) хослолууд байна.

n элементийн хослолын тоо m

Хослолын тоог C n m-ээр тэмдэглэж, дараах томъёогоор тооцоолно.

Жишээ 7Уншигч зургаан номноос хоёрыг хэдэн аргаар сонгож болох вэ?

Шийдэл:Аргын тоо нь зургаан номын хослолын тоо хоёроор тэнцүү байна, i.e. тэнцүү байна:

n элементийн сэлгэлт

Тодорхойлолт 3. Пермутаци-аас nэлементүүдийг дурын гэж нэрлэдэг захиалсан багцэдгээр элементүүд.

Жишээ 7a.Гурван элементээс (1, 2, 3) бүрдэх олонлогийн бүх боломжит орлуулалтууд нь: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , ( 3, 2, 1), (3, 1, 2).

n элементийн өөр өөр сэлгэлтийн тоог P n гэж тэмдэглэж P n =n! томъёогоор тооцоолно.

Жишээ 8Өөр өөр зохиолчдын долоон номыг тавиур дээр хэдэн янзаар дараалан байрлуулж болох вэ?

Шийдэл:Энэ асуудал нь долоон өөр номын сэлгэлтийн тооны тухай юм. Номуудыг цэгцлэх P 7 =7!=1*2*3*4*5*6*7=5040 арга бий.

Хэлэлцүүлэг.Боломжит хослолуудын тоог янз бүрийн дүрмийн дагуу (сэлгэн залгалт, хослол, байршил) тооцоолж болох бөгөөд үр дүн нь өөр байх болно гэдгийг бид харж байна, учир нь тоолох зарчим, томъёо нь өөр өөр байдаг. Тодорхойлолтыг анхааралтай ажиглавал үр дүн нь хэд хэдэн хүчин зүйлээс нэгэн зэрэг хамаардаг болохыг харж болно.

Нэгдүгээрт, бид хэдэн элементээс тэдгээрийн багцыг нэгтгэж чадах вэ (элементүүдийн ерөнхий популяци хэр их вэ).

Хоёрдугаарт, үр дүн нь бидэнд ямар хэмжээтэй элемент хэрэгтэй байгаагаас хамаарна.

Эцэст нь багц дахь элементүүдийн дараалал нь бидний хувьд чухал ач холбогдолтой эсэхийг мэдэх нь чухал юм. Сүүлийн хүчин зүйлийг дараах жишээгээр тайлбарлая.

Жишээ 9Эцэг эхийн хуралд 20 хүн оролцож байна. Эцэг эхийн хорооны бүрэлдэхүүнд 5 хүний ​​бүрэлдэхүүнтэй байхаар бол хэдэн өөр хувилбар байгаа вэ?
Шийдэл:Энэ жишээнд бид хорооны жагсаалтад байгаа нэрсийн дарааллыг сонирхохгүй байна. Үүний үр дүнд түүний найрлагад ижил хүмүүс гарч ирвэл бидний хувьд энэ нь ижил сонголт юм. Тиймээс бид тоог тооцоолохдоо томъёог ашиглаж болно хослолууд 20 элементээс 5.

Хорооны гишүүн бүр ажлын тодорхой чиглэлийг хариуцдаг бол бүх зүйл өөр байх болно. Дараа нь хорооны ижил цалинтай, дотор нь 5 боломжтой! сонголтууд орлуулалттэр асуудал. Өөр өөр сонголтуудын тоог (бүрэлдэхүүн болон хариуцлагын хүрээний хувьд) энэ тохиолдолд тоогоор тодорхойлно. байршуулалт 20 элементээс 5.

Өөрийгөө шалгах даалгавар
1. 0, 1, 2, 3, 4, 5, 6 гэсэн тоонуудыг давтаж чадвал гурван оронтой хэдэн тэгш тоо гаргаж болох вэ?

2. Зүүнээс баруун тийш, баруунаас зүүн тийш ижил уншдаг таван оронтой тоо хэд вэ?

3. Ангид арван хичээл, өдөрт таван хичээл ордог. Та нэг өдрийн хуваарийг хэдэн аргаар гаргаж болох вэ?

4. Бүлэгт 20 хүн байвал бага хуралд 4 төлөөлөгчийг хэдэн янзаар сонгож болох вэ?

5. Дугтуй бүрд ганцхан үсэг хийвэл найман өөр үсгийг найман өөр дугтуйнд хэдэн янзаар хийж болох вэ?

6. Гурван математикч, арван эдийн засагчаас хоёр математикч, зургаан эдийн засагчаас бүрдсэн комисс гаргах шаардлагатай. Үүнийг хэдэн аргаар хийж болох вэ?

Найзууд аа! Энэ үхсэн дэвтэр надад байгаа болохоор өчигдөр гурван физикч, хоёр эдийн засагч, нэг Политехникийн нэг, нэг хүмүүнлэгийн ухааны нэг хүний ​​тулгарсан асуудлыг асууж байна. Бид тархиа бүхэлд нь эвдэж, бид байнга өөр үр дүнд хүрдэг. Магадгүй та нарын дунд программистууд, математикийн суутнууд байгаа байх, үүнээс гадна асуудал нь ерөнхийдөө сургуулийнх бөгөөд маш амархан, бидэнд томъёо алга. Яагаад гэвэл нарийн шинжлэх ухааныг орхиод оронд нь яагаад ч юм ном бичиж, зураг зурдаг болсон. Уучлаарай.

Тэгэхээр, арын түүх.

Надад шинэ банкны карт өгсөн бөгөөд би ердийнхөөрөө түүний пин кодыг ямар ч хүчин чармайлтгүйгээр тааварлав. Гэхдээ дараалан биш. Пин код нь 8794 байсан гэж бодъё, би 9748 руу залгасан. Өөрөөр хэлбэл би ялалт байгуулсан. бүх тоог таасанөгөгдсөн дөрвөн оронтой тоонд агуулагдсан. За, тийм ээ, зүгээр нэг тоо биш, гэхдээ энгийнээр түүний бүрэлдэхүүн хэсгүүдгэж гайхсан. Гэхдээ бүх тоо үнэн! ТАЙЛБАР - Би санамсаргүй байдлаар үйлдэл хийсэн, өөрөөр хэлбэл би аль хэдийн мэдэгдэж байсан тоонуудыг зөв дарааллаар нь оруулах шаардлагагүй, би зүгээр л сүнсээр ажилласан: энд миний мэдэхгүй дөрвөн тоо байгаа бөгөөд тэдний дунд байж магадгүй гэж би итгэж байна. 9, 7, 4, 8, тэдгээрийн дараалал нь чухал биш юм.Бид тэр даруй өөрөөсөө асуув Надад хэдэн сонголт байсан(ямар дажгүй юм бэ гэдгийг ойлгохын тулд аваад тааж байсан байх). Өөрөөр хэлбэл, би дөрвөн тооны хэдэн хослолыг сонгох ёстой байсан бэ? Тэгээд мэдээж там эхэлсэн. Оройн турш бидний толгой дэлбэрч, эцэст нь бүгд туйлын гарч ирэв янз бүрийн хувилбаруудхариул! Би бүр эдгээр бүх хослолыг дэвтэр дээрээ дараалан бичиж эхэлсэн боловч дөрвөн зуугаар нь дөрвөн зуу гаруй нь байгааг ойлгосон (ямар ч байсан энэ нь физикч Трешийн хариултыг няцаасан. дөрвөн зуун хослол байсан гэж надад хэлсэн, гэхдээ энэ нь тийм ч тодорхой биш байна) - тэгээд бууж өгсөн.

Үнэндээ, асуултын мөн чанар.Дөрвөн оронтой тоонд агуулагдах дөрвөн тоог (ямар ч дарааллаар) таамаглах магадлал хэд вэ?

Үгүй ээ, (би хүмүүнлэг, уучлаарай, математикийн хувьд үргэлж асар их сул талтай байсан ч) үүнийг илүү тодорхой, ойлгомжтой болгохын тулд дахин томъёолъё. Хэрхэн давтагдахгүй 0-ээс 9999 хүртэлх дарааллын тооны цувралд агуулагдах тооны хослолууд? ( Үүнийг "хэчнээн хослолтой вэ" гэсэн асуулттай андуурч болохгүй давтагдахгүйтоо"!!! тоог давтаж болно! Энэ тохиолдолд 2233 ба 3322 нь ижил хослол юм!).

Эсвэл бүр тодруулбал. Би араваас нэг тоог дөрвөн удаа таах хэрэгтэй. Гэхдээ дараалан биш.

За, эсвэл өөр зүйл. Ерөнхийдөө картын пин кодыг бүрдүүлсэн тоон хослолын хэдэн сонголт байгааг олж мэдэх хэрэгтэй. Туслаач, сайн хүмүүс ээ! Зүгээр л туслаарай, эдгээрийн хувьд 9999 сонголт байна гэж шууд бичиж эхлэх хэрэггүй(өчигдөр энэ нь бүгдийн толгойд орж ирсэн) Учир нь энэ бол утгагүй зүйл - эцэст нь бидний санаа зовдог хэтийн төлөвийн хувьд 1234 тоо, 3421 тоо, 4312 тоо гэх мэт. нэг бөгөөд адилхан! За, тийм ээ, тоонууд давтаж болно, учир нь пин код 1111 эсвэл тэнд жишээ нь 0007. Та пин кодын оронд машины дугаарыг төсөөлж болно. Машины дугаарыг бүрдүүлдэг бүх нэг оронтой тоог таах магадлал хэд вэ гэж бодъё? Эсвэл магадлалын онолыг бүрмөсөн устгахын тулд би хэдэн тоон хослолоос нэгийг нь сонгох ёстой байсан бэ?

Өчигдөр бид ухаан алдах шахсан тул хариулт, үндэслэлээ тодорхой томъёогоор нөөцөлнө үү. Бүгдэд нь урьдчилж маш их баярлалаа!

P.S. Нэг ухаалаг хүн, програмист, зураач, зохион бүтээгч маш зөв санал болгов зөв шийдвэрАсуудал, надад хэдэн минут сайхан сэтгэлийг өгч байна: " Асуудлын шийдэл нь энэ юм: тэр хий үзэгдэлтэй-компульсив эмгэгтэй, эмчилгээ нь: гэрлэж, улаан лооль цац. Хэрэв би түүний оронд байсан бол "магадлал хэд вэ" гэсэн асуулт биш, харин "би энэ бүх тоонд анхаарлаа хандуулж байна уу" гэсэн асуултад илүү санаа тавих байсан.Ерөнхийдөө нэмэх зүйл алга :)

Доорх тооцоолуур нь n х m элементийн бүх хослолыг үүсгэх зориулалттай.
Ийм хослолын тоог "Комбинаторикийн элементүүд" тооцоолуур ашиглан тооцоолж болно. Сэлгээ, байршил, хослолууд.

Тооцоологч дор үүсгэх алгоритмын тайлбар.

Алгоритм

Холболтыг үг хэллэгийн дарааллаар үүсгэдэг. Алгоритм нь олонлогийн элементүүдийн дарааллын индексүүдтэй ажилладаг.
Алгоритмыг жишээгээр авч үзье.
Илтгэлд хялбар болгохын тулд индексүүд нь 1-ээр эхэлдэг таван элементийн багцыг авч үзье, тухайлбал 1 2 3 4 5.
m = 3 хэмжээтэй бүх хослолыг үүсгэх шаардлагатай.
Нэгдүгээрт, өгөгдсөн хэмжээтэй m-ийн эхний хослолыг эхлүүлсэн - өсөх дарааллаар индексүүд
1 2 3
Дараа нь сүүлчийн элементийг шалгана, өөрөөр хэлбэл i = 3. Хэрэв түүний утга n - m + i-ээс бага бол 1-ээр нэмэгдэнэ.
1 2 4
Сүүлийн элементийг дахин шалгаж, дахин нэмэгдүүлнэ.
1 2 5
Одоо элементийн утга нь хамгийн их боломжтой тэнцүү байна: n - m + i = 5 - 3 + 3 = 5, i = 2-тай өмнөх элементийг шалгана.
Хэрэв түүний утга нь n - m + i-ээс бага бол 1-ээр нэмэгдэх ба түүнийг дагаж байгаа бүх элементийн хувьд өмнөх элементийн утга 1-тэй тэнцүү байна.
1 (2+1)3 (3+1)4 = 1 3 4
Дараа нь бид i = 3 байгаа эсэхийг дахин шалгана.
1 3 5
Дараа нь - i = 2 байгаа эсэхийг шалгана уу.
1 4 5
Дараа нь i = 1 эргэлт ирнэ.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
Мөн цаашлаад,
2 3 5
2 4 5
3 4 5 - сүүлчийн хослол, учир нь түүний бүх элементүүд нь n - m + i-тэй тэнцүү байна.

Дэлхийн дэд бүтцэд PIN-ийн үүрэг чухал хэдий ч хүмүүс PIN кодыг хэрхэн сонгодог талаар эрдэм шинжилгээний судалгаа хараахан хийгдээгүй байна.

Кембрижийн их сургуулийн судлаач Сорен Прейбуш, Росс Андерсон нар 4 оронтой банкны PIN кодыг таахад хүндрэлтэй байгаа талаарх дэлхийн анхны тоон дүн шинжилгээг нийтэлснээр нөхцөл байдлыг зассан.

Банкны бус эх сурвалжаас нууц үг задруулсан тухай мэдээлэл болон онлайн судалгааг ашиглан судлаачид хэрэглэгчид вэб сайтын нууц үгийн сонголтоос хамаагүй илүү PIN кодыг сонгохдоо нухацтай ханддаг болохыг тогтоожээ: ихэнх кодууд нь бараг санамсаргүй тоонуудаас бүрддэг. Гэсэн хэдий ч анхны өгөгдлүүдийн дунд бас байдаг энгийн хослолууд, мөн төрсөн өдөр - өөрөөр хэлбэл, азаар халдагчид хүссэн кодыг тааж чадна.

Судалгааны эхлэл нь RockYou мэдээллийн сангаас 4 оронтой нууц үгийн дараалал (1.7 сая), түгжих програмын 200 мянган PIN кодын мэдээллийн сан байв. iPhone дэлгэц(Суурийг програм хөгжүүлэгч Даниел Амитай өгсөн). Энэхүү өгөгдлөөр бүтээгдсэн графикууд нь сонирхолтой хэв маягийг харуулдаг - огноо, жил, давтагдсан тоо, тэр ч байтугай 69-р төгссөн PIN кодууд. Эдгээр ажиглалт дээр үндэслэн эрдэмтэд шугаман регрессийн загварыг бүтээсэн бөгөөд энэ нь PIN бүрийн алдар нэрийг 25 хүчин зүйлээс хамааруулан тооцоолсон. код нь DDMM форматтай огноо мөн үү, өсөх дараалал уу гэх мэт. Эдгээр ерөнхий нөхцөл нь багц тус бүрийн PIN кодын 79% ба 93% хангагдсан байна.

Тиймээс хэрэглэгчид хэдхэн энгийн хүчин зүйл дээр үндэслэн 4 оронтой кодыг сонгодог. Хэрэв банкны ПИН кодыг ийм байдлаар сонгосон бол гуравхан оролдлого хийхэд тэдгээрийн 8-9% -ийг тааж болно! Гэхдээ мэдээжийн хэрэг хүмүүс банкны кодуудад илүү анхааралтай ханддаг. Банкны бодит мэдээлэл байхгүй тул судлаачид 1300 гаруй хүнтэй ярилцлага хийж, бодит ПИН код өмнө нь авч үзсэнээс хэр ялгаатай болохыг үнэлжээ. Судалгааны онцлогийг харгалзан судалгаанд оролцогчдоос кодуудын талаар асуугаагүй, зөвхөн дээрх хүчин зүйлсийн аль нэгэнд (өсөлт, DDMM формат гэх мэт) нийцэж байгаа эсэхийг асуусан.

Хүмүүс банкны пин кодыг сонгохдоо илүү болгоомжтой ханддаг нь тогтоогдсон. Судалгаанд оролцогчдын дөрөвний нэг нь банкнаас үүсгэсэн санамсаргүй PIN кодыг ашигладаг. Гуравны нэгээс илүү хувь нь хуучин утасны дугаар, оюутны ID дугаар эсвэл санамсаргүй мэт харагдах бусад дугаарыг ашиглан ПИН кодоо сонгодог. Үр дүнгээс харахад карт эзэмшигчдийн 64% нь псевдо санамсаргүй PIN код ашигладаг бөгөөд энэ нь өмнөх банк бус кодтой туршилтын явцад 23-27% -иас хамаагүй илүү байна. Өөр 5% нь тооны загвар (жишээ нь 4545) ашигладаг бол 9% нь гарын хээг (жишээ нь 2684) илүүд үздэг. Ерөнхийдөө зургаан оролдлого хийсэн халдагчид (гурвыг нь АТМ-ээр, гурав нь төлбөрийн терминалаар) хэн нэгний картын ПИН кодыг таах магадлал 2%-иас бага байдаг.

Хүчин зүйл	Жишээ	чамайг рок	iPhone	Ярилцлага
Огноо
DDMM	2311	5.26	1.38	3.07
DMYY	3876	9.26	6.46	5.54
MMDD	1123	10.00	9.35	3.66
ммй	0683	0.67	0.20	0.94
ӨӨӨӨ	1984	33.39	7.12	4.95
Нийт		58.57	24.51	22.76
Гарны загвар
холбоотой	6351	1.52	4.99	-
дөрвөлжин	1425	0.01	0.58	-
булангууд	9713	0.19	1.06	-
хөндлөн	8246	0.17	0.88	-
диагональ шугам	1590	0.10	1.36	-
хэвтээ шугам	5987	0.34	1.42	-
үг	5683	0.70	8.39	-
босоо шугам	8520	0.06	4.28	-
Нийт		3.09	22.97	8.96
дижитал загвар
69-ээр төгсдөг	6869	0.35	0.57	-
зөвхөн 0-3 тоо	2000	3.49	2.72	-
зөвхөн 0-6 тоо	5155	4.66	5.96	-
давтагддаг хосууд	2525	2.31	4.11	-
ижил цифрүүд	6666	0.40	6.67	-
буурах дараалал	3210	0.13	0.29	-
өсөх дараалал	4567	3.83	4.52	-
Нийт		15.16	24.85	4.60
Санамсаргүй тоонуудын багц		23.17	27.67	63.68

Бүх зүйл сайхан байх болно, гэхдээ харамсалтай нь судалгаанд оролцогчдын нэлээд хэсэг нь (23%) огноо хэлбэрээр ПИН кодыг сонгодог бөгөөд тэдний бараг гуравны нэг нь төрсөн он сар өдрөө ашигладаг. Энэ нь асуудлыг ихээхэн өөрчилдөг, учир нь бараг бүгд (99%) нь үүнийг түрийвчэндээ хадгалдаг гэж хариулжээ. банкны картуудэнэ огноог хэвлэсэн янз бүрийн иргэний үнэмлэх. Хэрэв халдагч карт эзэмшигчийн төрсөн өдрийг мэддэг бол чадварлаг арга барилаар PIN кодыг таах магадлал 9% хүртэл өсдөг.

Хамгийн алдартай 100 PIN код

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.Практик дээр халдагчид таны ПИН кодыг тагнаж чагнах нь үүнийг таамаглахаас хамаагүй хялбар байдаг. Гэхдээ та өөрийгөө шагайхаас хамгаалж чадна, тэр ч байтугай найдваргүй нөхцөлд ч гэсэн:

Бүх N элемент бөгөөд нэг нь ч давтагдахгүй бол энэ нь сэлгэцийн тооны асуудал юм. Шийдлийг энгийн байдлаар олж болно. N элементийн аль нэг нь эгнээний эхний байрыг эзэлж чадах тул N сонголтыг олж авна. Хоёрдугаарт - эхний байранд аль хэдийн ашиглагдсанаас бусад нь. Тиймээс аль хэдийн олдсон N сонголт бүрийн хувьд (N - 1) хоёрдугаар байрын сонголтууд байгаа бөгөөд нийт хослолын тоо N*(N - 1) болно.
Цувралын үлдсэн элементүүдийн хувьд ижил зүйлийг давтаж болно. Хамгийн сүүлчийн байранд зөвхөн нэг сонголт үлдсэн - сүүлчийн элемент. Эцсийн эцэст - хоёр сонголт гэх мэт.
Иймд N-ийн давтагдахгүй элементийн цуваа нь 1-ээс N хүртэлх бүх бүхэл тоонуудын үржвэртэй тэнцүү байна.Энэхүү үржвэрийг N-ийн факториал гэж нэрлэх ба N-ээр тэмдэглэнэ! ("en factorial" гэж уншина уу).

Өмнөх тохиолдолд боломжит элементүүдийн тоо болон цувралын газруудын тоо давхцаж, тэдгээрийн тоо нь N-тэй тэнцүү байсан. Гэхдээ цувралд боломжит элементүүдээс цөөн тооны газар байгаа тохиолдолд нөхцөл байдал боломжтой. Өөрөөр хэлбэл, түүврийн элементүүдийн тоо нь M, M тоотой тэнцүү байна< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Нэгдүгээрт, нийт дүнг тоолох шаардлагатай байж магадгүй юм боломжит арга замууд, тэдгээрийг N-ээс M элементийн цуваагаар байрлуулж болно.Ийм аргыг байршуулалт гэж нэрлэдэг.
Хоёрдугаарт, судлаач N элементээс M элементийг сонгох хэд хэдэн арга замыг сонирхож магадгүй. Энэ тохиолдолд элементүүдийн дараалал чухал байхаа больсон, гэхдээ дурын хоёр сонголт бие биенээсээ дор хаяж нэг элементээр ялгаатай байх ёстой. . Ийм аргыг хослол гэж нэрлэдэг.

N элементээс M элементийн байршлын тоог олохын тулд сэлгэн залгахтай адил үндэслэлийг ашиглаж болно. Эхний ээлжинд N элемент байж болно, хоёрдугаарт (N - 1) гэх мэт. Гэхдээ хамгийн сүүлчийнх нь тоо сонголтууднь 1 биш, харин (N - M + 1), учир нь хуваарилалт дуусахад (N - M) ашиглагдаагүй элементүүд байх болно.
Тиймээс, N-ээс M элемент дээр байршуулах тоо нь (N - M + 1) -ээс N хүртэлх бүх бүхэл тоонуудын үржвэртэй тэнцүү, эсвэл N!/(N - M)!

Мэдээжийн хэрэг, N-ээс M элементийн хослолын тоо нь байрлуулах тооноос бага байх болно. Боломжит хослол бүрт M байна! энэ хослолын элементүүдийн дарааллаас хамааран боломжит байршуулалт. Иймд энэ тоог олохын тулд та N элементийн M элемент дээрх байршлын тоог N-д хуваах хэрэгтэй! Өөрөөр хэлбэл, N-ээс M элементийн хослолын тоо нь N!/(M!*(N - M)!).