มีกี่ชุดค่าผสม 2 ใน 10 ชุดค่าผสม: กฎพื้นฐานและสูตร การเรียงสับเปลี่ยนและทฤษฎีความน่าจะเป็น

องค์ประกอบ N ทั้งหมดและไม่มีการทำซ้ำ นี่คือปัญหาของจำนวนการเรียงสับเปลี่ยน วิธีแก้ปัญหาสามารถพบได้ง่าย องค์ประกอบ N ใด ๆ สามารถเป็นที่หนึ่งในแถวได้ ดังนั้น N ตัวเลือกจะได้รับ อันดับที่สอง - ใด ๆ ยกเว้นอันที่ใช้เป็นที่หนึ่งแล้ว ดังนั้น สำหรับแต่ละตัวเลือก N ที่พบแล้ว จะมีตัวเลือกอันดับสอง (N - 1) และจำนวนชุดค่าผสมทั้งหมดจะกลายเป็น N*(N - 1)
สามารถทำซ้ำได้เช่นเดียวกันกับองค์ประกอบที่เหลือของซีรีส์ สำหรับสถานที่สุดท้ายมีเพียงตัวเลือกเดียวที่เหลืออยู่ - องค์ประกอบสุดท้ายที่เหลืออยู่ สำหรับขั้นสุดท้าย - สองตัวเลือกและอื่น ๆ
ดังนั้น สำหรับชุดขององค์ประกอบที่ไม่ซ้ำ N การเรียงสับเปลี่ยนที่เป็นไปได้จะเท่ากับผลคูณของจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง N ผลคูณนี้เรียกว่าแฟกทอเรียลของ N และเขียนแทนด้วย N! (อ่านว่า "en แฟกทอเรียล")

ในกรณีก่อนหน้านี้ จำนวนองค์ประกอบที่เป็นไปได้และจำนวนตำแหน่งในซีรีส์ใกล้เคียงกัน และจำนวนองค์ประกอบนั้นเท่ากับ N แต่สถานการณ์ก็เป็นไปได้เมื่อมีตำแหน่งในซีรีส์น้อยกว่าจำนวนองค์ประกอบที่เป็นไปได้ กล่าวอีกนัยหนึ่ง จำนวนองค์ประกอบในตัวอย่างเท่ากับจำนวน M และ M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
ขั้นแรก อาจจำเป็นต้องนับจำนวนวิธีที่เป็นไปได้ทั้งหมดที่สามารถจัดเรียงองค์ประกอบ M จาก N ในแถว วิธีดังกล่าวเรียกว่าตำแหน่ง
ประการที่สอง ผู้วิจัยอาจสนใจในจำนวนวิธีที่องค์ประกอบ M สามารถเลือกได้จาก N ในกรณีนี้ ลำดับขององค์ประกอบจะไม่มีความสำคัญอีกต่อไป แต่สองตัวเลือกใด ๆ จะต้องแตกต่างกันอย่างน้อยหนึ่งองค์ประกอบ . วิธีการดังกล่าวเรียกว่าการรวมกัน

ในการค้นหาจำนวนตำแหน่งขององค์ประกอบ M จาก N เราสามารถใช้วิธีให้เหตุผลแบบเดียวกับในกรณีของการเรียงสับเปลี่ยน ในตอนแรก ยังคงมีองค์ประกอบ N รายการได้ ในองค์ประกอบที่สอง (N - 1) เป็นต้น แต่สำหรับตำแหน่งสุดท้าย จำนวนตัวเลือกที่เป็นไปได้ไม่ใช่หนึ่ง แต่เป็น (N - M + 1) เนื่องจากเมื่อการจัดวางเสร็จสมบูรณ์ จะยังมี (N - M) องค์ประกอบที่ไม่ได้ใช้
ดังนั้น จำนวนตำแหน่งเหนือองค์ประกอบ M จาก N จะเท่ากับผลคูณของจำนวนเต็มทั้งหมดตั้งแต่ (N - M + 1) ถึง N หรือเทียบเท่า ผลหาร N!/(N - M)!

เห็นได้ชัดว่าจำนวนชุดค่าผสมขององค์ประกอบ M จาก N จะน้อยกว่าจำนวนตำแหน่ง สำหรับทุกชุดค่าผสมที่เป็นไปได้ มี M! ตำแหน่งที่เป็นไปได้ขึ้นอยู่กับลำดับขององค์ประกอบของชุดค่าผสมนี้ ดังนั้น หากต้องการหาตัวเลขนี้ คุณต้องหารจำนวนตำแหน่งในองค์ประกอบ M จาก N คูณ N! กล่าวอีกนัยหนึ่ง จำนวนองค์ประกอบ M จาก N คือ N!/(M!*(N - M)!)

