สายตานักจำลองแบบ
ตระกูลสุดท้ายไม่โจมตีปัญหา; มันเปลี่ยนว่าปัญหา*คือ*อะไร การแทนเสียใหม่ (re-representation) — เรื่องเล่ากลายเป็นกราฟ ผลบวกกลายเป็นเซต ปริศนากลายเป็นค่าเฉลี่ย — คือท่าที่เงียบที่สุดในคลังแสงและทรงพลังที่สุด: หลังการแปลที่ถูกต้อง ปัญหาที่ลือชื่อว่ายากก็แก้ตัวเองจนจบ และนี่ยังเป็นสนามที่นักแก้มนุษย์ถือแต้มนำเครื่องจักรกว้างที่สุดด้วย บทนี้ปิดท้ายด้วยฉากใหญ่เลื่องชื่อสามฉาก เล่าพร้อมชำระประวัติให้ตรงตามจริง
เรื่องเล่า → โครงสร้าง
เครื่องมือ. หล่อปัญหาขึ้นรูปใหม่ให้เป็นอินสแตนซ์ของนามธรรมที่รู้จักและแก้ไว้แล้ว: กราฟ โครงข่ายการไหล การจับคู่ วิถีสั้นสุด ระบบสมภาค การแก้โจทย์คือการแปลภาษา — บอกให้ได้ว่าจุดยอดคืออะไร เส้นเชื่อมคืออะไร และทฤษฎีบทคลาสสิกข้อไหนใช้ได้แล้ว ณ บัดนี้ การเขียนโปรแกรมแข่งขันระดับยอดคือกีฬาแห่งการจดจำการลดรูป (reduction); ปัญหายากส่วนใหญ่คือแก่นที่รู้จักกันดี สวมชุดแฟนซีมา
กลิ่น. เอนทิตีที่มีความสัมพันธ์เป็นคู่ๆ: กราฟกำลังมา "จัด X ให้ Y" ใต้เงื่อนไขความเข้ากันได้: การจับคู่สองฝั่ง (bipartite matching) "ปริมาณผ่านทาง" "คอขวด" "ตัดขาดพวกมัน": max-flow, min-cut สถานะต่อเนื่องพร้อมทรานซิชันที่ถูกกติกา: วิถีสั้นสุดบน*ปริภูมิสถานะ* ไม่ใช่บนพื้นที่กายภาพ สัญญาณเมตา: เรื่องเล่าต้านการโจมตีซึ่งหน้า แต่ทุกประโยคฟังเหมือนกำลังบรรยายโครงสร้างอะไรสักอย่าง รีเฟล็กซ์: ตั้งชื่อจุดยอด
ปริศนาแรกสุดของหนังสือเล่มนี้แอบเป็นตัวอย่างง่ายของหมวดนี้มาตลอด หมาป่า แพะ กะหล่ำปลี ของบทที่ 1 กลายเป็น: จุดยอด = การกระจายตัว*ที่ถูกกติกา*ของ {ชาวนา, หมาป่า, แพะ, กะหล่ำปลี} บนสองฝั่งน้ำ — สถานะดิบ 16 ถูกกติกา 10; เส้นเชื่อม = การข้ามฟากหนึ่งเที่ยว คำถามกลายเป็นวิถีสั้นสุด; breadth-first search หาเส้นทาง 7 เที่ยวข้ามเจอ แถม*รับรอง*ว่าน้อยสุด — และอาฮ่าอันลือลั่น การพาแพะย้อนกลับ ก็กลายเป็นแค่เส้นเชื่อมธรรมดาเส้นหนึ่ง ถูกข้ามผ่านโดยการเสิร์ชโง่ๆ ตัวเดียวกัน การปิ๊งอยู่ที่ขั้นจำลองแบบ; หลังจากนั้นไม่ต้องใช้การปิ๊งอีกเลย ท่าเดียวกันนี้แก้ลูกบาศก์ Rubik ปริศนาเลื่อนแผ่น และการทวนสอบโพรโทคอล: วิถีสั้นสุดในกราฟของ*คอนฟิกูเรชัน* ไม่ใช่ของสถานที่
★★★★ · ยามในวัง
พื้นวังขนาด 4 × 4 มีสมบัติอยู่ที่ช่อง (1,1), (1,3), (2,2), (3,1), (3,3) — แถว, คอลัมน์ ยามหนึ่งคนลาดตระเวนเต็มหนึ่งแถวหรือเต็มหนึ่งคอลัมน์ จงหาจำนวนยามน้อยที่สุดที่คุ้มกันสมบัติได้ครบทุกชิ้น และ*พิสูจน์*ว่าน้อยที่สุดจริง
หยุดตรงนี้ อะไรกันแน่คือจุดยอด?
เฉลย. ไปทางสองฝั่ง: จุดยอดฝั่งซ้ายคือแถว จุดยอดฝั่งขวาคือคอลัมน์ และสมบัติแต่ละชิ้นคือเส้นเชื่อมที่โยงแถวของมันเข้ากับคอลัมน์ของมัน ยามคือ*จุดยอด*; การคุ้มกันสมบัติครบทุกชิ้นคือการแตะทุกเส้นเชื่อม: vertex cover ในกราฟสองฝั่ง vertex cover น้อยสุดเท่ากับ matching มากสุด — ทฤษฎีบทของ König, 1931 ขอบเขตล่าง: สมบัติ (1,1), (2,2), (3,3) เป็น matching ขนาด 3 ไม่ใช้แถวร่วมกัน ไม่ใช้คอลัมน์ร่วมกัน และยามหนึ่งคนคุ้มเส้นเชื่อมของ matching ได้อย่างมากหนึ่งเส้น — 3 คนจึงถูกบังคับ ขอบเขตบน: แถว 1, 2, 3 คุ้มสมบัติครบทั้งห้า น้อยสุด: 3 ∎ (ตรวจตรงๆ ว่าสองคนไม่พอ: จะคุ้ม (2,2) ต้องใช้แถว 2 หรือคอลัมน์ 2 ซึ่งไม่แตะสมบัติมุมทั้งสี่ชิ้นเลย — และเส้นเดียวคุ้มสี่ชิ้นมุมนั้นได้อย่างมากสอง)
ไม่มีตรงไหนในเรื่องเล่าพูดคำว่า "กราฟ" และการแปลที่ชนะ — สมบัติ = เส้นเชื่อม ไม่ใช่จุดยอด — คือเนื้อแท้ของทักษะการจำลองแบบล้วนๆ พอแปลเสร็จ ทฤษฎีบทปี 1931 ก็ปิดฉากการต่อสู้ให้ พร้อมใบรับรองแนบมา: ตัว matching นั่นแหละ*คือ*พยานของขอบเขตล่าง
ท่า — ตั้งชื่อจุดยอด. เลือกอะตอมให้ถูก แล้วทฤษฎีบทมักรออยู่ตรงนั้นแล้ว
เครื่องจักรกับท่านี้. การรัน max-flow นั้นจิ๊บจ๊อย; *การตัดสินว่าเรื่องเล่านี้เป็นปัญหาการไหล*คือ abduction บนปริภูมิการแทนแบบเปิด — โมเดลจำชุดแฟนซีที่เคยอ่านผ่านตาได้ แต่พลาดท่ากับการปลอมตัวสดใหม่
แยกกรณี กับ WLOG
เครื่องมือ. เมื่อไม่มีอาร์กิวเมนต์เดียวที่คลุมได้ทั้งหมด จงแบ่งปริภูมิเป็นกรณีจำนวนจำกัดแล้วสังหารทีละกรณี วินัย: ครบถ้วน (บอกให้ได้ว่าทำไม) ควรไม่ทับซ้อนกัน และ*น้อยกรณี* — ตรงนี้แหละที่ "without loss of generality (WLOG — โดยไม่เสียนัยทั่วไป)" หาเลี้ยงชีพ: หารสมมาตรทิ้ง*ก่อน*จะแยกกรณี ด้วยการตรึงลำดับ ตรึงตำแหน่ง หรือตรึงการตั้งชื่อ
กลิ่น. ปริภูมิเล็กและมีโครงสร้าง — สองสี เศษเหลือ mod 3 ใครเดินก่อน ข้อความที่ไม่แปรเปลี่ยนใต้การสลับป้ายชื่อ: ความไม่แปรเปลี่ยนนั้นคือคูปอง จงใช้มัน กลิ่นเตือนในทิศตรงข้าม: จำนวนกรณีที่ทะลุห้าไปแล้วโดยประมาณ มักแปลว่าขาด invariant หรือขาดการเลือกตัวสุดขั้วสักตัว การแยกกรณีคือทางเลือกสุดท้ายอันมีเกียรติ
★★ · ปาร์ตี้หกคน
จงพิสูจน์ว่าในคน 6 คนใดๆ มีสัก 3 คนที่รู้จักกันหมด หรือสัก 3 คนที่แปลกหน้ากันหมด
หยุดก่อน ตรึงแขกหนึ่งคน แล้วมองความสัมพันธ์ทั้งห้าเส้นของเขา
เฉลย. ตรึงคนหนึ่งคน เรียก v ในความสัมพันธ์ 5 เส้นที่ v ต้องมีชนิดหนึ่งปรากฏอย่างน้อย ⌈5/2⌉ = 3 ครั้ง (หลักรังนกพิราบ); WLOG ให้เป็น "รู้จัก" — ตัวข้อความสมมาตรใต้การสลับ รู้จัก/แปลกหน้า ท่านี้จึงหั่นบทพิสูจน์เหลือครึ่งเดียว สมมุติ v รู้จัก A, B, C ถ้ามีคู่ไหนในสามคนนี้รู้จักกัน คู่นั้นบวก v คือสามเหลี่ยมคนรู้จัก ถ้าไม่มีคู่ไหนเลย A, B, C ก็คือสามคนแปลกหน้ากันหมด จบทั้งสองทาง ∎ ความคม: จับคน 5 คนนั่งเป็นรูปห้าเหลี่ยม เพื่อนบ้านรู้จักกัน เส้นทแยงแปลกหน้ากัน — ไม่มีสามเหลี่ยมชนิดใดเลย ดังนั้น 6 คือค่าเป๊ะ: R(3,3) = 6
เครื่องมือสามชิ้นในแปดบรรทัด — รังนกพิราบเลือกกิ่ง WLOG หั่นต้นไม้เหลือครึ่ง excluded middle ทำให้กรณีครบถ้วน แล้วคำขวัญของทฤษฎี Ramsey ก็ตามมา: โครงสร้างกลายเป็นสิ่งเลี่ยงไม่ได้เมื่อขนาดถึง
ท่า — หารสมมาตรทิ้งก่อนจะแยกกรณี. สมมาตรทุกอันที่คุณไม่ยอมใช้ จะกลายเป็นกรณีที่เหมือนกันเป๊ะสองกรณี ที่ถูกเขียนซ้ำสองรอบ
★★★★ · สามจากห้า
จงพิสูจน์ว่าในจำนวนเต็ม 5 ตัวใดๆ มีสัก 3 ตัวที่ผลบวกหารด้วย 3 ลงตัว — และจงแสดงว่า 4 ตัวนั้นไม่พอ
หยุดตรงนี้ เลือกวิธีแยกกรณีให้แต่ละกิ่งมีอาวุธประจำมือ
เฉลย. ที่สำคัญมีแค่เศษเหลือ mod 3; คัดห้าตัวเข้าชั้น R₀, R₁, R₂ แล้วแยกกรณีตาม*ขนาดชั้นที่ใหญ่ที่สุด* กรณี A — มีชั้นหนึ่งจุ ≥ 3. หยิบสามตัวจากชั้นนั้น: ผลบวก ≡ 3r ≡ 0 (mod 3) กรณี B — ทุกชั้นจุ ≤ 2. ห้าจำนวนจึงบังคับขนาดเป็น (2, 2, 1) ในลำดับใดลำดับหนึ่ง — โดยเฉพาะอย่างยิ่งไม่มีชั้นไหนว่าง เพราะสองชั้นจุได้อย่างมาก 4 หยิบชั้นละหนึ่งตัว: 0 + 1 + 2 ≡ 0 (mod 3) กรณีครบถ้วนแน่: ค่าสูงสุดถ้าไม่ ≥ 3 ก็ต้อง ≤ 2 ∎ ความคม. สี่จำนวนหลบได้: เศษเหลือ {0, 0, 1, 1} — สามตัวใดๆ บวกกันได้ 1 หรือ 2 (mod 3) ไม่มีวันเป็น 0 ดังนั้น 5 คือค่าเป๊ะ นี่คือกรณี n = 3 ของทฤษฎีบท Erdős–Ginzburg–Ziv (1961): ในจำนวนเต็ม 2n − 1 ตัวใดๆ มีสัก n ตัวที่ผลบวกหารด้วย n ลงตัว และ 2n − 2 ตัวไม่มีวันพอ — ศูนย์จำนวน n − 1 ตัวกับหนึ่งจำนวน n − 1 ตัวคือท่าหลบฉบับทั่วไป ป้ายบอกทาง "ความเป๊ะประหลาด" ของบทที่ 8 ระเบิดตรงตามนัด
ท่า — ออกแบบกรณีย้อนจากท่าปิดเกม. แยกตามตัวแปรที่เลือกมาให้ทุกกิ่งตายด้วยอาวุธที่มีในมือ; การวิเคราะห์ที่โชว์ความคม (tightness) ไม่ได้ มักซุกกรณีหย่อนไว้ที่ไหนสักแห่ง
เครื่องจักรกับท่านี้. การเช็กแบบถ้วนทั่วคือท่วงก้าวโดยกำเนิดของเครื่องจักร — บทพิสูจน์สี่สีของ Appel กับ Haken (1976) เช็กราว 1,936 คอนฟิกูเรชัน — แต่ใบอนุญาต WLOG การมองออกว่าผลหารตัวไหนยุบ 3⁶ กรณีให้เหลือ 2 ยังเป็นงานออกแบบของมนุษย์
แก้โจทย์เล็กก่อน
เครื่องมือ. สองทิศทางบนหน้าปัดเดียว กรณีเล็กก่อน: คำนวณ n = 1, 2, 3, 4 ด้วยมือ ตั้งข้อคาดการณ์แพตเทิร์น แล้วพิสูจน์มัน — กรณีที่คำนวณไว้กลายเป็นฐานของอุปนัย วางนัยทั่วไปก่อน — ปฏิทรรศน์นักประดิษฐ์ของ Pólya อีกครั้ง: แทนที่คำถามเฉพาะเจาะจง (100, เลขปีนี้, กระดานแผ่นนี้) ด้วยครอบครัวพารามิเตอร์ของมัน; คำถามฉบับทั่วไปมีโครงสร้างให้จับมากกว่า และคำตอบเฉพาะก็ร่วงออกมาเองด้วยการแทนค่า
กลิ่น. ค่าคงตัวใหญ่เจาะจง — 2026, 100, 10¹⁸ — แทบทุกครั้งคือชุดแฟนซีที่คลุมพารามิเตอร์สะอาดๆ ตัวหนึ่งชื่อ n "จงหาค่า" โดยไม่มีโครงสร้างให้เห็น: ทำตารางทันที ข้อความที่ให้ความรู้สึกตามอำเภอใจ: วางนัยทั่วไปจนกว่ามันจะรู้สึกหลีกเลี่ยงไม่ได้ และรีเฟล็กซ์ของมืออาชีพ: แพตเทิร์นจากข้อมูลสามจุดคือสมมุติฐาน ไม่ใช่คำตอบ
★★ · หลักสุดท้ายของ 7²⁰²⁶
จงหาหลักสุดท้ายของ 7²⁰²⁶
หยุดก่อน แทน 2026 ด้วย n แล้วทำตารางเล็กๆ
เฉลย. ทำตาราง 7ⁿ mod 10: 7, 9, 3, 1 แล้วก็ 7, 9, 3, 1, … — คาบ 4 (เศษเหลือซ้ำเมื่อไร ทั้งวงจรต้องซ้ำตาม: การคูณด้วย 7 mod 10 เป็นแมปตายตัว) คำตอบจึงขึ้นกับ n mod 4 เท่านั้น และ 2026 ≡ 2 (mod 4): หลักสุดท้าย = 7² mod 10 = 9 ∎ เบื้องหลังของเล่นชิ้นนี้คือเครื่องจักรทั่วไป: กำลังต่างๆ mod m เป็นคาบในที่สุดเสมอ — รังนกพิราบบนเศษเหลือ m ตัว — และทฤษฎีบทของ Euler ทำนายว่าคาบต้องหาร φ(10) = 4 ลงตัว
ท่า — แทนปีด้วย n. ความเป็นคาบสองบรรทัด ในชุดแฟนซีสี่หลัก จงถอดชุดมันออก
★★★★ · วงกลมปะทะเสียงไซเรน
วงกลม n วงบนระนาบ แต่ละคู่ตัดกันที่ 2 จุดพอดี ไม่มีสามวงผ่านจุดเดียวกัน พวกมันหั่นระนาบออกเป็นกี่บริเวณ? จงคำนวณกรณีเล็ก ตั้งข้อคาดการณ์ — แล้วพิสูจน์
หยุดตรงนี้ และอย่าเชื่อสูตรแรกของตัวเอง
เฉลย. กรณีเล็ก: n = 1 → 2 บริเวณ; n = 2 → 4; n = 3 → 8 ไซเรนขับขาน: 2ⁿ ทดสอบ n = 4 วงกลมวงที่สี่ตัดอีก 3 วงก่อนหน้าที่ 6 จุด ถูกหั่นเป็น 6 ส่วนโค้ง และแต่ละส่วนโค้งผ่าหนึ่งบริเวณ: 8 + 6 = 14 ไม่ใช่ 16 การเบิ้ลสองเท่าคือภาพลวงตาของจำนวนเล็ก การนับแบบสะสมทีละวง คราวนี้ซื่อตรง: วงกลมวงที่ k ตัดวงก่อนหน้าทั้ง k − 1 วงที่ 2(k − 1) จุด ถูกหั่นเป็น 2(k − 1) ส่วนโค้ง และแต่ละส่วนโค้งผ่าบริเวณเดิมหนึ่งบริเวณพอดี — เพิ่ม 2(k − 1) ขณะที่วงแรกเพิ่ม 1 จากค่าตั้งต้น 1 R(n) = 2 + Σₖ₌₂ⁿ 2(k − 1) = n² − n + 2 ตรวจ: 2, 4, 8, 14, 22 ✓ แล้วรับรอง*อย่างเป็นอิสระ*ด้วยสูตรของ Euler V − E + F = 2: V = n(n − 1) จุดตัด; แต่ละวงแบกจุดตัดไว้ 2(n − 1) จุด ดังนั้น E = 2n(n − 1) ส่วนโค้ง; F = 2 − V + E = n(n − 1) + 2 — ได้ n² − n + 2 ตัวเดิม ∎ สองถนน หนึ่งคำตอบ: มาตรฐานที่แท้จริงของคำว่า "ทวนสอบแล้ว"
วางแฝดเตือนใจไว้เคียงกัน — ปัญหาวงกลมของ Moser: n จุดบนวงกลม ลากคอร์ดครบทุกเส้น ไม่มีสามเส้นร่วมจุดเดียว นับบริเวณ ลำดับวิ่ง 1, 2, 4, 8, 16 — แล้วก็ 31 ที่ n = 6 สูตรจริงคือ C(n,4) + C(n,2) + 1 (คอร์ดแต่ละเส้นเพิ่มหนึ่งบริเวณ; จุดตัดภายในแต่ละจุด — หนึ่งจุดต่อทุก 4 จุดบนวง — เพิ่มอีกหนึ่ง): 1, 2, 4, 8, 16, 31, 57 — ลำดับ A000127 ใน OEIS เบิ้ลสองเท่าห้าครั้งติดกัน แล้วก็ทรยศ กรณีเล็กมีหน้าที่เสนอ; บทพิสูจน์เท่านั้นที่ชี้ขาด
ท่า — คาดการณ์ให้ถูกๆ ทวนสอบให้แพงๆ รับรองสองชั้น. กรณีเล็กตัวที่สี่คือเบี้ยประกันราคาถูก; การหาที่มาอีกเส้นทางที่เป็นอิสระคือตราประทับ
เครื่องจักรกับท่านี้. เครื่องจักรแจกแจงเก่งกว่าเราชนิดไร้สาระ — นักแข่งคำนวณสี่พจน์แล้วเปิด OEIS กันจริงๆ — แต่การลากเส้นต่อเป็น 2ⁿ จากสี่พจน์คือกับดักของ Moser ฉบับอุตสาหกรรม; คาดการณ์-แล้ว-รับรอง ถ่ายโอนไปใช้ตรวจสอบเอาต์พุตของเครื่องจักรได้คำต่อคำ
นับสองทาง
เครื่องมือ. นับวัตถุชุดเดียวด้วยระบบทำบัญชีสองแบบ; ทั้งสองแบบนับสิ่งเดียวกัน สองนิพจน์จึงเท่ากัน — และสมการนั้นแหละคือทฤษฎีบท วัตถุที่ใช้บ่อยคือเซตของ*อุบัติการณ์ (incidence)*: ผลรวมรายแถวปะทะผลรวมรายคอลัมน์ของเมทริกซ์ 0/1 ตัวเดียวกัน นับสองทางคือโรงตีเหล็กแห่งเอกลักษณ์ของคอมบินาทอริกส์
กลิ่น. เอกลักษณ์หรือการหารลงตัวระหว่างปริมาณเชิงนับ; ผลบวกที่จะง่ายลงถ้าจัดดัชนีใหม่ — "สำหรับนักเรียนแต่ละคน…" ปะทะ "สำหรับโจทย์แต่ละข้อ…"; การจับมือ สมาชิกภาพ ค่าเฉลี่ย (ค่าเฉลี่ยคือการนับสองทางหารด้วยจำนวนหัว) รีเฟล็กซ์: นิยามเซตอุบัติการณ์ให้ชัดแจ้ง — "คู่ (x, y) ที่ซึ่ง…" — แล้วรวมยอดมันทั้งสองทาง
★★ · การจับมือ กับสำมะโน
(ก) จงพิสูจน์ว่าในกราฟใดๆ ผลรวมของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม และสรุปว่าจำนวนจุดยอดดีกรีคี่เป็นจำนวนคู่เสมอ (ข) ในห้องเรียนหนึ่ง นักเรียน 35 คนแต่ละคนแก้โจทย์ได้คนละ 3 ข้อพอดี และโจทย์ทุกข้อถูกแก้โดยนักเรียน 5 คนพอดี มีโจทย์ทั้งหมดกี่ข้อ?
หยุดก่อน ทั้งสองข้อคือท่าเดียวกัน
เฉลย. (ก) นับอุบัติการณ์ (v, e) ที่จุดยอด v เป็นปลายของเส้นเชื่อม e: จัดกลุ่มตามจุดยอด ได้ Σ deg(v); จัดกลุ่มตามเส้นเชื่อม ได้เส้นละ 2 พอดี ดังนั้น Σ deg(v) = 2|E| — และผลบวกของจำนวนเต็มที่ลงเอยเป็นคู่ ต้องมีพจน์คี่อยู่เป็นจำนวนคู่ตัว จุดยอดดีกรีคี่จึงมาเป็นจำนวนคู่เสมอ (ข) นับอุบัติการณ์ (นักเรียน, โจทย์) สองทาง: 35 · 3 = P · 5 ดังนั้น P = 21 ∎ ไม่ต้องแจกแจง ไม่ต้องรู้โครงสร้าง — สองมุมมองเพียงลำพังก็ตรึงคำตอบอยู่หมัด
ท่า — รวมยอดเมทริกซ์ทั้งสองทาง. จะรายแถวหรือรายคอลัมน์ ยอดรวมใหญ่ไม่มีทางแคร์ จงทำให้ความไม่แคร์นั้นพูดอะไรออกมาสักอย่าง
★★★★ · จุดตรึงทุกจุด นับจากด้านข้าง
(IMO 1987 ข้อ 1) ให้ pₙ(k) เป็นจำนวนการเรียงสับเปลี่ยนของ {1, …, n} ที่มีจุดตรึง k จุดพอดี จงพิสูจน์ว่า Σₖ₌₀ⁿ k · pₙ(k) = n!
หยุดตรงนี้ เซตหนึ่งเดียวเซตไหน ที่ทั้งสองข้างอาจกำลังนับอยู่?
เฉลย. ข้างซ้ายนับการเรียงสับเปลี่ยน π แต่ละตัว หนึ่งครั้ง*ต่อจุดตรึงหนึ่งจุดที่มันมี*: มันคือขนาดของเซตอุบัติการณ์ F = {(π, i) : π(i) = i} เมื่อจัดกลุ่มตาม π จัดกลุ่มตาม i แทนสิ: การเรียงสับเปลี่ยนที่ตรึง i ตัวที่กำหนด ก็คือการเรียงสับเปลี่ยนของสมาชิกอีก n − 1 ตัวนั่นเอง — มี (n − 1)! ตัว ดังนั้น |F| = n · (n − 1)! = n! ∎ เช็กสติที่ n = 3: การเรียงสับเปลี่ยนหนึ่งตัวมีจุดตรึง 3 จุด สามตัวมี 1 สองตัวมี 0; 3·1 + 1·3 + 0·2 = 6 = 3! ✓
โจทย์ IMO แท้ๆ — และคำเฉลยทั้งหมดคือการเปลี่ยนมุมมองครั้งเดียว ยาวสามบรรทัด ความยากกับความยาวของคำเฉลยที่ดีที่สุดแทบเป็นตัวแปรอิสระต่อกัน; ข้อสอบข้อนี้ทดสอบว่าผลบวกตัวนั้น*ได้กลิ่น*การนับอุบัติการณ์หรือเปล่า อ่านในเชิงความน่าจะเป็น เอกลักษณ์นี้บอกว่าการเรียงสับเปลี่ยนโดยเฉลี่ยมีจุดตรึงหนึ่งจุดพอดี — ซึ่งส่งเครื่องมือถัดไปมาใส่มือเรา
ท่า — ทุกผลบวกคือเซตหนึ่งที่กำลังถูกนับ จงหาเซตนั้นให้เจอ.
เครื่องจักรกับท่านี้. การทวนสอบว่าสองยอดตรงกันคือเลขคณิต; *การเลือกเซตอุบัติการณ์*คือการแทนเสียใหม่ ซึ่งวางนัยทั่วไปได้แย่ในโมเดล เมื่อเจอผลบวกถ่วงน้ำหนักที่แปลกใหม่
เลนส์ความน่าจะเป็น
เครื่องมือ. นำเข้าความน่าจะเป็นสู่ปัญหาที่ไม่เอ่ยถึงมันสักคำ เครื่องยนต์ที่หนึ่ง — ภาวะเชิงเส้นของค่าคาดหมาย: E[X₁ + ⋯ + Xₙ] = Σ E[Xᵢ] โดยสมมุติความเป็นอิสระ*ศูนย์*ข้อ ความยุ่งเหยิงที่พันกันสหสัมพันธ์กันจึงแตกตัวเป็นผลบวกรายชิ้นส่วน เครื่องยนต์ที่สอง — การเฉลี่ย วิธีความน่าจะเป็น (probabilistic method) ของ Erdős: ถ้าค่าเฉลี่ยทั่วทั้งครอบครัวคือ v สมาชิกบางตัวย่อมทำได้อย่างน้อย v สุ่มหยิบวัตถุ คำนวณคุณค่าคาดหมายของมัน แล้ววัตถุดีๆ ก็มีอยู่จริง — โดยไม่เคยถูกสร้างขึ้นเลย
กลิ่น. "จงพิสูจน์ว่ามีการจัดเรียง / การระบายสี / สับเซต ที่อย่างน้อย…" โดยมองไม่เห็นวิธีสร้าง: จงสุ่มแล้วเฉลี่ย ปริมาณใดก็ตามที่เป็นผลบวกของส่วนช่วยเล็กๆ จำนวนมากที่ทับซ้อนกัน: ผลบวกตัวชี้วัด (indicator) รีเฟล็กซ์: ตั้งชื่อตัวชี้วัด — แล้วมองดูการพึ่งพากัน อุปสรรคตัวใหญ่ในทุกที่อื่น กลายเป็นไม่สำคัญเสียเฉยๆ
★★ · การเรียงสับเปลี่ยนเฉลี่ย
จงแสดงว่าจำนวนจุดตรึงเฉลี่ยของการเรียงสับเปลี่ยนสุ่มของ n สมาชิกคือ 1 — สำหรับทุก n
หยุดก่อน ห้ามใช้ผลบวกบน k
เฉลย. ให้ Xᵢ = 1 ถ้า π(i) = i มิฉะนั้นเป็น 0; จำนวนจุดตรึงคือ X = Σ Xᵢ และ E[Xᵢ] = P(π(i) = i) = (n − 1)!/n! = 1/n ภาวะเชิงเส้น — Xᵢ ทั้งหลายสหสัมพันธ์กันหนักหน่วง และนั่นไม่สำคัญเลย: E[X] = n · (1/n) = 1 ∎
เลขคณิตข้อนี้ก็คือเอกลักษณ์ IMO จากหมวดที่แล้ว หารด้วย n! แต่การนับสองทางต้องการแรงบันดาลใจ — ต้องหาเซตอุบัติการณ์ให้เจอ — ขณะที่ค่าคาดหมายต้องการแค่รีเฟล็กซ์ประจำกาย ภาษาความน่าจะเป็นแปลงการปิ๊งครั้งเดียวจบให้กลายเป็นการคำนวณกิจวัตร; การแปลงนั้นแหละคือประเด็นของการมีเลนส์เป็นของตัวเอง
ท่า — เขียนตัวชี้วัดออกมา. ภาวะเชิงเส้นไม่เคยถามว่าพวกมันอิสระต่อกันหรือเปล่า
★★★★ · รอยตัดใหญ่
จงพิสูจน์ว่ากราฟทุกกราฟที่มี m เส้นเชื่อม มีการแบ่งจุดยอดออกเป็นสองฝั่ง ที่มีเส้นเชื่อมข้ามระหว่างฝั่งอย่างน้อย m/2 เส้น (ไม่มีความสุ่มอยู่ในตัวโจทย์เลย)
หยุดตรงนี้ โยนเหรียญให้จุดยอดทุกจุด
เฉลย. ระบายสีจุดยอดแต่ละจุดเป็น ซ้าย หรือ ขวา ด้วยเหรียญเที่ยงตรงที่อิสระต่อกัน สำหรับเส้นเชื่อม e = {u, v} ให้ Xₑ ชี้วัดเหตุการณ์ "u กับ v อยู่คนละฝั่ง": P(Xₑ = 1) = 1/2 ดังนั้น E[Σ Xₑ] = m/2 ค่าเฉลี่ย m/2 บังคับให้มีบางผลลัพธ์ ≥ m/2 — ค่าเฉลี่ยเกินค่าสูงสุดของตัวเองไม่ได้ ผลลัพธ์นั้นแหละคือการแบ่งฝั่งที่ต้องการ ∎
จากนั้นถอดความสุ่ม (derandomize) ด้วยเพื่อนเก่าคนหนึ่ง บทพิสูจน์ไม่ได้ระบุชื่อรอยตัดสักอัน แต่ monovariant (บทที่ 9) สกัดมันออกมาได้: เริ่มที่ไหนก็ได้; ตราบใดที่ยังมีจุดยอดสักจุดที่มีเพื่อนบ้านฝั่งตัวเองมากกว่าฝั่งตรงข้าม จงพลิกฝั่งมัน การพลิกแต่ละครั้งเพิ่มจำนวนเส้นข้ามฝั่งโดยแท้ ซึ่งถูกขังเพดานไว้ที่ m กระบวนการจึงต้องหยุด — และ ณ จุดหยุด จุดยอดทุกจุดมีอย่างน้อยครึ่งหนึ่งของดีกรีข้ามฝั่งอยู่ ดังนั้นเส้นข้าม ≥ ½ · Σ deg(v)/2 = m/2 การค้นเฉพาะที่ (local search) หาสิ่งที่ความน่าจะเป็นให้สัญญาไว้จนเจอ (สูงขึ้นอีกขั้นบันได: การกำหนดค่าแบบสุ่มทำให้อนุประโยค (clause) ของสูตร 3-SAT ใดๆ เป็นจริงได้ 7/8 ส่วน แต่ละอนุประโยคล้มด้วยความน่าจะเป็น 1/8 — และ Håstad พิสูจน์ว่า 7/8 คือค่าประมาณที่ดีที่สุดแล้ว เว้นแต่ P = NP ขอบเขตสุ่มแสนธรรมดาคือพรมแดนเป๊ะๆ ของความแก้ไหว)
Erdős ก่อตั้งวิธีนี้ในปี 1947 ด้วยการหาขอบเขตล่างของจำนวน Ramsey ผ่านการระบายสีสุ่ม มันคือการคิดแบบกรณีเฉลี่ยในฐานะอาวุธ: ถามว่ากรณี*ตามแบบฉบับ*ทำได้แค่ไหน แล้วอัปเกรดความตามแบบฉบับให้เป็นการมีอยู่ (การเฉลี่ย) หรือเป็นอัลกอริทึม (การถอดความสุ่ม) ปาฏิหาริย์นักโทษร้อยคนของบทที่ 7 คือเลนส์นี้เปิดเต็มกำลัง — อัตรารอดของปัจเจกไม่มีใครดีขึ้นเลย; กลยุทธ์เพียงต้อนความล้มเหลวทั้งหลายให้ไปกองอยู่ในโลกซวยชุดเดียวกัน ค่าเฉลี่ยแตะต้องไม่ได้; ความแปรปรวนคือคานงัด
ท่า — อัปเกรดค่าเฉลี่ยเป็นการมีอยู่ แล้วเป็นอัลกอริทึม.
เครื่องจักรกับท่านี้. ไม่มีอะไรให้การเสิร์ชค้นเจอ จนกว่าใครสักคนจะหล่อกรอบ "มีอยู่" เสียใหม่เป็น "ค่าเฉลี่ย" — การเป็นเจ้าของการตัดสินใจที่จะสุ่มโลกที่กำหนดแน่นอนไว้แล้ว ยังคงเป็นส่วนของมนุษย์
งบประมาณมาก่อน
เครื่องมือ. ก่อนลงมือแก้ จงตั้งงบ: ขนาดของปริภูมิค้นหา ปริมาณสารสนเทศของคำตอบ จำนวนปฏิบัติการที่จ่ายไหว — แล้วปล่อยให้ตัวเลขเหล่านั้น*เลือกวิธีให้* สำหรับโปรแกรมเมอร์นี่คือความหมายตรงตัว: ราว 10⁸ ปฏิบัติการง่ายๆ ต่อวินาที เงื่อนไขขอบเขตของโจทย์จึงเข้ารหัสอัลกอริทึมที่ผู้ออกตั้งใจไว้ สำหรับนักคณิตศาสตร์มันคือเชิงทฤษฎีสารสนเทศ: กระบวนการที่มีผลลัพธ์สามทางจำนวน k ครั้ง แยกแยะได้อย่างมาก 3ᵏ สถานการณ์ กลยุทธ์ใดๆ จึงต้องใช้อย่างน้อย ⌈log(#กรณี)⌉ ขั้น — ขอบเขตล่างที่ไม่เรียกร้องความเฉลียวฉลาด เรียกร้องแค่การนับ
แหวนถอดรหัสของนักแข่งเขียนโปรแกรม ควรค่าแก่การพิมพ์แปะข้างโต๊ะ:
| เงื่อนไขขอบเขต | รูปทรงที่จ่ายไหว | เจตนาตามแบบฉบับ |
|---|---|---|
| n ≤ 11 | n! ≈ 4·10⁷ | brute-force การเรียงสับเปลี่ยน |
| n ≤ 20–24 | 2ⁿ·n | bitmask DP |
| n ≤ 40 | 2^(n/2) | meet in the middle |
| n ≤ 500 | n³ | DP กำลังสาม / วิถีสั้นสุดทุกคู่ |
| n ≤ 10⁵–10⁶ | n log n | sort / heap / แบ่งแล้วพิชิต |
| n ≤ 10⁸ | n | กวาดเชิงเส้น, two pointers |
| n ~ 10¹⁸ | log n / √n | ไบนารีเสิร์ชบนคำตอบ, คณิตศาสตร์ |
อ่านไปข้างหน้า ตารางนี้ตั้งงบให้แผนของคุณ; อ่านย้อนกลับ มันคือเครื่องถอดรหัสเจตนาผู้ออกโจทย์ของบทที่ 8
กลิ่น. เงื่อนไขขอบเขตใดๆ ที่ถูกระบุมา — n ≤ 20, n ≤ 10⁵ และ n ≤ 10¹⁸ คือสามปัญหาคนละเรื่องที่สวมโจทย์ข้อความเดียวกัน "อย่างน้อยต้องถาม / ชั่ง / เปรียบเทียบกี่ครั้ง?": ขอบเขตเชิงสารสนเทศกำลังร้องขอให้ถูกนับ แผนที่ยังไม่เคยประเมินต้นทุน: จงประเมินก่อนลงมือ
★★ · พบกันครึ่งทาง
มีสับเซตของ {1, 2, 3, 4} กี่ชุดที่ผลบวกเป็น 5 — และคุณจะนับผลบวกสับเซตในหมู่ตัวเลข 40 ตัวอย่างไร ในเมื่อ brute force บน 2⁴⁰ ≈ 10¹² สับเซตนั้นตายสนิท?
หยุดก่อน ผ่าตัวปัญหา ไม่ใช่ผ่าครึ่งความต่าง
เฉลย. ผ่าครึ่ง: L = {1, 2}, R = {3, 4} ผลบวกสับเซตของแต่ละข้างคือ {0, 1, 2, 3} และ {0, 3, 4, 7} สับเซตเต็มตัวคือคู่หนึ่งคู่ หยิบชิ้นส่วนข้างละหนึ่ง และมันแตะ 5 เมื่อ sₗ + sᵣ = 5: คู่ (1, 4) = {1} + {4} กับ (2, 3) = {2} + {3} สองสับเซต ตรงกับการแจกแจงตรงๆ สำหรับ n = 40: แจกแจงผลบวก 2²⁰ ≈ 10⁶ ค่าของแต่ละครึ่ง sort ข้างหนึ่ง แล้วไบนารีเสิร์ชหาตัวเติมเต็ม — ราว 2²⁰ · 20 ปฏิบัติการ เป็นหลักวินาทีแทนที่จะเป็นหลักศตวรรษ ไอเดียเดียวที่ใช้คือเลขคณิต: 2ⁿ ฆ่าคุณตาย 2 · 2^(n/2) ถูกแสนถูก และคู่ของครึ่งสับเซตสมนัยหนึ่งต่อหนึ่งกับสับเซต เลขคณิตงบประมาณไม่ได้แค่ตรวจวิธี — มัน*ประดิษฐ์*วิธีขึ้นมาเลย ∎
ท่า — ซื้อเลขชี้กำลังมาครึ่งเดียว. เมื่อ 2ⁿ ฆ่าคุณ จงถามว่าปัญหาผ่าออกเป็นสองครึ่งที่มาบรรจบกันตรงตะเข็บได้หรือไม่
หน้าเชิงทฤษฎีสารสนเทศของท่านี้ชนะศึกไปแล้วในบทที่ 7: การชั่งลูกบอลสิบสองลูกมีคำตอบเป็นไปได้ 24 แบบ กับตาชั่งสามผลลัพธ์ — 3² = 9 < 24 สองครั้งชั่งจึงตายสนิท; 3³ = 27 ผ่านฉิวเฉียด และขอบเขตนี้ทำงานสองหน้าที่ *ออกแบบ*แผนการชั่งให้ด้วย: การชั่งแต่ละครั้งต้องผ่าผู้รอดชีวิตให้ใกล้สามส่วนเท่าๆ กัน จึงต้องสี่ต่อสี่ ขณะที่หกต่อหกทิ้งผลลัพธ์ตาชั่งสมดุลไปเปล่าๆ นับปริภูมิคำตอบ นับความจุช่องสัญญาณ ให้อัตราส่วนเป็นหางเสือ — รีเฟล็กซ์เดียวกันนี้ตีราคาเกมยี่สิบคำถาม (2²⁰ ≈ 10⁶ วัตถุ) การ sort ด้วยการเปรียบเทียบ (log₂ n! ≈ n log n) และเมื่ออ่านย้อนกลับ เงื่อนไขขอบเขตของคนออกโจทย์
เครื่องจักรกับท่านี้. อะซิมป์โทติกคือธาตุแท้ของเครื่องจักร กระนั้นการประเมินก่อนคำนวณคือพฤติกรรมเชิงวางแผนที่เอเจนต์อัตโนมัติขึ้นชื่อลือชาว่าชอบข้าม — และขอบเขตเชิงสารสนเทศคือบทพิสูจน์ว่าด้วยกลยุทธ์ทั้งหมด ไม่ใช่กลยุทธ์อันใดอันหนึ่ง: รสไม่เชิงสร้าง (nonconstructive) แบบนั้นอีกแล้ว
สามฉากใหญ่
เรื่องเล่าเลื่องชื่อสามเรื่อง แต่ละเรื่องคือเครื่องมือหนึ่งชิ้นในชุดแฟนซีที่โด่งดังที่สุดของมัน — และแต่ละเรื่องมาพร้อมการแก้ข้อมูลที่ฉบับเล่าซ้ำมักข้ามไป
★★ · สะพานทั้งเจ็ดแห่ง Königsberg
Königsberg ปี 1736 — ปัจจุบันคือ Kaliningrad แม่น้ำ Pregel แบ่งเมืองออกเป็นแผ่นดินสี่ผืน — เกาะ Kneiphof ฝั่งเหนือ ฝั่งใต้ และแหลมด้านตะวันออก — เชื่อมกันด้วยสะพานเจ็ดแห่ง จะเดินเล่นให้ข้ามสะพานทุกแห่ง แห่งละหนึ่งครั้งพอดี ได้หรือไม่?
หยุดก่อน ตอนนี้คุณมีเครื่องมือแล้ว: ตั้งชื่อจุดยอด
เฉลย. ท่าของ Euler — พูดได้เต็มปากว่าเป็นปฐมบทของทฤษฎีกราฟและของโทโพโลยี "เรขาคณิตแห่งตำแหน่ง" ในถ้อยคำของเขาเอง — คือการ*ลบเมืองทิ้ง*: แผ่นดินแต่ละผืนเป็นจุด สะพานแต่ละแห่งเป็นเส้น สิ่งที่เหลือรอดมีแค่โครงสร้างอุบัติการณ์ จากนั้นคือข้อสังเกต: การเดินที่ผ่านทะลุจุดยอดหนึ่ง บริโภคสะพานของมัน*เป็นคู่* เข้าหนึ่งออกหนึ่ง ดังนั้นแผ่นดินทุกผืน ยกเว้นอย่างมากจุดตั้งต้นกับจุดสิ้นสุด ต้องมีสะพานเป็นจำนวนคู่ ดีกรีของ Königsberg คือ 5, 3, 3, 3 — รวมได้ 14 = 2 × 7 สะพาน เช็กสติเงียบๆ ของบทตั้งการจับมือ — จุดยอดคี่สี่จุด ในขณะที่การเดินหนึ่งรอบทนได้อย่างมากสอง การเดินเล่นเช่นว่าจึงไม่มีอยู่จริง ∎ Euler พิสูจน์ฝั่งความเป็นไปไม่ได้; ส่วนที่ว่าจุดยอดคี่ไม่เกินสองนั้น*เพียงพอ*บนมัลติกราฟเชื่อมโยง ถูกตอกตะปูปิดโดย Hierholzer ในปี 1873
คติของเรื่องคือท่าเปิดบทนี้ทั้งบทในฉบับจิ๋ว: การปิ๊งไม่ได้เกี่ยวกับสะพานเลย มันคือการตัดสินใจว่ามีแต่โครงสร้างเท่านั้นที่สำคัญ — นามธรรมหนึ่งชั้น จากนั้นภาวะคู่คี่ (parity) ที่เด็กก็เช็กได้
ท่า — ลบเมืองทิ้ง. ปอกทุกรายละเอียดที่คำถามไม่ได้บริโภคออกไป; สิ่งที่เหลือมักเป็นปัญหาที่แก้ไว้แล้ว
★★★ · วงกลมของ Josephus
ตำนานว่าไว้: Yodfat ปี ค.ศ. 67 — นักประวัติศาสตร์ Flavius Josephus ติดกับดักอยู่กับเหล่าทหารของเขา และรอดชีวิตจากวงกลมมรณะ ความซื่อตรงต้องมาก่อน: บันทึกของเขาเอง (The Jewish War เล่ม 3) บอกว่าใช้การจับสลาก และเขาเหลือรอดจนคนสุดท้าย "โดยบังเอิญหรือโดยพรหมลิขิต" ฉบับกำหนดแน่นอน — n คนยืนเป็นวงกลม นับวนไป ทุกคนที่ k ล้มลง คนสุดท้ายรอด — คือการจัดรูปของนักคณิตศาสตร์ยุคหลัง คุณควรไปยืนตรงไหน?
หยุดก่อน แก้วงสองคนก่อน แล้วค่อยวงสามคน
เฉลย. ให้ J(n) เป็นตำแหน่งผู้รอดชีวิต ดัชนีเริ่มที่ 0 ก้าวนับ k หลังการกำจัดครั้งแรก (ตำแหน่ง k − 1) คนที่เหลือ n − 1 คนเล่น*เกมเดียวกันเป๊ะ*แค่เลื่อนไป k: J(n) = (J(n−1) + k) mod n โดย J(1) = 0 หนึ่งบรรทัด รันได้ใน O(n) ทวนสอบด้วยการจำลองสำหรับ k = 2: n = 5 กำจัด 2, 4, 1, 5 เหลือ 3 และความสัมพันธ์เวียนเกิดให้ 0, 0, 2, 0, 2 → ตำแหน่ง 3 ✓; n = 6 กำจัด 2, 4, 6, 3, 1 เหลือ 5 และความสัมพันธ์เวียนเกิดให้ 4 → ตำแหน่ง 5 ✓ สำหรับ k = 2 มีรูปปิด: เขียน n = 2^m + L โดย 0 ≤ L < 2^m; ผู้รอดชีวิต นับจาก 1 คือ 2L + 1 พูดอีกแบบที่เทียบเท่ากัน — อัญมณีเม็ดหนึ่ง — หมุนการแทนฐานสองของ n ไปทางซ้ายหนึ่งบิต: 41 = 101001₂ → 010011₂ = 19 และจริงตามนั้น 41 = 32 + 9 ให้ 2·9 + 1 = 19 ✓; 6 = 110₂ → 101₂ = 5 ✓ (รอบแรกกำจัดตำแหน่งเลขคู่ทั้งหมด และผู้รอดถูกติดป้ายใหม่เป็นการเลื่อนบิตฐานสองพอดิบพอดี — การเวียนเกิดที่มองเห็นได้ในตัวฐานเลข) ตัวเลขของตำนาน: ด้วย n = 41 กับ k = 3 ความสัมพันธ์เวียนเกิดรันเต็มรูปให้ J(41) = 30 — ตำแหน่ง 31 เมื่อนับจาก 1 โดยผู้รอดรองสุดท้ายอยู่ที่ 16 ฉบับเล่าขานดั้งเดิม — Josephus ที่ตำแหน่ง 31 กับสหายที่ 16 — แม่นยำเชิงเลขคณิตเป๊ะ ไม่ว่านักประวัติศาสตร์ผู้นั้นจะคำนวณหรือด้นสด ∎
ท่า — หดวงให้เล็กลง. การกำจัดหนึ่งครั้งเปลี่ยนเกมให้เป็นสำเนาย่อส่วนของตัวมันเอง ที่ถูกติดป้ายใหม่; จงแก้วงเล็กที่สุด แล้วยกคำตอบกลับขึ้นมา
★ · ผลบวกของคุณครู
เรื่องเล่า: ครู Büttner สั่งให้ทั้งชั้นบวก 1 + 2 + ⋯ + 100 หมายจะได้ชั่วโมงเงียบสงบ; หนูน้อย Gauss เขียน 5050 ลงกระดานชนวนแทบจะทันที ทำได้อย่างไร — และมันเกิดขึ้นจริงหรือเปล่า?
หยุดก่อน คุณเจอท่านี้มาแล้วในบทที่ 9
เฉลย. จับตัวแรกคู่กับตัวสุดท้าย: 1 + 100, 2 + 99, …, 50 + 51 — ห้าสิบคู่ คู่ละ 101 พอดี: 50 × 101 = 5050 รูปทั่วไปที่ทนทานกว่าเลี่ยงข้อกังวลเรื่อง n คี่ได้ทุกประตู: เขียนผลบวกไปข้างหน้าและย้อนกลับ แล้วบวกทีละคอลัมน์ — 2S = n(n + 1) ดังนั้น S = n(n + 1)/2 ∎ ทีนี้มาดูบันทึกจริง: แหล่งข้อมูลแรกสุดของเกร็ดนี้ ชีวประวัติที่ระลึกของ Gauss โดย Sartorius von Waltershausen (1856) เอ่ยถึงโจทย์อนุกรมเลขคณิต*ข้อหนึ่ง* แต่ไม่ได้ระบุทั้ง 1-ถึง-100 และทริกจับคู่; รายละเอียดชวนเห็นภาพพอกพูนขึ้นตลอดหนึ่งศตวรรษของการเล่าซ้ำ และ Brian Hayes (American Scientist, 2006) ตามรอยพบฉบับเล่าหลายสิบฉบับที่ขัดแย้งกันเอง จงเล่ามันแบบตำนาน; จงสอนมันแบบคณิตศาสตร์ เนื้อแท้จริงคืออินโวลูชัน k ↦ n + 1 − k ที่ทำให้ทุกคู่บวกได้ค่าคงตัว — หินฐานรากที่ใช้บวกอนุกรมเลขคณิตได้ทุกอนุกรม และแสดงว่า C(n, k) = C(n, n−k)
ท่า — จับคู่ให้ได้ค่าคงตัว. เครื่องมือสมมาตรของบทที่ 9 ในชุดออกงานวันอาทิตย์
ห้องสมุด ครบชุดแล้ว
เครื่องมือสิบหกชิ้นตลอดสามบท — กล่องถูกประดิษฐ์ ประจุถูกอนุรักษ์ ตัวสุดขั้วถูกซักถาม กระจกถูกยกขึ้นส่อง การระบายสีถูกวิศวกรรม; สมมุติฐานถูกเสริมแรง ประวัติศาสตร์ถูกบีบอัด ค่าเหมาะที่สุดถูกปั้นรูป ธรณีประตูถูกผ่าครึ่ง ตารางถูกรันย้อนกลับ; จุดยอดถูกตั้งชื่อ สมมาตรถูกหารทิ้ง ปีถูกแปลงเป็น n ผลบวกถูกนับจากด้านข้าง โลกถูกเฉลี่ย งบประมาณถูกอ่าน หนังสือทุกเล่มในห้องสมุดนี้คือวิธีของ*การมองเห็น* ไม่ใช่วิธีของการบดขยี้ เครื่องจักรก็อ่านห้องสมุดนี้จบแล้วเช่นกัน — พวกมันอ่านมาแล้วทุกอย่าง ตรงไหนที่วันนี้พวกมันรันเครื่องมือได้เร็วกว่ามนุษย์คนไหนๆ และตรงไหนที่พวกมันยังเอื้อมหยิบมันเองไม่ได้หากไม่มีใครสะกิด คือคำถามของภาคถัดไป ซึ่งมาพร้อมวันที่และตัวเลข
บทถัดไป · 17 / 21กระดานคะแนน