Our งานปริศนา เดือนที่แล้วคือการประหยัด Trek สตาร์ พรรคผิวแปดนำโดย Enterprise เจ้าหน้าที่สื่อสาร ร้อยโท Uhura (เล่นโดยสาย นิโคลัส นิโคลัส). ลูกเรือถูกจองจำโดยเผ่าพันธุ์ต่างดาว Catenati บนดาวเคราะห์ใน เนบิวลาสร้อยคอ. ในการหลบหนี พวกเขาต้องเพิ่มความเป็นไปได้สูงสุดในการปฏิบัติงาน ซึ่งในตอนแรกดูเหมือนว่าจะมีความเป็นไปได้เพียงเล็กน้อยที่จะประสบความสำเร็จ
ลูกเรือแปดคนได้รับแจ้งเกี่ยวกับภารกิจนี้ในขณะที่ถูกกักตัวไว้ชั่วคราวในห้องส่วนกลาง ซึ่งพวกเขาสามารถสื่อสารและวางแผนได้อย่างอิสระ ในอีกไม่กี่ชั่วโมง พวกเขาจะถูกพาไปที่ห้องรูเล็ตทีละคน ห้องนี้มีปุ่มแปดปุ่มเรียงเป็นแถว โดยแต่ละปุ่มได้รับการตั้งโปรแกรมให้ตอบสนองต่อสมาชิกลูกเรือที่แตกต่างกัน เพื่อทำให้ลูกเรือเข้าใจผิด ปุ่มแต่ละปุ่มจะติดป้ายชื่อลูกเรือคนอื่นโดยสุ่ม ลูกเรือแต่ละคนสามารถกดได้ถึงสี่ปุ่ม ตามลำดับใดก็ได้ เมื่อใดก็ตามที่พวกเขากดปุ่ม พวกเขาจะเห็นว่าปุ่มนั้นเป็นของใคร ภายในสี่ครั้ง พวกเขาต้องหาปุ่มที่กำหนดให้ เพื่อให้ลูกเรือเป็นอิสระ พวกเขาทั้งหมดต้องประสบความสำเร็จในงานนี้ หากล้มเหลวแม้แต่ข้อเดียว ทั้งหมดจะถูกประหารชีวิต หลังจากสมาชิกลูกเรือเสร็จสิ้นความพยายาม พวกเขาจะต้องถูกโดดเดี่ยวโดยไม่มีวิธีส่งข้อมูลให้เพื่อนร่วมทีมของพวกเขา
โอกาสของความสำเร็จดูมีน้อย หากลูกเรือเลือกปุ่มแบบสุ่ม แต่ละคนจะมีโอกาส 1 ใน 2 ในการค้นหาปุ่มของตน โอกาสที่ทั้งแปดจะสำเร็จมีเพียง 1 ใน 256 หรือประมาณ 0.4%
แต่ไม่จำเป็นต้องกดปุ่มแบบสุ่ม วิธีหนึ่งที่จะเพิ่มความน่าจะเป็นของความสำเร็จก็คือการกดปุ่มทั้งหมดให้เท่ากันไม่ทางใดก็ทางหนึ่ง นี้นำเราไปสู่คำถามปริศนาแรกของเรา
1 ปริศนา
ความน่าจะเป็นในการเอาชีวิตรอดของลูกเรือจะดีขึ้นได้มากน้อยเพียงใดหากพวกเขาแน่ใจว่ากดปุ่มแต่ละปุ่มบ่อยเท่ากัน (แทนที่จะกดปุ่มสี่ปุ่มแบบสุ่ม)
ร็อบ คอร์เล็ตต์ และ เจปาเยตต์ ตอบคำถามนี้ได้ดีเหมือนที่พวกเขาทำคำถามอื่นๆ ทั้งหมด สำหรับแนวคิดหลักที่เข้าใจยากเบื้องหลังปริศนาในคอลัมน์นี้ Rob Corlett, JPayette และ Jouni Seppanen อธิบายไว้อย่างสวยงามในขณะที่ ซาชา บั๊กนอน มีส่วนในการแก้ปัญหาคอมพิวเตอร์
นี่คือคำตอบของ Rob Corlett:
วิธีหนึ่งที่จะทำให้แน่ใจได้ว่าแต่ละปุ่มถูกกดจำนวนครั้งเท่ากันคือแยกนักโทษออกเป็นสองกลุ่มที่มีขนาดเท่ากัน กลุ่มละ 4 คน
แต่ละกลุ่มจะกดปุ่มที่ตรงกับสมาชิกของกลุ่มเท่านั้น ดังนั้น หาก A, B, C และ D ทั้งหมดอยู่ในกลุ่มย่อยเดียวกัน พวกเขาจะกดปุ่มสำหรับ A, B, C และ D เท่านั้น
สิ่งนี้เปลี่ยนปัญหาเป็นการถามถึงความน่าจะเป็นที่นักโทษทุกคนจะได้รับการจัดสรรให้อยู่ในกลุ่มที่ถูกต้อง จากนั้นพวกเขาจะรับประกันว่าจะกดปุ่มของพวกเขาในการกดสี่ครั้งหรือน้อยกว่านั้น
จำนวนวิธีในการเติมกลุ่มแรก (และดังนั้นกลุ่มที่สองด้วย) ที่มีสี่คน คือ จำนวนวิธีในการเลือก 4 จาก 8 ซึ่งเท่ากับ C(8, 4) = 70 ดังนั้น จำนวนวิธีทั้งหมด แบ่งทุกคนออกเป็นสองกลุ่มคือ 70
มีการจัดสรรเพียงแห่งเดียวที่จัดสรรผู้ต้องขังแต่ละคนไปยังกลุ่มที่ถูกต้องได้อย่างถูกต้อง ดังนั้นความน่าจะเป็นที่ทุกคนจะอยู่ในกลุ่มที่ถูกต้องและนักโทษทั้งหมดที่รอดชีวิตคือ 1/70 ซึ่งดีกว่า 3.66 เท่าของ 1/256 ของกลยุทธ์ก่อนหน้านี้ [แต่มันยังเล็กมาก: แค่โอกาส 1.4%]
2 ปริศนา
มีวิธีปรับปรุงอัตราต่อรองที่น่าหดหู่ดั้งเดิมมากกว่า 90 เท่าเป็น 36.5% ซึ่งดูน่าอัศจรรย์! กลยุทธ์นี้เกี่ยวข้องกับการใช้การเดาแบบวนซ้ำหรือแบบโซ่ ดังนั้นการอ้างอิงถึงเนบิวลาสร้อยคอและคาเทนาติ (โซ่ เป็นภาษาละตินสำหรับลูกโซ่) ในรูปแบบพื้นฐานของกลยุทธ์ สมาชิกลูกเรือแต่ละคนเริ่มต้นด้วยการกดปุ่มที่มีชื่อของพวกเขา จากนั้นไปที่ปุ่มที่มีชื่อของสมาชิกลูกเรือซึ่งปุ่มแรกเป็นของจริง เป็นต้น สร้างสายสัมพันธ์ของชื่อ
เรามาดูกันว่ามันทำงานอย่างไรในทางปฏิบัติ ในแผนภาพ ปุ่มต่างๆ จะแสดงพร้อมกับป้ายกำกับเป็นสีขาว ตัวอักษรสีน้ำเงินด้านล่างแสดงถึงเจ้าของที่แท้จริงของปุ่มต่างๆ เมื่อสมาชิกลูกเรือคนแรก A เข้าไปในห้องรูเล็ต เธอกดปุ่ม A ก่อน นี่คือปุ่มของ C ดังนั้นเธอจึงกดปุ่ม C ถัดไป จากนั้นจึงกดปุ่ม E และสุดท้ายคือปุ่ม F ซึ่งอันที่จริงแล้วเป็นปุ่มของ A ดังนั้นเธอจึงค้นพบได้สำเร็จในสี่ครั้ง โปรดทราบว่าปุ่ม ACEF จะสร้างวงปิดของปุ่มสี่ปุ่ม เมื่อสมาชิกลูกเรือ C, E และ F ผลัดกัน พวกเขาจะไปรอบ ๆ วงปิดเดียวกันโดยเริ่มจากสถานที่ของตัวเองและค้นหาปุ่มของตัวเองในสี่ครั้ง
การจัดเรียงนี้ยังมีลูปขนาดเล็กสองปุ่มสองปุ่มแต่ละปุ่ม: BD และ GH ลูกเรือสี่คนนี้จะพบปุ่มของตัวเองภายในสองครั้ง ดังนั้น ด้วยข้อตกลงนี้ ลูกเรือทั้งหมดจะประสบความสำเร็จ และพวกเขาจะได้รับอิสรภาพ เป็นที่ชัดเจนว่าหากการจัดเรียงมีเพียงลูปที่มีความยาว 4 หรือน้อยกว่า ลูกเรือทั้งหมดจะประสบความสำเร็จและจะถูกปล่อยตัว ในทางกลับกัน หากมีการวนซ้ำ 5 ครั้งขึ้นไป ลูกเรือทั้งหมดในลูปนั้นจะไม่พบปุ่มของตนในสี่ครั้ง และลูกเรือจะถูกประหารชีวิต ในการหาความน่าจะเป็นของความสำเร็จ เราสามารถหาความน่าจะเป็นของการวนเป็น 5, 6, 7 หรือ 8 บวกกัน แล้วลบผลรวมนั้นออกจาก 1 ซึ่งคำนวณได้ง่ายกว่าวิธีอื่นเพราะสำหรับ 5 ปุ่มสามารถมีได้เพียงลูปเดียวที่มีสมาชิก 6, 7, 8 หรือ XNUMX คน
มี 8! วิธีต่างๆในการจัดเรียงปุ่มแปดปุ่ม แต่เมื่อเราสร้างลูป ลูปเดียวกันจะพิจารณาถึงแปดของการจัดเรียงเหล่านี้ (ABCDEFGH จะสร้างลูปเดียวกันกับ BCDEFGHA ซึ่งเหมือนกับ CDEFGHAB เป็นต้น) ดังนั้นความน่าจะเป็นที่จะมีลูปขนาด 8 คือ (8!/8)/8! ซึ่งก็แค่ 1/8 ในทำนองเดียวกัน ความน่าจะเป็นที่จะมีลูปขนาด 7 คือ 1/7 ของขนาด 6 คือ 1/6 และขนาด 5 คือ 1/5 ดังนั้น ความน่าจะเป็นที่จะประสบความสำเร็จสำหรับลูกเรือที่กล้าหาญของเราคือ 1 − (1/5 + 1/6 + 1/7 + 1/8) หรือ 36.5% ตามที่กล่าวไว้ก่อนหน้านี้
กลยุทธ์ข้างต้นใช้ได้กับนักโทษจำนวนเท่าใดก็ได้ และการปรับปรุงโอกาสเหนือวิธีการสุ่มจะเพิ่มขึ้นอย่างรวดเร็วเมื่อจำนวนนั้นเพิ่มขึ้น ประมาณเจ็ดเท่าสำหรับนักโทษสี่คน 24 เท่าสำหรับหกคน 93 เท่าสำหรับแปดคนและน่าประหลาดใจ (3.8 × 1029)-พับ 100 นักโทษ กุญแจสำคัญในการทำความเข้าใจการเพิ่มขึ้นอย่างมากนี้คือวิธีการผูกความสำเร็จหรือความล้มเหลวของสมาชิกแต่ละคนในกลุ่มกับคนอื่นๆ ส่วนใหญ่พวกเขาทั้งหมดประสบความสำเร็จหรือล้มเหลวร่วมกัน ความน่าจะเป็นของกลุ่มที่จะประสบความสำเร็จไม่ได้ลดลงมากจากคนเพียงคนเดียว โดยลดลงจาก 50% สำหรับผู้ต้องขังเพียงคนเดียวเป็น 30.69% เนื่องจากจำนวนผู้ต้องขังเพิ่มขึ้นโดยไม่มีขีดจำกัด ในทางกลับกัน ความน่าจะเป็นของวิธีการสุ่มหรือแม้กระทั่งวิธีการ "กดปุ่มคู่" ที่ประสบความสำเร็จลดลงอย่างรวดเร็วจนเกือบเป็นศูนย์สำหรับผู้ต้องขังจำนวนน้อย
หากตรรกะที่อยู่เบื้องหลังกลยุทธ์นี้ยังดูคลุมเครือ นี่คือการวิเคราะห์ปัญหานักโทษ 100 คนในเรื่องนี้ วิดีโอที่ยอดเยี่ยมโดย Veritasium.
3 ปริศนา
ปริศนานี้เกี่ยวกับร้อยโท Uhura ที่จำเกมในวัยเด็กซึ่งเป็นปริศนาตัวเดียวกัน แต่สำหรับหกคน ตามคำใบ้ฉันแนะนำให้แก้ไขปัญหาสำหรับคนสี่คน ตอนนี้เรามีสูตรแล้ว เราก็สามารถคำนวณความน่าจะเป็นได้ง่ายๆ
สำหรับสี่คน ความน่าจะเป็นที่จะวนรอบที่ยาวที่สุดเพียง 2 หรือ 1 คือ: 1 − (1/3 + 1/4) หรือ 41.7% โดยมีการเพิ่มเจ็ดเท่าจากการเลือกแบบสุ่ม
สำหรับหกคน ความน่าจะเป็นที่จะวนรอบที่ยาวที่สุดคือ 3, 2 หรือ 1 คือ: 1 − (1/4 + 1/5 + 1/6) หรือ 38.3% โดยได้กำไรมากกว่าตัวเลือกแบบสุ่มมากกว่า 24 เท่า
4 ปริศนา
ในขณะที่เรื่องราวของเราดำเนินต่อไป ปรากฎว่าหนึ่งใน Catenati ไม่ชอบเป็นพิเศษกับ Enterprise ลูกเรือและกำลังติดตามพวกเขาจากระยะไกล เขาสงสัยว่าพวกเขาได้คิดกลยุทธ์ที่มีประสิทธิภาพตามแผนภาพของอูฮูร่าแล้ว เขาตั้งใจแน่วแน่ที่จะทำลายแผนของพวกเขาโดยเข้าไปในห้องและเปลี่ยนลำดับของป้ายปุ่มก่อนที่รูเล็ตจะเริ่มขึ้น เขาสามารถขัดขวางแผนสำเร็จได้หรือไม่? ฝ่ายลงจอดต้องระมัดระวังเป็นพิเศษเพื่อปกปิดอะไร?
ในช่วงต้นของการอภิปรายกลยุทธ์ของลูกเรือ ดวงตาของ Uhura ก็หรี่ลงทันใด เธอให้สัญญาณกับลูกทีมของเธอ และเธอก็เปลี่ยนไปพูดเป็นภาษา Nicholese โดยประกาศว่า "โปรดอภิปรายเพิ่มเติมใน Nicholese" Nicholese เป็นภาษาใหม่ที่ Uhura ประดิษฐ์ขึ้นในช่วงต้นอาชีพของเธอสำหรับสถานการณ์แบบนี้เพื่อหลีกเลี่ยงการใช้นักแปลสากล “คุณต้องสังเกตเห็น Catenati ที่น่าสงสัย” เธอกล่าวต่อ “เขาสามารถพยายามก่อวินาศกรรมเราได้ ดังนั้นเราต้องแก้ไขแผนของเรา นี่คือสิ่งที่เราต้องทำ…”
Uhura ร่างแผนใหม่จนกระทั่งเธอพอใจที่สมาชิกทุกคนในทีมของเธอรู้ดีอย่างสมบูรณ์ จากนั้นเธอก็รำพึงด้วยสายตาอันไกลโพ้น “ฉันตั้งชื่อให้นิโคลีสตามนักแสดงหญิงที่มีชื่อเสียงในศตวรรษที่ 20 ฉันดีใจที่ฉันยืนยันว่า Starfleet สร้างมาตรฐานให้กับเรือทุกลำของเรา”
เธอหันกลับมาหาลูกเรือ “แค่นั้นเจ้าหน้าที่ รู้นะว่าต้องทำยังไง!”
เราไม่รู้แน่ชัดว่า Uhura บอกอะไรกับทีมของเธอ แต่ JPayette และ Rob Corlett มีความคิดที่ดีทีเดียว นี่คือ Rob Corlett อีกครั้ง:
หาก Catenati ชั่วร้ายได้ยินว่าพวกเขากำลังใช้กลยุทธ์นี้ เขาสามารถเปลี่ยนชื่อที่แสดงบนหน้าจอเพื่อให้แน่ใจว่ามีวงจรที่ยาวกว่า 4
เพื่อทำลายสิ่งนี้ นักโทษต้องยอมรับคำสั่งลับที่สุ่มลำดับ พวกเขาทำเช่นนี้โดยพูดว่า "ถ้าคุณเห็นชื่อ Uhura ให้ไปที่ปุ่มที่มีเครื่องหมาย Chekov หากคุณเห็นชื่อ Chekov ปรากฏขึ้น ให้ไปที่ปุ่มที่ระบุว่า Smith เป็นต้น”
ด้วยวิธีนี้ การจัดลำดับใหม่โดย Catenati ไม่สำคัญ เนื่องจากจะใช้ได้ก็ต่อเมื่อคุณทราบวิธีที่ลูกเรือจะตอบสนองต่อชื่อบนจอแสดงผลเท่านั้น พวกเขาจำเป็นต้องเก็บเป็นความลับในการสั่งซื้อใหม่ มิฉะนั้น มันอาจจะถูกทำลายอีกครั้ง
อย่างที่เราเห็น Uhura มั่นใจว่าความลับจะถูกเก็บไว้อย่างปลอดภัย สมาชิกแต่ละคนในทีมต้องใช้คำสั่งลับแบบเดียวกัน และทำให้แน่ใจว่า Catenati ชั่วร้ายไม่รู้ว่ามันคืออะไร อันที่จริง คำสั่งที่เปลี่ยนแปลงโดย Catenati ชั่วร้ายนั้นเพิ่มความน่าจะเป็นของลูกเรือที่จะประสบความสำเร็จ!
นี่คือสิ่งที่เกิดขึ้น Uhura เป็นคนแรกที่ถูกพาไปที่ห้องรูเล็ต เธอกดสามปุ่ม ไม่มีใครเป็นของเธอ เธอควรจะเศร้าหรือดีใจ? เธอกลั้นหายใจและกดที่สี่ เธอได้พบปุ่มที่แท้จริงของเธอแล้ว!
เธอรู้ว่าพวกเขาทั้งหมดจะรอด
5 ปริศนา
เปอร์เซ็นต์สูงสุดของความสำเร็จเข้าใกล้ขีดจำกัดเท่าใดเมื่อขนาดของฝ่ายลงจอดเพิ่มขึ้นอย่างไม่มีกำหนด? คุณช่วยอธิบายได้ไหมว่าทำไมวิธีนี้จึงมีประสิทธิภาพมากกว่าการกดปุ่มแบบสุ่ม
JPayette พิมพ์ว่า:
ทั้งหมดข้างต้นสรุปตรงไปตรงมากับลูกเรือ2n สมาชิกแต่ละคนอนุญาตให้กดได้มากที่สุด n ปุ่ม จากปริศนาที่ 2 เราสรุปได้ว่าโอกาสในการประสบความสำเร็จคือ
1 – (ผลรวมมากกว่า k ระหว่าง n + 1 และ 2n จาก 1/k).
ผลรวมสามารถเปรียบเทียบกับอินทิกรัลของ 1/x ในช่วงเวลา [n, 2n] ซึ่งทำให้เราสามารถพิสูจน์ได้ว่าในฐานะ n เติบโตเป็นอนันต์ ความน่าจะเป็นข้างต้นลดลงเพื่อมาบรรจบกันเป็น 1 − ln(2) ≈ 30.6% ที่น่าประหลาดใจ [จริง ๆ แล้ว 30.69% เป็นทศนิยมสองตำแหน่ง]
Rob Corlett เพิ่ม:
หากคุณไม่ทราบการผสานรวม คุณสามารถหาคำตอบโดยประมาณได้อย่างรวดเร็วโดยการคำนวณโดยใช้สเปรดชีต ฉันได้ 0.307 หนึ่งครั้ง n ถึงประมาณ 750 ซึ่งแม่นยำถึงทศนิยม 3 ตำแหน่ง
เราได้อธิบายไว้ข้างต้นแล้วว่าทำไมวิธีนี้ถึงได้ผล การวนซ้ำทั้งหมดที่ยาวกว่า 1 จะถูกแชร์โดยสมาชิกลูกเรือหลายคน ดังนั้นความสำเร็จและความล้มเหลวของพวกเขาจึงมีความสัมพันธ์กันอย่างมาก เป็นภาพประกอบของหลักการ "ทั้งหมดเพื่อหนึ่งและทั้งหมด" ออกจากคู่มือ Starfleet!
ขอขอบคุณผู้ร่วมสมทบทุกท่าน JPayette และ Rob Corlett ต่างก็ส่งคำตอบที่คุ้มค่าซึ่งทำให้คอลัมน์โซลูชันนี้ดูเหมือนซ้ำซากเกือบ อนิจจา ฉันต้องยึดกฎของเราในการเลือกผู้ชนะหนึ่งคนต่อคอลัมน์ปริศนา รางวัล Insights ตกเป็นของ JPayette เพื่อรับทราบการมีส่วนร่วมที่นี่และในปริศนาก่อนหน้า ยินดีด้วย! Rob Corlett ผลงานของคุณจะไม่ถูกลืม
เจอกันใหม่เดือนหน้าสำหรับ Insights ใหม่!