คอมบิเนเตอร์

Combinatorics เป็นสาขาหนึ่งของคณิตศาสตร์ที่ศึกษาปัญหาของการเลือกและการจัดเรียงองค์ประกอบจากชุดพื้นฐานตามกฎที่กำหนด สูตรและหลักการของ combinatorics ใช้ในทฤษฎีความน่าจะเป็นเพื่อคำนวณความน่าจะเป็นของเหตุการณ์สุ่ม และเพื่อให้ได้กฎการกระจายตัวของตัวแปรสุ่ม สิ่งนี้ทำให้สามารถศึกษากฎของปรากฏการณ์สุ่มมวลได้ ซึ่งเป็นสิ่งสำคัญมากสำหรับความเข้าใจที่ถูกต้องเกี่ยวกับกฎทางสถิติที่แสดงออกในธรรมชาติและเทคโนโลยี

กฎสำหรับการบวกและการคูณใน combinatorics

กฎผลรวม หากการกระทำ A และ B สองอย่างเป็นเอกสิทธิ์ร่วมกัน และการกระทำ A สามารถดำเนินการได้ m วิธี และ B ได้ n วิธี ดังนั้น การกระทำอย่างใดอย่างหนึ่งเหล่านี้ (A หรือ B) สามารถดำเนินการได้ n + m วิธี

ตัวอย่างที่ 1

มีเด็กชาย 16 คนและเด็กหญิง 10 คนในชั้นเรียน สามารถแต่งตั้งผู้ดูแลได้กี่วิธี?

สารละลาย

คุณสามารถแต่งตั้งเด็กชายหรือเด็กหญิงให้ปฏิบัติหน้าที่ได้ เช่น เด็กผู้ชาย 16 คนหรือเด็กผู้หญิง 10 คนใดก็ได้สามารถปฏิบัติหน้าที่ได้

ตามกฎผลรวม เราได้ว่าเจ้าหน้าที่ปฏิบัติหน้าที่หนึ่งคนสามารถกำหนดได้ 16+10=26 วิธี

กฎของผลิตภัณฑ์ ให้มันจำเป็นต้องดำเนินการ k ตามลำดับ ถ้าการกระทำที่หนึ่งทำได้ n 1 วิธี การกระทำที่สองทำได้ n 2 วิธี การกระทำที่สามทำได้ n 3 วิธี เรื่อยไปจนถึงการกระทำที่ k ที่สามารถดำเนินการได้ n k วิธี ดังนั้นการกระทำทั้งหมดพร้อมกันจะได้ ดำเนินการ:

วิธี

ตัวอย่างที่ 2

มีเด็กชาย 16 คนและเด็กหญิง 10 คนในชั้นเรียน สามารถแต่งตั้งผู้เข้าร่วมประชุมสองคนได้กี่วิธี?

สารละลาย

บุคคลแรกที่ปฏิบัติหน้าที่อาจเป็นเด็กชายหรือเด็กหญิงก็ได้ เพราะ มีเด็กผู้ชาย 16 คนและเด็กผู้หญิง 10 คนในชั้นเรียน จากนั้นคุณสามารถแต่งตั้งเจ้าหน้าที่คนแรกได้ด้วยวิธี 16 + 10 = 26 วิธี

หลังจากที่เราเลือกเจ้าหน้าที่คนแรกแล้ว เราก็สามารถเลือกคนที่สองจาก 25 คนที่เหลือได้ นั่นคือ 25 วิธี

ตามทฤษฎีบทการคูณ ผู้เข้าร่วมสองคนสามารถเลือกได้ด้วยวิธี 26*25=650

ชุดค่าผสมโดยไม่ต้องทำซ้ำ การผสมผสานกับการทำซ้ำ

ปัญหาคลาสสิกของ combinatorics คือปัญหาของจำนวนชุดค่าผสมที่ไม่มีการทำซ้ำ เนื้อหาของคำถามสามารถแสดงได้: เท่าไหร่ วิธี สามารถ เลือก ม. จาก น. รายการต่าง ๆ?

ตัวอย่างที่ 3

คุณต้องเลือกหนังสือ 4 ใน 10 เล่มที่มีให้เป็นของขวัญ สามารถทำได้กี่วิธี?

