ห้องบอส
เหล่านี้คือปริศนาที่นักคณิตศาสตร์เล่าสู่กันฟัง แต่ละข้อเคยหยุดห้องพักอาจารย์ที่เต็มไปด้วยมืออาชีพมาแล้วทั้งห้อง; หลายข้องอกวรรณกรรมวิชาการเป็นของตัวเอง; ข้อสุดท้ายต้านทานทุกข้อเสนอคลี่คลายมาเกือบแปดสิบปี และปิดบทนี้ทั้งที่ตัวมันยังเปิดอยู่ เรตติงในห้องนี้อ่านว่า ★★★★ กับ ★★★★★ และมันวัดความลึก ไม่ใช่ความรู้พื้นฐาน — ไม่มีอะไรในห้องนี้ต้องการเกินกว่าเลขคณิต สิ่งที่แต่ละปริศนาเรียกร้องคือท่าที่น่าจะยังไม่อยู่ในกระเป๋าเครื่องมือของคุณ ลงมือไปตามโซ่เหตุผลยาวเหยียดโดยรั่วไหลเป็นศูนย์
ห้องนี้มีกฎ หนึ่งปริศนาต่อการนั่งหนึ่งครั้ง อ่านโจทย์ แล้วปิดหนังสือ แบกปัญหาไว้กับตัวหนึ่งวันก่อนอ่านต่อ: คุณค่าถูกผลิตขึ้นระหว่างความพยายาม ไม่ใช่ที่ตัวคำตอบ การแก้ข้อใดข้อหนึ่งในนี้ได้สดๆ เป็นเรื่องหายาก และนั่นไม่ใช่เกณฑ์วัด เกณฑ์คือการมาพบเฉลยแต่ละข้อโดยมีความพยายามที่ล้มเหลวมากพอหนุนหลัง จนไอเดียกุญแจ เมื่อมันมาถึง ได้ตอบคำถามที่คุณถามไปแล้วจริงๆ บอสที่ถูกศึกษาถ่ายโอนได้เกือบดีเท่าบอสที่ถูกโค่น
ข้อสังเกตหนึ่งข้อก่อนประตูจะเปิด แทบทุกสถานการณ์ในห้องนี้คุกคามชีวิตตัวละครของมัน — นักโทษ โจรสลัด ชาวเกาะใต้กฤษฎีกา ชายผู้ต้องโทษประหาร แนวเรื่องกำลังซื่อสัตย์กับระดับความสูงที่ไต่มาถึง: ที่ระดับนี้ไม่มีคะแนนปลอบใจ หกในเจ็ดเฉลยข้างล่างแน่นหนาไร้รอยรั่ว เป็นความแน่นอนโดยการก่อสร้าง ข้อที่เจ็ดแลกความแน่นอนกับปาฏิหาริย์ 31 เปอร์เซ็นต์ — แล้วพิสูจน์ว่าไม่มีกลยุทธ์ใดบนโลกนี้ทำได้ดีกว่าอย่างมีนัยสำคัญ
★★★★ 8 · ลูกบอลสิบสองลูก
ลูกบอลสิบสองลูกหน้าตาเหมือนกันหมด; หนึ่งลูกพอดีน้ำหนักเพี้ยน — หนักกว่าหรือเบากว่า ไม่รู้ว่าทางไหน มีตาชั่งสองแขนหนึ่งเครื่อง และชั่งได้สามครั้งเท่านั้น จงระบุลูกที่เพี้ยน และ ว่ามันหนักหรือเบา แบบการันตีผล
ข้อนี้คุ้มค่ากับหนึ่งคืนเต็มๆ มอบให้มันสักคืน
เฉลย. ก่อนความเฉลียวฉลาดใดๆ ให้ทำงบก่อน คำตอบที่เป็นไปได้มี 24 แบบ: สิบสองลูก แต่ละลูกอาจหนักหรือเบา การชั่งหนึ่งครั้งมีผลลัพธ์สามทางพอดี — ซ้ายจม ขวาจม สมดุล — ดังนั้นสามการชั่งแยกแยะอนาคตได้อย่างมากที่สุด 3³ = 27 แบบ ขณะที่สองครั้งจัดการได้เพียง 9 สามคือพื้นขั้นต่ำ และ 24 ≤ 27 บอกว่าพื้นนั้น*เฉียดฉิว*พอดี: ห้ามการชั่งครั้งใดผลาญสารสนเทศทิ้ง หลังผลลัพธ์ทุกทาง กรณีที่รอดต้องเหลืออย่างมาก 9 แล้ว 3 แล้ว 1
เลขคณิตนั้นออกแบบการเดินหมากแรกให้เองเสร็จสรรพ ชั่งหกกับหก สมดุลเป็นไปไม่ได้: การเอียงเกิดแน่ สิบสองกรณีรอดผ่านมัน และสิบสองอัดผ่านอนาคต 9 ทางที่สองการชั่งที่เหลือมีให้ไม่ได้ ตายตั้งแต่ยังไม่เริ่ม ห้ากับห้า? เอียงแล้วเหลือสิบ ตาย สี่กับสี่: เอียงเหลือแปด (สี่ผู้ต้องสงสัยข้อหาหนัก สี่ข้อหาเบา) และสมดุลก็เหลือแปด (สี่ลูกที่ไม่ถูกแตะ เป็นได้ทั้งสองทาง) รอดทุกกิ่ง ขอบเขตเชิงสารสนเทศบังคับการแบ่ง 4–4 ก่อนที่ความช่างประดิษฐ์จะถูกเรียกปรึกษาเสียด้วยซ้ำ
การชั่งครั้งแรก: {1,2,3,4} กับ {5,6,7,8}
ถ้าสมดุล — ลูกเพี้ยนอยู่ใน 9–12 แปดกรณี การชั่งครั้งสอง: {9,10,11} กับ {1,2,3} สามผู้ต้องสงสัยเทียบกับตุ้มถ่วงที่รู้แน่ว่าดี สมดุล → 12 คือตัวเพี้ยน; ชั่ง 12 กับลูกดีลูกใดก็ได้เพื่ออ่านทิศทาง ซ้ายจม → หนึ่งใน 9, 10, 11 หนัก; ชั่ง 9 กับ 10 — จานที่หนักกว่าชี้ตัวผู้ร้าย สมดุลตัดสินให้ 11 ผิด ขวาจม → สามตัวเดิมกลายเป็นผู้ต้องสงสัยข้อหาเบา; ทำแบบกระจกเงา
ถ้าฝั่งซ้ายจม — ไม่ 1–4 หนัก ก็ 5–8 เบา แปดกรณี การชั่งครั้งสองต้องคละผู้ต้องสงสัยข้ามจาน: {1,2,5} กับ {3,4,6} พัก 7 กับ 8 ไว้ข้างสนาม สมดุล → 7 หรือ 8 เบา; ชั่ง 7 กับ 8 ตัวที่เบากว่าคือผู้ร้าย (พวกมันสมดุลกันไม่ได้) ซ้ายจมอีกครั้ง → 1 หรือ 2 หนัก หรือ 6 เบา; ชั่ง 1 กับ 2 — ตัวหนักกว่าผิด สมดุลตัดสิน 6 เบา ขวาจม → 3 หรือ 4 หนัก หรือ 5 เบา; ชั่ง 3 กับ 4 — ตัวหนักกว่าผิด สมดุลตัดสิน 5 เบา นับกิ่งก้าน: 2 + 3 + 3 = 8 ทุกกรณีลงจอดครบ
ถ้าฝั่งขวาจม — ภาพกระจกเงา
สองไอเดียแบกการออกแบบนี้ไว้ ลูกที่พ้นข้อสงสัยแล้วกลายเป็นเครื่องมือ — ตุ้มถ่วงที่รู้แน่ว่าดี ซึ่งทำให้ชั่งผู้ต้องสงสัยสามตัวเทียบกับ "ความจริง" ได้ และผู้ต้องสงสัยถูกหมุนเวียนสลับจานเพื่อให้แต่ละผลลัพธ์ผ่าผู้รอดออกเป็นเกือบสามส่วนเท่าๆ กัน นี่คือปัญหาที่นักคณิตศาสตร์ยุคสงครามพูดเล่นกันว่าน่าจะโปรยทางอากาศเหนือเยอรมนีเพื่อทำให้งานวิจัยของศัตรูเป็นอัมพาต; การวิเคราะห์อย่างเป็นระบบของ Freeman Dyson ลงพิมพ์ใน Mathematical Gazette, 1946 — การคิดเชิงทฤษฎีสารสนเทศ สองปีก่อน Shannon จะตั้งชื่อให้ศาสตร์นั้น
ท่า — รีดสารสนเทศสูงสุดต่อการทดสอบ. ทำงบผลลัพธ์ก่อนออกแบบการทดลอง แล้วปั้นทุกการทดสอบให้ผลลัพธ์ของมันรับน้ำหนักเท่ากันที่สุดเท่าที่จะทำได้ นี่คือการออกแบบการทดลองฉบับจิ๋ว และมันโผล่ซ้ำทุกที่ที่คำถามมีราคาต้องจ่าย: การดีบัก การคัดแยกผู้ป่วยฉุกเฉิน และเกมยี่สิบคำถามทุกรูปแบบ
★★★★ 44 · เกมโจรสลัด
โจรสลัดห้าคน มีเหตุผลสมบูรณ์แบบ จัดลำดับชั้นเคร่งครัด: A อาวุโสสุด ตามด้วย B, C, D, E พวกเขาต้องแบ่งเหรียญทอง 100 เหรียญ โจรสลัดอาวุโสสุดเสนอวิธีแบ่ง; ทั้งห้าโหวต; คะแนนเสมอถือว่าผ่าน โดยเสียงของผู้เสนอเป็นเสียงชี้ขาด ถ้าข้อเสนอตก ผู้เสนอถูกโยนลงทะเล แล้วคนถัดไปตามลำดับชั้นขึ้นเสนอแทน ลำดับความสำคัญของโจรสลัดทุกคน เรียงตามนี้: เอาชีวิตรอด; จากนั้นกอบโกยทองให้มากที่สุด; จากนั้น หากอย่างอื่นเท่ากันหมด ก็*สนุก*กับการได้เห็นคู่แข่งถูกโยนลงทะเล A จะเสนออะไร?
ใช้เวลาตามสบาย ทองไม่หนีไปไหน
เฉลย. การให้เหตุผลเดินหน้าจมน้ำตาย — "B จะทำอะไร ซึ่งขึ้นกับว่า C จะทำอะไร ซึ่งขึ้นกับ…" หมุนวนโดยไร้สมอ จงทอดสมอที่ตอนจบ ตรงที่เกมกลายเป็นเรื่องจิ๊บจ๊อย แล้วม้วนย้อนกลับมา
เหลือโจรสลัดสองคน (D, E): D เสนอ 100–0 ให้ตัวเอง โหวตรับเอง และคะแนนเสมอผ่าน ความเห็นของ E เป็นเพียงเครื่องประดับ
สามคน (C, D, E): ถ้า C ตาย รัชสมัยของ D จะให้ E ศูนย์ — ดังนั้นเสียงของ E มีราคาหนึ่งเหรียญพอดี ซึ่งชนะ "ความว่างเปล่า" ที่ D สัญญาไว้ (เกณฑ์ชี้ขาดกระหายเลือดใช้ได้เฉพาะเมื่อ*อย่างอื่นเท่ากันหมด*เท่านั้น) C เสนอ 99–0–1 และผ่าน 2–1 D สวนราคาไม่ได้: อนาคตรอบถัดไปของเขาเองคือ 100 ดังนั้น C ไม่มีวันซื้อเขาไหว
สี่คน (B, C, D, E): ถ้า B ตาย ระบอบของ C จ่าย D ศูนย์ D จึงกลายเป็นเสียงราคาถูก: 99–0–1–0 ผ่าน 2–2 ด้วยเสียงชี้ขาดของ B การซื้อ E แทนจะแพงถึง 2 เพราะ E เก็บ 1 อยู่แล้วภายใต้ C
ห้าคน: ถ้า A ตาย แผนของ B จ่าย C ศูนย์และ E ศูนย์ A ต้องการสามเสียงจากห้า — ของตัวเองบวกอีกสอง — และคนอนาถาสองคนภายใต้ B ก็คือ C กับ E พอดี ราคาคนละหนึ่งเหรียญ A เสนอ 98–0–1–0–1 และผ่าน 3–2
ความช็อกอยู่ที่ทิศทาง ผู้เล่นที่เปราะบางที่สุด — คนแรกที่ต้องเผชิญไม้กระดานพาดกราบเรือ — คว้าไป 98 เปอร์เซ็นต์ ขณะที่โจรสลัดผู้ถือ "อำนาจต่อรองชัดๆ" เก็บได้เหรียญเดียวหรือไม่ได้เลย กติกาการโหวตบวกความรู้ร่วม (common knowledge) เรื่องความมีเหตุผล จัดสรรอำนาจในแบบที่สัญชาตญาณเรื่องอาวุโสไม่มีวันทำนายถูก บทเรียนที่สองซื้อได้ถูกกว่าที่นี่เมื่อเทียบกับโต๊ะเจรจาจริง: ทฤษฎีบทนี้เปราะ มนุษย์จริงปฏิเสธข้อเสนอที่หยามหน้าด้วยความแค้น — การทดลองเกมคำขาด (ultimatum game) แสดงให้เห็นซ้ำแล้วซ้ำเล่า — ดังนั้นการอุปนัยย้อนกลับยืนได้ไกลเพียงเท่าที่ข้อตั้งของมันยืน จงรู้ว่าเมื่อไรเกมเป็นโจรสลัด และเมื่อไรเป็นมนุษย์ ปัญหานี้เป็นคติชนของวงการเศรษฐศาสตร์; ฉบับบัญญัติคือ "A Puzzle for Pirates" ของ Ian Stewart ใน Scientific American, พฤษภาคม 1999 ซึ่งให้เครดิต Stephen Omohundro
ท่า — แก้เกมช่วงปลายก่อน. ทอดสมอที่เกมย่อยสุดท้าย ตรงที่คำตอบจิ๊บจ๊อย แล้วม้วนกลับมาสู่ปัจจุบัน ตีราคาทุกเสียงโหวตด้วยอนาคตทางเลือกของเจ้าของเสียง หมากรุกช่วงท้ายกระดาน การออกแบบสัญญา และการเจรจาทุกครั้งที่มีทางเดินหนี ล้วนวิ่งด้วยเครื่องยนต์ตัวนี้
★★★★ 9 · นักโทษ 100 คนกับหลอดไฟ
นักโทษหนึ่งร้อยคน ห้องสอบสวนหนึ่งห้องมีหลอดไฟดวงเดียว เริ่มต้นปิดอยู่ แต่ละวันพัศดีพานักโทษหนึ่งคน สุ่มอย่างสม่ำเสมอ เข้าห้อง; นักโทษจะสับสวิตช์หลอดไฟหรือปล่อยไว้เฉยๆ ก็ได้ ณ ขณะใดก็ตาม นักโทษคนใดก็ได้อาจประกาศ: "พวกเราทั้งหนึ่งร้อยคนได้เข้าห้องนี้แล้ว" ถ้าคำประกาศถูก ทุกคนเป็นอิสระ; ถ้าผิด ทุกคนตาย นักโทษปรึกษาหารือกันได้หนึ่งครั้ง ก่อนการเยือนครั้งแรก จงหากลยุทธ์ที่ไม่มีทางผิด
ออกแบบโพรโทคอลของตัวเองก่อนอ่านของพวกเขา
เฉลย. หน่วยความจำร่วมของห้องคือหนึ่งบิต ไม่มีใครนับเลขในนั้นได้ — แต่คนหนึ่งร้อยคน*คุยผ่าน*มันได้ ถ้าตกลงกันล่วงหน้าว่าใครพูดอะไร และเมื่อไร แต่งตั้งนักโทษหนึ่งคนเป็นผู้นับ (Counter) ที่เหลือทุกคนทำตามกฎข้อเดียว: ครั้งแรกที่คุณเข้าไปแล้วพบหลอดไฟปิดอยู่ จงเปิดมัน — ครั้งเดียวในชีวิต; ในทุกสถานการณ์อื่น อย่าแตะอะไรทั้งนั้น กฎของผู้นับ: เมื่อใดที่เขาพบหลอดเปิดอยู่ เขาปิดมันและบวกหนึ่งเข้าบัญชีส่วนตัว เมื่อบัญชีถึง 99 เขาประกาศ
ความถูกต้องนั้นสัมบูรณ์ ไม่ใช่แค่น่าจะถูก ทุกวงจรเปิด-แล้ว-ปิดที่ผู้นับบันทึก สมนัยกับสัญญาณครั้งแรก-และ-ครั้งเดียวของผู้ที่ไม่ใช่ผู้นับหนึ่งคนที่แตกต่างกันพอดีเป๊ะ: ไม่มีใครส่งสัญญาณสองครั้ง และไม่มีสัญญาณใดสูญหายได้ เพราะมีเพียงผู้นับเท่านั้นที่เคยปิดหลอด บัญชี 99 จึงแปลว่าคนอื่นที่แตกต่างกัน 99 คนได้มาเยือนแล้ว — และตัวผู้นับเองทำให้ครบ 100 หลอดไฟคือช่องสัญญาณขนาดหนึ่งบิต; โพรโทคอลนี้เรียงส่งสาร 99 ฉบับผ่านมัน ทีละฉบับ
ราคาที่ต้องจ่ายคือความอดทน ซิมูเลชันประเมินเวลารอคาดหมายไว้ราว 10,300 วัน — ยี่สิบแปดปี — ส่วนใหญ่หมดไปกับหลอดที่ติดค้างเปล่าประโยชน์ รอการเยือนสุ่มครั้งถัดไปของผู้นับ โพรโทคอลที่เร็วกว่ามีอยู่จริง: แผนหลายขั้นที่นักโทษถือ "โทเคน" มูลค่าไต่ระดับ ลดเวลาคาดหมายลงได้มาก (ตระกูลนี้ถูกวิเคราะห์โดย Dehaye, Ford & Segerman, Mathematical Intelligencer, 2003) แต่แผนผู้นับเดี่ยวคือบทพิสูจน์บัญญัติของความเป็นไปได้ และอาร์กิวเมนต์ความถูกต้องของมันจุลงในสี่ประโยค — ความเหมาะที่สุดในแบบของมันเอง ปริศนานี้ยังหนุ่มมากสำหรับความคลาสสิก: ถูกโพสต์ครั้งแรกในนิวส์กรุ๊ป rec.puzzles เมื่อ 24 กรกฎาคม 2002
ท่า — ออกแบบโพรโทคอลหนึ่งบิต. เมื่อสถานะร่วมจิ๋วเหลือเกิน จงเลิกถามว่า "ฉันนิรนัยอะไรได้บ้าง?" แล้วถามว่า "เราตกลงโพรโทคอลอะไรกันไว้ล่วงหน้าได้บ้าง?" แต่งตั้งผู้รวบยอดหนึ่งคน; ทำให้ทุกสัญญาณยิงได้นัดเดียวและปราศจากความกำกวม นี่คือวิศวกรรมระบบกระจาย (distributed systems) ที่ถูกเล่าเป็นนิทาน
★★★★★ 37 · นักโทษ 100 คนกับกล่อง 100 ใบ
นักโทษหนึ่งร้อยคนเดิม ในห้องที่โหดร้ายกว่า กล่องหนึ่งร้อยใบเรียงเป็นแถว; ข้างในคือหมายเลข 1 ถึง 100 ในการเรียงสับเปลี่ยนสุ่มอย่างสม่ำเสมอ ใบละหนึ่งหมายเลข นักโทษแต่ละคน ตามลำพัง เปิดกล่องได้ห้าสิบใบเพื่อค้นหาหมายเลขของตัวเอง จากนั้นห้องถูกจัดคืนสภาพเหมือนเดิมเป๊ะ และเขาออกไปอีกประตูหนึ่ง ส่งสัญญาณอะไรไม่ได้ทั้งสิ้น ถ้านักโทษ*ทุกคน*พบหมายเลขของตัวเอง ทุกคนเป็นอิสระ; พลาดเพียงคนเดียว ตายทั้งหมด หากเปิดกล่องแบบสุ่ม นักโทษแต่ละคนสำเร็จด้วยความน่าจะเป็น 1/2 กลุ่มจึงรอดด้วยความน่าจะเป็น (1/2)¹⁰⁰ ≈ 8 × 10⁻³¹ — เรียกมันว่าไม่มีวัน มีกลยุทธ์ที่ความน่าจะเป็นในการรอดเกิน 31 เปอร์เซ็นต์อยู่จริง จงหามัน
อ่านอีกครั้ง: จาก 10⁻³⁰ สู่เกือบหนึ่งในสาม ทีนี้ ออกล่า
เฉลย. การสื่อสารเป็นไปไม่ได้ ดังนั้นการประสานงานต้องถูกลักลอบผ่านโครงสร้างร่วมเพียงหนึ่งเดียวที่มีอยู่: เนื้อในของกล่องนั่นเอง กลยุทธ์วัฏจักร: นักโทษหมายเลข k เปิดกล่อง k ก่อน ข้างในมีเลข j สักตัว; เขาเปิดกล่อง j ต่อ; อ่านเจอ m ก็เปิดกล่อง m — ไล่ตามตัวชี้ไปเรื่อยๆ นั่นคือกลยุทธ์ทั้งหมด
ทำไมมันได้ผล: ความสัมพันธ์กล่อง-สู่-เนื้อในคือการเรียงสับเปลี่ยน และทุกการเรียงสับเปลี่ยนแยกสลายตัวออกเป็นวัฏจักร การเริ่มที่กล่อง k แล้วไล่ตามตัวชี้คือการเดินไปตามวัฏจักรที่บรรจุ k อยู่พอดี และการเดินนั้นการันตีว่าจะไปถึงกล่องที่ถือหมายเลข k — ตัวชี้ที่ปิดห่วงโซ่ ดังนั้นนักโทษ k สำเร็จก็ต่อเมื่อ*วัฏจักรของเขายาวไม่เกินห้าสิบ*เท่านั้น ชะตาของเขาเลิกเป็นการพนันอิสระห้าสิบตา และกลายเป็นคำถามข้อเดียวว่าด้วยรูปทรงของการเรียงสับเปลี่ยน
เมื่อได้อย่างนั้น ชะตาของทั้งกลุ่มก็ยุบรวมลงบนเหตุการณ์ระดับสากลเหตุการณ์เดียว: ทั้งหนึ่งร้อยสำเร็จ ก็ต่อเมื่อการเรียงสับเปลี่ยนไม่มีวัฏจักรยาวเกิน 50 วัฏจักรยาวมีโอกาสแค่ไหน? สำหรับความยาว k > 50 ใดๆ วัฏจักรเช่นนั้นมีได้อย่างมากหนึ่งวง (สองวงต้องใช้สมาชิกเกิน 100 ตัว) และความน่าจะเป็นที่การเรียงสับเปลี่ยนสุ่มของ 100 จะบรรจุวัฏจักรความยาว k คือ 1/k พอดี ดังนั้นความน่าจะเป็นของความล้มเหลวคือ 1/51 + 1/52 + ⋯ + 1/100 = H₁₀₀ − H₅₀ ≈ ln 2 ≈ 0.693 และการรอดชีวิตคือ 1 − (H₁₀₀ − H₅₀) = 0.31183 คำนวณได้แม่นเป๊ะ ตัวเลขนี้แทบไม่เสื่อมถอยเมื่อคุกโตขึ้น: ลิมิตคือ 1 − ln 2 ≈ 30.7 เปอร์เซ็นต์ ไม่ว่านักโทษจะมีหนึ่งร้อยคนหรือหนึ่งพันล้านคน
ทีนี้ถึงส่วนที่ควรนั่งนิ่งๆ อยู่กับมัน ลองถามนักโทษคนใดคนหนึ่งว่ากลยุทธ์นี้ทำอะไรให้*เขา*บ้าง: วัฏจักรที่ผ่านกล่องของเขามีโอกาสเท่ากันที่จะยาวเท่าใดก็ได้ตั้งแต่ 1 ถึง 100 ดังนั้นความน่าจะเป็นสำเร็จส่วนตัวของเขาคือ 50/100 — เท่ากับ 1/2 พอดี ไม่ต่างจากการเดาสุ่มเลยสักนิด แต้มต่อของปัจเจกไม่กระเตื้องขึ้นแม้แต่คนเดียว สิ่งที่เปลี่ยนคือ*สหสัมพันธ์* นักเดาสุ่มล้มเหลวเป็นอิสระจากกัน ใครสักคนจึงล้มเหลวแทบแน่นอน; นักไล่วัฏจักรล้มเหลวพร้อมกันหรือไม่ล้มเลย เพราะสมาชิกทุกคนของวัฏจักรที่ยาวเกินล้มพร้อมกันทั้งยวง และเมื่อไม่มีวัฏจักรยาว ก็ไม่มีใครล้มเลย กลยุทธ์นี้ต้อนชะตาหนึ่งร้อยชีวิตขึ้นไปกองอยู่บนการโยนเหรียญครั้งเดียว ว่าด้วยรูปทรงของการเรียงสับเปลี่ยนชุดเดียว และมันแทบไร้ผู้ท้าชิง: Curtin กับ Warshauer (2006) ต่อยอดการวิเคราะห์ดั้งเดิมของ Miltersen กับ Gál แสดงว่าไม่มีกลยุทธ์ใดทำได้ดีกว่านี้อย่างมีนัยสำคัญ
ปัญหานี้ถือกำเนิดในวิทยาการคอมพิวเตอร์เชิงทฤษฎี — Peter Bro Miltersen ตั้งมันขึ้น (ร่วมกับ Anna Gál) ที่ ICALP 2003 ในฐานะกลไกชิ้นหนึ่งของบทพิสูจน์ขอบเขตล่างของโครงสร้างข้อมูล และเพื่อนร่วมงานของเขา Sven Skyum คือผู้ค้นพบกลยุทธ์วัฏจักร มันถูกขนานนามอย่างมีน้ำหนักน่าเชื่อว่า เป็นผลลัพธ์ที่ฝืนสัญชาตญาณที่สุดในคณิตศาสตร์บันเทิง
ท่า — ผูกชะตาให้สัมพันธ์กัน. เมื่อความสำเร็จอิสระคูณทบกันเป็นหายนะ จงออกแบบใหม่ให้ทุกคนสำเร็จหรือล้มเหลวบนเหตุการณ์เดียวกัน มีท่าที่สองติดสอยมาด้วย: ยัดเยียดโครงสร้างให้ความสุ่ม — การแยกสลายเป็นวัฏจักรของการเรียงสับเปลี่ยนนอนรออยู่ตรงนั้นมาตลอด รอเพียงใครสักคนอ่านกล่องเป็นตัวชี้
★★★★★ 10 · ชาวเกาะตาสีฟ้า
เกาะแห่งหนึ่งมีนักตรรกะสมบูรณ์แบบสองร้อยคน: ตาสีฟ้าหนึ่งร้อย ตาสีน้ำตาลหนึ่งร้อย ไม่มีกระจก ไม่มีผืนน้ำที่สะท้อนเงา และสีตาไม่เคยถูกพูดถึง — ข้อห้ามที่มีเขี้ยวเล็บจริง ทุกคนเห็นดวงตาของทุกคนอื่น; ไม่มีใครรู้สีตาของตนเอง กฎหมายมีว่า: ณ เที่ยงคืนหลังจากที่คุณ*รู้*ว่าตาของตัวเองสีฟ้า คุณต้องออกจากเกาะไปตลอดกาล ทั้งหมดนี้ — ตัวกฎหมาย ความเป็นนักตรรกะสมบูรณ์แบบของทุกคน — เป็นความรู้ร่วม (common knowledge) วันหนึ่งผู้มาเยือนกล่าวต่อทั้งเกาะพร้อมกัน: "ข้าพเจ้าเห็นคนตาสีฟ้าอย่างน้อยหนึ่งคน" ชาวเกาะทุกคนเห็นคนตาสีฟ้าอย่างน้อยเก้าสิบเก้าคนอยู่แล้ว; ผู้มาเยือนดูจะไม่ได้พูดอะไรใหม่เลย จะเกิดอะไรขึ้น?
ผู้มาเยือนเพิ่มอะไรเข้ามากันแน่? นั่งอยู่กับคำถามนั้นก่อน
เฉลย. ชาวเกาะตาสีฟ้าทั้งหนึ่งร้อยคนออกจากเกาะพร้อมกัน ณ เที่ยงคืนของวันที่หนึ่งร้อย
ไต่ขึ้นจากพื้น ชาวเกาะตาสีฟ้าหนึ่งคน: เธอมองไปทางไหนก็ไม่เห็นตาสีฟ้า คำประกาศจึงหมายถึงเธอได้คนเดียว เธอออกไปในเที่ยงคืนแรก สองคน: แต่ละคนเห็นคนตาสีฟ้าหนึ่งคนพอดี และให้เหตุผลว่า "ถ้าตาฉันสีน้ำตาล เขาก็อยู่ลำพัง — เขาจะคิดออกแล้วออกไปคืนนี้" ไม่มีใครออก เพราะต่างคนต่างรอกันและกัน ความเงียบนั้นดังกึกก้อง: บัดนี้แต่ละคนรู้แล้วว่ามีดวงตาสีฟ้าคู่ที่สอง และรู้ว่าเป็นของใคร ทั้งคู่ออกไปในเที่ยงคืนที่สอง สามคน: ชาวเกาะตาสีฟ้าแต่ละคนเห็นสองคน และให้เหตุผลว่า "ถ้าฉันสีน้ำตาล สองคนนั้นจะคลี่คลายกันเองภายในคืนที่สอง" เที่ยงคืนที่สองผ่านไป เกาะยังอยู่กันครบ ทั้งสามจึงรู้; พวกเขาออกไปคืนที่สาม การอุปนัยวิ่งบนราง: ชาวเกาะตาสีฟ้า n คนออกจากเกาะ ณ เที่ยงคืนที่ n เมื่อมีหนึ่งร้อยคน — เก้าสิบเก้าเที่ยงคืนแห่งความเงียบ แล้วจึงการอพยพครั้งใหญ่ในคืนที่หนึ่งร้อย
แต่ผู้มาเยือน*เพิ่ม*อะไรกันแน่? ทุกคนเห็นตาสีฟ้าอยู่แล้ว นี่คือคำตอบที่ซื่อสัตย์ และมันคือปริศนาทั้งข้อ: ก่อนคำประกาศ "มีคนตาสีฟ้า" เป็นสิ่งที่ทุกคนรู้ — แต่มันไม่ใช่ความรู้ร่วม (common knowledge) ไล่ตามการซ้อนชั้นดู ชาวเกาะตาสีฟ้าคนหนึ่งเห็นคนอื่น 99 คน เขารู้ว่าแต่ละคนในนั้นเห็นอย่างน้อย 98 เขารู้ว่าพวกเขารู้ว่าคนอื่นๆ เห็นอย่างน้อย 97… "ทุกคนรู้ว่าทุกคนรู้" แต่ละชั้นเผาผลาญส่วนเผื่อไปหนึ่งชาวเกาะ และที่ความลึก 99 โซ่ก็หยั่งก้นลงในชาวเกาะสมมุติคนหนึ่งซึ่ง — ภายในจินตนาการซ้อนชั้นทั้งหมดนั้น — อาจไม่เห็นดวงตาสีฟ้าเลยสักคู่ ข้อความที่ลึก 99 ชั้นนั้น*เท็จ* คำประกาศของผู้มาเยือน — ทุกคนได้ยิน ทุกคนเห็นว่าทุกคนได้ยิน — ทำให้ "มีคนตาสีฟ้า" เป็นจริงที่ทุกความลึกพร้อมกันในคราวเดียว นั่นคือสิ่งใหม่: ไม่ใช่ข้อเท็จจริงเกี่ยวกับดวงตา แต่เป็นข้อเท็จจริงเกี่ยวกับความรู้ว่าด้วยความรู้
นับจากนั้น เที่ยงคืนอันเงียบงันแต่ละคืนก็เป็นประกาศสาธารณะในตัวมันเอง — "ยังไม่มีใครรู้" — และการอุปนัยไต่ขึ้นคืนละขั้นบันได จนแตะถึงความจริง ถ้อยแถลงสาธารณะเปลี่ยนโลกได้ ทั้งที่เพิ่มสารสนเทศชั้นที่หนึ่งเป็นศูนย์ ปริศนานี้สืบเชื้อสายจากปัญหาใบหน้าเปื้อนของ Littlewood (A Mathematician's Miscellany, 1953) และภรรยานอกใจสี่สิบคนของ Gamow กับ Stern (Puzzle-Math, 1958); อาภรณ์ฉบับตาสีฟ้าของมันแพร่ไปในทศวรรษ 2000 โดยเฉพาะผ่าน xkcd และบทความบล็อกปี 2008 ของ Terence Tao
ท่า — อุปนัยบนความรู้ร่วม. "ทุกคนรู้ X" กับ "ทุกคนรู้ว่าทุกคนรู้ X…" คือสถานะของโลกที่ต่างกันคนละใบ และโพรโทคอล ตลาด กับการเผชิญหน้ากันล้วนวิ่งอยู่บนความต่างนั้น เมื่อเหตุการณ์สาธารณะเปลี่ยนพฤติกรรมโดยไม่เปลี่ยนข้อเท็จจริงส่วนตัวของใครเลย จงมองหาความลึกของความรู้ที่มันเพิ่งเติมจนครบ
★★★★★ 49 · ปริศนาเป็นไปไม่ได้ของ Freudenthal
จำนวนเต็มสองจำนวน x กับ y ถูกเลือกขึ้น โดย 1 < x < y และ x + y ≤ 100 คุณ P ได้รู้เพียงผลคูณ; คุณ S ได้รู้เพียงผลบวก บทสนทนาต่อไปนี้เกิดขึ้น ทุกถ้อยคำเป็นจริงและทั้งคู่ได้ยิน:
P: "ผมไม่รู้ว่าตัวเลขคืออะไร" S: "ผมรู้อยู่แล้วว่าคุณไม่รู้" P: "ตอนนี้ผมรู้แล้ว" S: "ตอนนี้ผมก็รู้แล้วเหมือนกัน"
จงหา x กับ y — จากบทสนทนาเพียงลำพัง
มันเคยถูกเรียกว่าปัญหาที่เป็นไปไม่ได้ มันไม่ใช่หรอก — เกือบไปเท่านั้น
เฉลย. ไม่มีสักคำที่เอ่ยถึงตัวเลข ทว่าแต่ละบรรทัดคือข้อเท็จจริงแข็งโป๊กว่าสารสนเทศของผู้พูดอนุญาตให้ทำอะไรได้ — และข้อเท็จจริงแต่ละข้อกรองคู่ผู้สมัครลงไปเรื่อยๆ
บรรทัด 1 — P ไม่รู้ ผลคูณของเขาต้องแยกตัวประกอบได้อย่างกำกวมภายใต้เงื่อนไข หากมันเป็น สมมุติ 35 = 5 × 7 จำนวนเฉพาะสองตัว เขาย่อมรู้ทันที ผลคูณทุกตัวที่แยกได้แบบเดียวตายที่บรรทัดนี้
บรรทัด 2 — S *รู้อยู่แล้ว*ว่า P ไม่รู้ ไม่ใช่เดา: รู้ จากผลบวกเพียงลำพัง ดังนั้นการแตกผลบวกของ S ทุกแบบที่ยอมรับได้ ต้องให้ผลคูณที่กำกวมทั้งหมด ข้อนี้โหดเหี้ยม ผลบวกใดที่แตกเป็นจำนวนเฉพาะสองตัวได้ ตกรอบ — ผลคูณของการแตกแบบนั้นจะบอก P จนหมดเปลือก — และที่ขนาดนี้ ผลบวกคู่ทุกตัวแตกเช่นนั้นได้ (ตรวจตรงๆ ได้เลย; ไม่ต้องพึ่งข้อความคาดการณ์ใด) ร่อนผู้รอดที่เป็นจำนวนคี่แล้วเหลือผลบวกสิบตัวพอดี: {11, 17, 23, 27, 29, 35, 37, 41, 47, 53}
บรรทัด 3 — ตอนนี้ P รู้แล้ว การได้ยินบรรทัด 2 บอก P ว่าผลบวกอยู่ในบัญชีสิบตัวนั้น; ผลคูณของเขาต้องเข้ากันได้กับสมาชิก*เพียงหนึ่งเดียว*เท่านั้น ดูมันทำงานกับคำตอบสุดท้าย: ผลคูณ 52 = 4 × 13 ผลบวก 17 — อยู่ในบัญชี; หรือ 2 × 26 ผลบวก 28 — เป็นคู่ ตกไป เหลือผู้รอดหนึ่งเดียว P จึงประกาศว่ารู้
บรรทัด 4 — ตอนนี้ S ก็รู้ด้วย ในบรรดาการแตกทั้งหมดของผลบวกของเขา ต้องมีเพียงแบบเดียวที่เพิ่งกลายเป็นแบบที่ P แก้ได้ ณ บรรทัด 3 ลองรันผลบวกของเขา 17: การแตก (2,15) มีผลคูณ 30 = 2 × 15 (ผลบวก 17 อยู่ในบัญชี) แต่ก็เท่ากับ 5 × 6 (ผลบวก 11 ซึ่ง*ก็*อยู่ในบัญชี) — P แบบนั้นจะยังติดแหง็ก ดังนั้น (2,15) ถูกคัดทิ้ง (3,14): ผลคูณ 42 กำกวมระหว่างผลบวก 17 กับ 23 ตก (5,12): 60 ฉีกใจระหว่าง 17 กับ 23 (7,10): 70 ฉีกระหว่าง 17 กับ 37 (8,9): 72 ฉีกระหว่าง 17 กับ 27 (6,11): 66 ฉีกระหว่าง 17 กับ 35 เหลือรอดเพียง (4,13) — ดังนั้น S ผู้ถือ 17 จึงรู้แล้ว และการทวนสอบด้วยเครื่องปิดวงจรให้สนิท: สำหรับผลบวก*ตัวอื่นทุกตัว*ในบัญชี มีการแตกที่รอดบรรทัด 3 อยู่สองแบบขึ้นไป บรรทัด 4 จึงย่อมเป็นเท็จ ผลบวกคือ 17 ผลคูณคือ 52: x = 4, y = 13
บทสนทนาที่ดูไร้เนื้อหากลับกำหนดตัวเลขสองตัวได้อย่างหนึ่งเดียว วันเกิดของ Cheryl ในบทที่ 5 คือทายาทป๊อปไวรัลของปริศนาข้อนี้ รันด้วยเครื่องยนต์เดียวกันที่แรงดันต่ำกว่า Hans Freudenthal ตีพิมพ์ต้นฉบับใน Nieuw Archief voor Wiskunde, 1969; Gardner นำมาเล่าเป็นภาษาอังกฤษในทศวรรษถัดมาในชื่อ "the impossible problem" — เป็นไปไม่ได้แค่โดยรูปลักษณ์ เพราะความไม่รู้ที่ถูกประกาศออกมา ดูราวกับการไร้ซึ่งสารสนเทศ
ท่า — ขุดเหมืองจากอภิถ้อยแถลง. "ผมไม่รู้" กับ "ผมรู้อยู่แล้วว่าคุณไม่รู้" คือข้อเท็จจริงทางคณิตศาสตร์เกี่ยวกับเซตสารสนเทศ — ตัวกรองที่คมกริบเท่าสมการ เมื่อนักเจรจา ตลาด หรือเครื่องจักรประกาศสิ่งที่มัน*ยังสรุปไม่ได้* คำประกาศนั้นคือข้อมูล ไม่มีอะไรถูกพูดเกี่ยวกับตัวเลขเลย และนั่นแหละคือข้อมูล
★★★★ 50 · การแขวนคอที่ไม่คาดฝัน
ผู้พิพากษามีคำสั่งในวันอาทิตย์: "เจ้าจะถูกแขวนคอตอนเที่ยงของวันธรรมดาวันหนึ่งในสัปดาห์ที่จะถึงนี้ — และการแขวนคอจะเป็นเรื่องไม่คาดฝัน เจ้าจะไม่รู้วันล่วงหน้า" นักโทษให้เหตุผล: "พวกเขาแขวนฉันวันศุกร์ไม่ได้: พอถึงคืนวันพฤหัส เมื่อสี่วันผ่านพ้นไป ฉันย่อมรู้ว่ามันกำลังจะมา วันศุกร์ตกไป แต่เมื่อวันศุกร์ถูกขีดฆ่า วันพฤหัสก็กลายเป็นวันสุดท้ายที่เป็นไปได้ ดังนั้นพอถึงคืนวันพุธฉันย่อมรู้ — วันพฤหัสก็ตกไปด้วย" วันแล้ววันเล่า ทั้งสัปดาห์พังครืนลง และนักโทษก็สรุปอย่างโล่งอกว่าโทษนี้ไม่มีทางถูกลงมือได้เลย วันพุธตอนเที่ยง เพชฌฆาตมาถึง นักโทษประหลาดใจอย่างสิ้นเชิง คำสั่งนั้น ในบั้นปลาย เป็นจริง ข้อบกพร่องในการให้เหตุผลของเขาอยู่ตรงไหน?
ปรัชญาเกือบแปดสิบปียังปิดคดีข้อนี้ไม่ลง
เฉลย. ไม่มี — อย่างน้อยก็ไม่มีข้อยุติ — และหนังสือเล่มนี้จะไม่แสร้งว่ามี สิ่งที่ตกลงกันได้มีเท่านี้: อาร์กิวเมนต์คัดวันทิ้งของนักโทษ กับการที่คำสั่งเป็นจริงขึ้นมาในท้ายที่สุด จะถูกต้องพร้อมกันทั้งคู่ไม่ได้ และรอยตำหนิต้องนั่งอยู่ที่ไหนสักแห่งในการให้เหตุผลว่าด้วย*การรู้* แต่ตรงไหนกันแน่ ยังคงเป็นสมรภูมิช่วงชิงกันในบทความวิชาการกว่าห้าสิบชิ้น
การวินิจฉัยมีสามตระกูล ไม่มีตระกูลใดเป็นฉันทามติ Quine (1953) โจมตีฐานของการอุปนัย: การคัดวันศุกร์ทิ้งต้องการให้คำสั่งไม่เพียงเป็นจริง แต่ต้อง*พึ่งพิงได้อย่างรู้ได้ ณ ทุกจุดเวลาในอนาคต* — และ "คำสั่งจะเป็นจริง" กับ "ฉันเอาคำสั่งมาใช้พิงในการให้เหตุผลของตัวเองได้" เป็นคนละคำกล่าวอ้าง ที่ถูกเหมารวมเข้าด้วยกันอย่างเงียบเชียบ สำนักตรรกศาสตร์เชิงญาณ (epistemic logic) จัดรูป "ความไม่คาดฝัน" ด้วยตัวดำเนินการความรู้ และพบว่าคำประกาศนั้นไม่เสถียรเชิงอ้างถึงตัวเอง: ข้อความที่เป็นจริงได้แต่ไม่อาจรู้ได้ว่าจริง จนการที่นักโทษหยิบมันไปใช้เองคือสิ่งที่ทำลายมัน — Sorensen (1988) เรียกกรณีวันสุดท้ายว่า "blindspot" ส่วนสำนักลดทอนยักไหล่: สำหรับสัปดาห์ที่มีวันเดียว คำสั่งขัดแย้งกันโต้งๆ สำหรับห้าวัน มัน "ยืนยันได้โดยประมาณ" และสัญชาตญาณก็ละเลงความต่างนั้นจนกลายเป็นรัศมีเรืองรองของพาราด็อกซ์
ว่ากันว่าปัญหานี้เริ่มชีวิตในฐานะประกาศป้องกันภัยฝ่ายพลเรือนยามสงครามของสวีเดน — การซ้อมที่จะจัดขึ้นสัปดาห์หน้า ในวันที่ไม่มีใครทำนายได้ — และถูกขบคิดต่อกันมาจน D. J. O'Connor นำมันลงวารสาร Mind ในปี 1948 คอลัมน์ปี 1963 ของ Gardner ทำให้มันโด่งดัง; Blindspots (1988) ของ Sorensen มอบหนังสือทั้งเล่มให้มัน บัญชีคดีนี้ยังเปิดอยู่
ทำไมจึงปิดห้องบอสด้วยบอสที่ยังไม่มีใครโค่น? เพราะแนวเรื่องควรซื่อสัตย์กับขอบเขตของตัวเอง และเพราะบทเรียนอยู่รอดได้แม้เฉลยจะขาดหาย ปริศนาข้ออื่นทุกข้อในห้องนี้วิ่งอยู่บนความรู้ที่ประพฤติตามกฎ — ถูกนับผ่านหลอดไฟ ถูกซ้อนชั้นบนเกาะ ถูกขุดออกจากบทสนทนา ตรงนี้คือประตูที่แปะป้ายว่า ความรู้เกี่ยวกับความรู้ในอนาคตของตนเอง และเบื้องหลังบานประตูนั้น พื้นหายไป การตอบสนองที่ซื่อสัตย์ต่อปัญหาเปิดคือประโยคที่หนังสือเล่มนี้พยายามมาตลอดทั้งเล่ม เพื่อให้ได้สิทธิ์พูดมันออกมาตรงๆ: ยังไม่มีใครรู้
ท่า — ความรู้ทำลายตัวเองได้. ถ้อยแถลงว่าด้วยสิ่งที่คุณ*จะรู้* ไม่ใช่ข้อเท็จจริงธรรมดา; การป้อนมันกลับเข้าการอนุมานของตัวเองอาจทำให้มันเป็นโมฆะ จงเคารพความต่างเชิงชนิดระหว่างสิ่งที่เป็นจริง กับสิ่งที่รู้ได้ว่าจริง — คำประกาศทำนอง "คุณจะถูกตรวจสอบ โดยไม่แจ้งล่วงหน้า" มีน้ำหนักจริงในทางกฎหมายและความมั่นคง และปริศนาข้อนี้คือหลักฐานยืนยงว่า สิ่งเหล่านั้นอาจถูกก่อขึ้นบนอากาศ
ท่าที่ตอนนี้เป็นของคุณแล้ว
- รีดสารสนเทศสูงสุดต่อการทดสอบ (★★★★ 8, ลูกบอลสิบสองลูก) — ทำงบผลลัพธ์ก่อน (3³ ≥ 24) แล้วให้ทุกการทดสอบผ่าผู้รอดออกอย่างเท่าเทียม
- แก้เกมช่วงปลายก่อน (★★★★ 44, โจรสลัด) — ทอดสมอตรงที่เกมจิ๊บจ๊อย; ม้วนย้อนกลับ ตีราคาแต่ละเสียงด้วยอนาคตทางเลือกของมัน
- ออกแบบโพรโทคอลหนึ่งบิต (★★★★ 9, หลอดไฟ) — สถานะร่วมอันจิ๋วเรียกหาโพรโทคอลที่ตกลงกันล่วงหน้า ไม่ใช่การนิรนัย; แต่งตั้งผู้รวบยอด
- ผูกชะตาให้สัมพันธ์กัน (★★★★★ 37, กล่อง) — เมื่อความสำเร็จแบบอิสระสิ้นหวัง จงแขวนความสำเร็จของทุกคนไว้บนเหตุการณ์ร่วมเดียว
- อุปนัยบนความรู้ร่วม (★★★★★ 10, ชาวเกาะ) — "ทุกคนรู้" กับ "ทุกคนรู้ว่าทุกคนรู้" คือคนละโลก
- ขุดเหมืองจากอภิถ้อยแถลง (★★★★★ 49, Freudenthal) — ความไม่รู้ที่ถูกประกาศคือข้อมูล; กรองบนเซตสารสนเทศ
- ความรู้ทำลายตัวเองได้ (★★★★ 50, การแขวนคอ) — ความจริงว่าด้วยความรู้ในอนาคตอาจไม่รอดจากการถูกนำไปใช้
ทั้งเจ็ดนี้คือสันเขายอดสุดของภาค II เหนือไปกว่าท่าเดี่ยวๆ ของแต่ละข้อ พวกมันฝึกอุปนิสัยอย่างหนึ่ง: ความอดทนต่อโซ่เหตุผลยาวที่ห้ามรั่วสักข้อ ความเคารพต่อคำตอบที่หยามสัญชาตญาณแต่ก็จริงอยู่ดี และ — เพียงครั้งเดียว ในตอนท้าย — ความสงบนิ่งพอที่จะทิ้งคำถามไว้ให้เปิดอยู่ เพราะมันยังเปิดอยู่จริงๆ ภาค III จะพาไปเยือนผู้คนที่ไต่เกรดระดับนี้เป็นกีฬา แล้วแกะการฝึกของพวกเขาออกมาเป็นชิ้นๆ
บทถัดไป · 13 / 21แชมป์คิดอย่างไร