สารละลาย

เราต้องเลือกหนังสือ 4 ใน 10 เล่ม และลำดับที่เลือกไม่สำคัญ ดังนั้น คุณต้องหาจำนวนชุดค่าผสมของ 10 องค์ประกอบด้วย 4:

.

พิจารณาปัญหาของจำนวนชุดค่าผสมที่มีการทำซ้ำ: มีวัตถุที่เหมือนกัน r ของแต่ละชนิดที่แตกต่างกัน n ชนิด; เท่าไหร่ วิธี สามารถ เลือก ม.() ของ เหล่านี้ (n*r) รายการ?

.

ตัวอย่างที่ 4

ร้านขนมอบขายเค้ก 4 ชนิด ได้แก่ นโปเลียน เอแคลร์ ชอร์ตเบรด และพัฟ เค้ก 7 ชิ้นซื้อได้กี่วิธี?

สารละลาย

เพราะ ในบรรดาเค้ก 7 ชิ้นสามารถมีเค้กที่มีความหลากหลายเหมือนกันได้ จากนั้นจำนวนวิธีที่สามารถซื้อเค้ก 7 ชิ้นได้จะพิจารณาจากจำนวนชุดค่าผสมที่มีการทำซ้ำตั้งแต่ 7 ถึง 4

.

ตำแหน่งที่ไม่มีการทำซ้ำ ตำแหน่งที่มีการทำซ้ำ

ปัญหาคลาสสิกของ combinatorics คือปัญหาของจำนวนตำแหน่งที่ไม่มีการทำซ้ำ เนื้อหาของคำถามสามารถแสดงได้: เท่าไหร่ วิธี สามารถ เลือก และ สถานที่ โดย ม. ที่แตกต่างกัน สถานที่ ม. จาก แตกต่างกัน รายการ?

ตัวอย่างที่ 5

หนังสือพิมพ์บางฉบับมี 12 หน้า จำเป็นต้องวางรูปถ่ายสี่รูปบนหน้าหนังสือพิมพ์นี้ สามารถทำได้กี่วิธีหากไม่มีหน้าใดของหนังสือพิมพ์ควรมีรูปถ่ายมากกว่าหนึ่งรูป

สารละลาย.

ในปัญหานี้ เราไม่เพียงแค่เลือกรูปถ่ายเท่านั้น แต่วางไว้ในบางหน้าของหนังสือพิมพ์ และแต่ละหน้าของหนังสือพิมพ์ควรมีรูปภาพไม่เกินหนึ่งรูป ดังนั้นปัญหาจึงลดลงเป็นปัญหาคลาสสิกในการกำหนดจำนวนตำแหน่งโดยไม่ต้องทำซ้ำจาก 12 องค์ประกอบโดย 4 องค์ประกอบ:

ดังนั้น 4 รูปใน 12 หน้าจึงสามารถจัดเรียงได้ 11880 วิธี

นอกจากนี้ งานดั้งเดิมของ combinatorics คือปัญหาของจำนวนตำแหน่งที่มีการทำซ้ำ ซึ่งเนื้อหาสามารถแสดงได้ด้วยคำถาม: เท่าไหร่ วิธี สามารถ คุณขกองทัพ และ สถานที่ โดย ม. ที่แตกต่างกัน สถานที่ ม. จาก n รายการกับเรดิ ที่ มี เหมือน?

ตัวอย่างที่ 6

เด็กชายมีแสตมป์ที่มีหมายเลข 1, 3 และ 7 จากชุดสำหรับเกมกระดาน เขาตัดสินใจใช้แสตมป์เหล่านี้เพื่อใส่ตัวเลข 5 หลักในหนังสือทุกเล่ม เพื่อรวบรวมเป็นแคตตาล็อก เด็กชายสามารถสร้างตัวเลขห้าหลักได้กี่ตัว?

การเรียงสับเปลี่ยนโดยไม่ต้องทำซ้ำ. การเรียงสับเปลี่ยนด้วยการทำซ้ำ

ปัญหาคลาสสิกของ combinatorics คือปัญหาของจำนวนของการเรียงสับเปลี่ยนโดยไม่มีการทำซ้ำ เนื้อหาของคำถามสามารถแสดงได้: เท่าไหร่ วิธี สามารถ สถานที่ น หลากหลาย รายการ บน แตกต่างกัน สถานที่?

ตัวอย่างที่ 7

"คำ" สี่ตัวอักษรสามารถสร้างจากตัวอักษรของคำว่า "การแต่งงาน" ได้กี่ตัว?

สารละลาย

ชุดทั่วไปคือ 4 ตัวอักษรของคำว่า "การแต่งงาน" (b, p, a, k) จำนวนของ "คำ" ถูกกำหนดโดยการเรียงสับเปลี่ยนของตัวอักษรทั้ง 4 ตัวนี้ เช่น

ในกรณีที่มีองค์ประกอบ n ที่เลือกเหมือนกัน (การเลือกพร้อมการส่งคืน) ปัญหาของจำนวนการเรียงสับเปลี่ยนที่มีการทำซ้ำสามารถแสดงได้ด้วยคำถาม: วัตถุ n ชิ้นสามารถจัดเรียงใหม่ในสถานที่ต่างๆ ได้กี่วิธี ถ้าในบรรดาวัตถุ n ชิ้น มี k ประเภทที่แตกต่างกัน (k< n), т. е. есть одинаковые предметы.

ตัวอย่างที่ 8

ตัวอักษรของคำว่า "Mississippi" สามารถผสมตัวอักษรได้กี่แบบ?

สารละลาย

มีตัวอักษร "m" 1 ตัว "i" 4 ตัว "c" 3 ตัว และ "p" 1 ตัว รวมทั้งหมด 9 ตัว ดังนั้น จำนวนการเรียงสับเปลี่ยนที่มีการทำซ้ำคือ

สรุปความเป็นมาในส่วน "COMBINATORICS"

เพื่อน! เนื่องจากผมมีสมุดบันทึกที่ตายแล้วนี้อยู่แล้ว ผมจึงใช้มันเพื่อถามปัญหาที่นักฟิสิกส์ 3 คน นักเศรษฐศาสตร์ 2 คน คนหนึ่งจากโพลีเทคนิค และอีกคนหนึ่งจากมนุษยศาสตร์ ประสบปัญหาเมื่อวานนี้ เราทำลายสมองของเราทั้งหมด และเราได้รับผลลัพธ์ที่แตกต่างกันอย่างต่อเนื่อง อาจมีโปรแกรมเมอร์และอัจฉริยะทางคณิตศาสตร์ในหมู่คุณ นอกจากนั้น ปัญหามักเกิดขึ้นที่โรงเรียนและง่ายมาก เราแค่ไม่มีสูตร เพราะเราละทิ้งวิทยาศาสตร์ที่แน่นอน และด้วยเหตุผลบางอย่าง เราจึงเขียนหนังสือและวาดภาพแทน ขอโทษ.

ดังนั้น backstory

ฉันได้รับบัตรธนาคารใบใหม่ และเช่นเคย ฉันเดารหัสพินได้อย่างง่ายดาย แต่ไม่ได้อยู่ในแถว ฉันหมายถึงว่ารหัสพินคือ 8794 และฉันโทรไปที่ 9748 นั่นคือฉันได้รับชัยชนะ เดาตัวเลขทั้งหมดอยู่ในเลขสี่หลักที่กำหนด ใช่ ไม่ใช่แค่ตัวเลขแต่เพียงแค่ ส่วนประกอบของมันที่สงสัย. แต่ตัวเลขล้วนจริง! หมายเหตุ - ฉันทำแบบสุ่ม นั่นคือฉันไม่ต้องใส่ตัวเลขที่รู้จักแล้วในลำดับที่ถูกต้อง ฉันแค่แสดงด้วยจิตวิญญาณ: ที่นี่มีตัวเลขสี่ตัวที่ฉันไม่รู้จัก และฉันเชื่อว่าในหมู่พวกเขาอาจมี เป็น 9, 7, 4 และ 8 และลำดับของพวกเขาไม่สำคัญเราถามตัวเองทันที ฉันมีกี่ตัวเลือก(คงเข้าใจว่าเท่เลยเอามาเดาเอา) นั่นคือฉันต้องเลือกตัวเลขสี่ตัวรวมกันกี่ตัว และแน่นอนว่านรกก็เริ่มขึ้น หัวของเราระเบิดตลอดเย็นและทุกคนก็ได้รับคำตอบที่แตกต่างไปจากเดิมอย่างสิ้นเชิง! ฉันยังเริ่มเขียนชุดค่าผสมทั้งหมดนี้ลงในสมุดโน้ตติดต่อกันเมื่อมันเพิ่มขึ้น แต่เมื่ออายุสี่ร้อยฉันรู้ว่ามีมากกว่าสี่ร้อยชุด (ไม่ว่าในกรณีใด นี่เป็นการหักล้างคำตอบของนักฟิสิกส์ Thrash ผู้ซึ่งรับรองกับฉันว่า มีชุดค่าผสมสี่ร้อยชุด แต่ก็ยังไม่ชัดเจนนัก) - และยอมแพ้

จริงๆ แล้ว, สาระสำคัญของคำถามความน่าจะเป็นของการเดา (ในลำดับใดก็ได้) ตัวเลขสี่ตัวที่อยู่ในตัวเลขสี่หลักคืออะไร?

หรือไม่มาจัดโครงสร้างใหม่ (ฉันเป็นนักมนุษยนิยม ขออภัย แม้ว่าฉันจะมีจุดอ่อนด้านคณิตศาสตร์อย่างมาก) เพื่อให้ชัดเจนและชัดเจนยิ่งขึ้น เท่าไหร่ ไม่เกิดซ้ำการผสมตัวเลขที่อยู่ในชุดเลขลำดับตั้งแต่ 0 ถึง 9999? ( โปรดอย่าสับสนกับคำถาม "จำนวนค่าผสม ไม่เกิดซ้ำตัวเลข"!!! เลขซ้ำได้! ฉันหมายความว่า 2233 และ 3322 เป็นชุดค่าผสมเดียวกันในกรณีนี้!!)

หรือเฉพาะเจาะจง ฉันต้องทายเลขหนึ่งในสิบสี่ครั้ง แต่ไม่ได้อยู่ในแถว

ดีหรืออย่างอื่น โดยทั่วไปคุณต้องทราบว่าฉันมีกี่ตัวเลือกสำหรับชุดค่าผสมตัวเลขซึ่งสร้างรหัสพินของการ์ด ช่วยด้วยคนดี! ได้โปรดช่วยอย่าเริ่มเขียนว่ามีตัวเลือก 9999 ตัวเลือกสำหรับสิ่งเหล่านี้(เมื่อวานนึกถึงทุกคนในตอนแรก) เพราะนี่เป็นเรื่องไร้สาระ - ในมุมมองที่เรากังวลคือหมายเลข 1234, หมายเลข 3421, หมายเลข 4312 และอื่น ๆ เป็นหนึ่งเดียวกัน! ใช่ตัวเลขสามารถทำซ้ำได้เพราะมีรหัสพิน 1111 หรือที่นั่นเช่น 0007 คุณสามารถจินตนาการถึงหมายเลขรถแทนรหัสพิน สมมติว่าความน่าจะเป็นในการเดาตัวเลขหลักเดียวทั้งหมดที่ประกอบกันเป็นหมายเลขรถยนต์เป็นเท่าใด หรือเพื่อที่จะกำจัดทฤษฎีความน่าจะเป็นโดยสิ้นเชิง - ฉันต้องเลือกชุดค่าผสมตัวเลขกี่ชุด?

โปรดสำรองคำตอบและเหตุผลของคุณด้วยสูตรที่แน่นอน เพราะเมื่อวานเราเกือบจะเสียสติไปแล้ว ขอบคุณมากล่วงหน้าสำหรับทุกคน!

ป.ล. คนฉลาดคนหนึ่ง โปรแกรมเมอร์ ศิลปิน และนักประดิษฐ์ แค่แนะนำวิธีแก้ไขปัญหาอย่างถูกต้อง ทำให้ฉันอารมณ์ดีไม่กี่นาที: " วิธีแก้ปัญหาคือ: เธอมีโรคย้ำคิดย้ำทำ การรักษาคือ: แต่งงานและพ่นมะเขือเทศ ถ้าฉันอยู่ในตำแหน่งของเธอ ฉันจะไม่กังวลกับคำถามที่ว่า "ความน่าจะเป็นคืออะไร" มากกว่า แต่กับคำถามที่ว่า "ฉันจะสนใจตัวเลขพวกนี้ไหม"โดยทั่วไปไม่มีอะไรจะเพิ่ม :)

เครื่องคิดเลขด้านล่างได้รับการออกแบบมาเพื่อสร้างชุดค่าผสมทั้งหมดขององค์ประกอบ n คูณ m
จำนวนของชุดค่าผสมดังกล่าวสามารถคำนวณได้โดยใช้เครื่องคิดเลข Elements of Combinatorics การเรียงสับเปลี่ยน ตำแหน่ง การรวมกัน

คำอธิบายของอัลกอริทึมการสร้างภายใต้เครื่องคิดเลข

อัลกอริทึม

ชุดค่าผสมถูกสร้างขึ้นตามลำดับพจนานุกรม อัลกอริทึมทำงานร่วมกับดัชนีลำดับขององค์ประกอบของชุด
ลองพิจารณาอัลกอริทึมด้วยตัวอย่าง
เพื่อความสะดวกในการนำเสนอ ให้พิจารณาชุดขององค์ประกอบ 5 รายการที่มีดัชนีขึ้นต้นด้วย 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

นักวิจัยแห่งมหาวิทยาลัยเคมบริดจ์ Sören Preibusch และ Ross Anderson ได้แก้ไขสถานการณ์ด้วยการเผยแพร่การวิเคราะห์เชิงปริมาณครั้งแรกของโลกเกี่ยวกับความยากในการเดารหัส PIN ธนาคาร 4 หลัก

นักวิจัยใช้ข้อมูลเกี่ยวกับการรั่วไหลของรหัสผ่านจากแหล่งที่ไม่ใช่ธนาคารและแบบสำรวจออนไลน์ นักวิจัยพบว่าผู้ใช้ให้ความสำคัญกับการเลือกรหัส PIN อย่างจริงจังมากกว่าการเลือกรหัสผ่านสำหรับเว็บไซต์ รหัสส่วนใหญ่ประกอบด้วยชุดตัวเลขที่เกือบจะสุ่ม อย่างไรก็ตามในข้อมูลเริ่มต้นมีทั้งชุดค่าผสมที่เรียบง่ายและวันเกิด - นั่นคือโชคดีผู้โจมตีสามารถเดารหัสที่เป็นเจ้าข้าวเจ้าของได้

จุดเริ่มต้นของการศึกษาคือชุดของลำดับรหัสผ่าน 4 หลักจากฐานข้อมูล RockYou (1.7 ล้าน) และฐานข้อมูลรหัส PIN 200,000 รหัสจากโปรแกรมล็อกหน้าจอ iPhone (ฐานข้อมูลนี้จัดทำโดยนักพัฒนาแอปพลิเคชัน Daniel Amitay) . กราฟที่สร้างขึ้นจากข้อมูลนี้แสดงรูปแบบที่น่าสนใจ เช่น วันที่ ปี ตัวเลขซ้ำ และแม้แต่รหัส PIN ที่ลงท้ายด้วย 69 จากการสังเกตเหล่านี้ นักวิทยาศาสตร์ได้สร้างแบบจำลองการถดถอยเชิงเส้นที่ประเมินความนิยมของ PIN แต่ละรายการโดยขึ้นอยู่กับปัจจัย 25 ประการ เช่น รหัสเป็นวันที่ในรูปแบบ DDMM ไม่ว่าจะเป็นลำดับจากน้อยไปหามากหรือไม่ และอื่นๆ เงื่อนไขทั่วไปเหล่านี้เป็นไปตาม 79% และ 93% ของรหัส PIN ในแต่ละชุด

ดังนั้น ผู้ใช้จึงเลือกรหัส 4 หลักตามปัจจัยง่ายๆ เพียงไม่กี่ข้อ หากเลือกรหัส PIN ของธนาคารด้วยวิธีนี้ 8-9% ของรหัสเหล่านั้นสามารถเดาได้ในความพยายามเพียงสามครั้ง! แต่แน่นอนว่าผู้คนให้ความสนใจกับรหัสธนาคารมากขึ้น ในกรณีที่ไม่มีข้อมูลธนาคารจริงจำนวนมาก นักวิจัยได้สัมภาษณ์ผู้คนมากกว่า 1,300 คนเพื่อประเมินว่ารหัส PIN จริงแตกต่างจากที่พิจารณาไปแล้วอย่างไร จากข้อมูลเฉพาะของการศึกษา ผู้ตอบแบบสอบถามจะไม่ถูกถามเกี่ยวกับรหัส แต่ถามเกี่ยวกับการปฏิบัติตามปัจจัยใดๆ ข้างต้นเท่านั้น (เพิ่มขึ้น รูปแบบ DDMM ฯลฯ)

ปรากฎว่าผู้คนระมัดระวังมากขึ้นในการเลือกรหัส PIN ของธนาคาร ประมาณหนึ่งในสี่ของผู้ตอบแบบสอบถามใช้ PIN แบบสุ่มที่ธนาคารสร้างขึ้น มากกว่าหนึ่งในสามเลือก PIN โดยใช้หมายเลขโทรศัพท์เก่า หมายเลขประจำตัวนักเรียน หรือชุดตัวเลขอื่นๆ ที่ดูสุ่ม จากผลการวิจัยพบว่า 64% ของผู้ถือบัตรใช้รหัส PIN แบบสุ่มหลอก ซึ่งมากกว่า 23-27% ในการทดลองก่อนหน้านี้กับรหัสที่ไม่ใช่ธนาคาร อีก 5% ใช้รูปแบบตัวเลข (เช่น 4545) และ 9% ชอบรูปแบบแป้นพิมพ์ (เช่น 2684) โดยทั่วไปแล้ว ผู้โจมตีที่พยายาม 6 ครั้ง (สามครั้งด้วย ATM และ 3 ครั้งด้วยเครื่องชำระเงิน) มีโอกาสน้อยกว่า 2% ที่จะคาดเดา PIN บัตรของผู้อื่น

PIN ยอดนิยม 100 อันดับแรก

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.

ป.ล.ในทางปฏิบัติ แน่นอนว่าผู้โจมตีสามารถสอดแนม PIN ของคุณได้ง่ายกว่าการคาดเดา แต่คุณยังสามารถป้องกันตัวเองจากการแอบดูได้ แม้จะดูเหมือนอยู่ในสถานการณ์ที่สิ้นหวัง:

Combinatorics เป็นสาขาหนึ่งของคณิตศาสตร์ที่ศึกษาคำถามเกี่ยวกับจำนวนค่าผสมต่างๆ ที่สามารถสร้างขึ้นจากวัตถุที่กำหนดภายใต้เงื่อนไขบางประการ พื้นฐานของ combinatorics มีความสำคัญมากสำหรับการประมาณค่าความน่าจะเป็นของเหตุการณ์สุ่ม เนื่องจาก มันคือสิ่งที่ทำให้สามารถคำนวณจำนวนสถานการณ์ที่แตกต่างกันที่เป็นไปได้โดยพื้นฐานสำหรับการพัฒนากิจกรรม

สูตรคอมบิเนชั่นพื้นฐาน

ให้มีองค์ประกอบ k กลุ่ม และกลุ่ม i-th ประกอบด้วยองค์ประกอบ n i เลือกหนึ่งองค์ประกอบจากแต่ละกลุ่ม จากนั้นจำนวน N ของวิธีทั้งหมดที่สามารถเลือกได้จะถูกกำหนดโดยความสัมพันธ์ N=n 1 *n 2 *n 3 *...*n k .

ตัวอย่างที่ 1ให้เราอธิบายกฎนี้ด้วยตัวอย่างง่ายๆ ให้มีองค์ประกอบ 2 กลุ่ม กลุ่มแรกประกอบด้วย 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 . วิธีการเลือกใน combinatorics นี้เรียกว่า ส่งคืนตัวอย่าง

ตัวอย่างที่ 3ตัวเลข 4 หลักจากเลข 1, 5, 6, 7, 8 สร้างจากเลข 1, 5, 6, 7, 8 ได้กี่ตัว
สารละลาย.มีความเป็นไปได้ห้าอย่างสำหรับแต่ละหลักของตัวเลขสี่หลัก ดังนั้น N=5*5*5*5=5 4 =625

พิจารณาเซตที่ประกอบด้วยสมาชิก n ตัว เซตนี้เรียกว่า combinatorics ประชากรทั่วไป.

จำนวนตำแหน่งจาก n องค์ประกอบโดย m

คำจำกัดความ 1.ที่พักจาก นองค์ประกอบโดย มใน combinatorics เรียกว่าใด ๆ ชุดที่สั่งจาก มองค์ประกอบต่าง ๆ ที่คัดเลือกมาจากประชาชนทั่วไปใน นองค์ประกอบ

ตัวอย่างที่ 4การจัดเรียงที่แตกต่างกันของสามองค์ประกอบ (1, 2, 3) สองต่อสองจะเป็นชุด (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3 , 2 ). ตำแหน่งอาจแตกต่างกันทั้งในองค์ประกอบและตามลำดับ

จำนวนตำแหน่งใน combinatorics แสดงด้วย A n m และคำนวณโดยสูตร:

ความคิดเห็น: n!=1*2*3*...*n (อ่าน: "en factorial") นอกจากนี้ จะถือว่า 0!=1

ตัวอย่างที่ 5. มีเลขสองหลักกี่ตัวที่หลักสิบกับหลักหน่วยต่างกันและเป็นเลขคี่?
สารละลาย:เพราะ มีเลขคี่ห้าหลัก ได้แก่ 1, 3, 5, 7, 9 จากนั้นปัญหานี้จะลดลงเหลือการเลือกและวางตัวเลขสองในห้าหลักที่แตกต่างกันในสองตำแหน่งที่แตกต่างกัน เช่น ตัวเลขที่กำหนดจะเป็น:

ความหมาย 2. การรวมกันจาก นองค์ประกอบโดย มใน combinatorics เรียกว่าใด ๆ ชุดไม่เรียงลำดับจาก มองค์ประกอบต่าง ๆ ที่คัดเลือกมาจากประชาชนทั่วไปใน นองค์ประกอบ

ตัวอย่างที่ 6. สำหรับชุด (1, 2, 3) ชุดค่าผสมคือ (1, 2), (1, 3), (2, 3)

จำนวนการรวมกันขององค์ประกอบ n โดย m

จำนวนชุดค่าผสมแสดงโดย C n m และคำนวณโดยสูตร:

ตัวอย่างที่ 7ผู้อ่านสามารถเลือกหนังสือสองเล่มจากหกเล่มที่มีอยู่ได้กี่วิธี?

สารละลาย:จำนวนวิธีเท่ากับจำนวนชุดของหนังสือหกเล่มคูณสอง นั่นคือ เท่ากับ:

การเรียงสับเปลี่ยนขององค์ประกอบ n

ความหมาย 3. การเรียงสับเปลี่ยนจาก นองค์ประกอบเรียกว่าใด ๆ ชุดที่สั่งองค์ประกอบเหล่านี้

ตัวอย่างที่ 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 ถ้าสามารถทำซ้ำได้กี่จำนวน
เพราะ เลขคู่ในตำแหน่งที่สามสามารถเป็น 0, 2, 4, 6, เช่น สี่หลัก ตำแหน่งที่สองสามารถเป็นตัวเลขเจ็ดหลักใดก็ได้ ตำแหน่งแรกสามารถเป็นตัวเลขเจ็ดหลักใดก็ได้ยกเว้นศูนย์ เช่น 6 ความเป็นไปได้ ผลลัพธ์ =4*7*6=168.
2. มีตัวเลขห้าหลักกี่ตัวที่อ่านเหมือนกันจากซ้ายไปขวาและจากขวาไปซ้าย?
ตำแหน่งแรกสามารถเป็นตัวเลขใดก็ได้ยกเว้น 0 เช่น ความเป็นไปได้ 9 ประการ ตำแหน่งที่สองสามารถเป็นตัวเลขใดก็ได้ เช่น 10 ความเป็นไปได้ อันดับที่สามสามารถเป็นหมายเลขใดก็ได้ เช่น 10 ความเป็นไปได้ หลักที่สี่และห้าถูกกำหนดไว้แล้ว โดยตรงกับหลักที่หนึ่งและสอง ดังนั้น จำนวนของตัวเลขดังกล่าวคือ 9*10*10=900
3. มีสิบวิชาในชั้นเรียนและห้าบทเรียนต่อวัน คุณสามารถจัดตารางเวลาในหนึ่งวันได้กี่วิธี?

4. สามารถเลือกผู้แทน 4 คนสำหรับการประชุมได้กี่วิธีหากมี 20 คนในกลุ่ม?

n = C 20 4 = (20!)/(4!*(20-4)!)=(16!*17*18*19*20)/((1*2*3*4)*(16! ))=(17*18*19*20)/(1*2*3*4)=4845.
5. สามารถใส่จดหมายแปดฉบับที่แตกต่างกันลงในซองจดหมายแปดซองได้กี่วิธีหากใส่จดหมายเพียงฉบับเดียวในแต่ละซอง
ในซองจดหมายแรก คุณสามารถใส่ตัวอักษร 1 ตัวจากทั้งหมด 8 ตัว ตัวที่สองจากตัวที่เหลืออีก 7 ตัว ตัวที่สามจากทั้งหมด 6 ตัว เป็นต้น n = 8! = 1*2*3*4*5*6*7*8 = 40320.
6. จากนักคณิตศาสตร์สามคนและนักเศรษฐศาสตร์สิบคน จำเป็นต้องมีคณะกรรมการซึ่งประกอบด้วยนักคณิตศาสตร์สองคนและนักเศรษฐศาสตร์หกคน สามารถทำได้กี่วิธี?