ท่าสังหาร
เครื่องมือบางชิ้นก่อคำตอบขึ้นทีละชิ้นส่วน แต่ห้าชิ้นนี้จบการต่อสู้ในดาบเดียว ท่าสังหารคือข้อสังเกตเพียงหนึ่งเดียวที่ทำให้การค้นหาเชิงเอ็กซ์โพเนนเชียลหมดความจำเป็น: หนึ่งบรรทัด ณ จุดที่เครื่องจักรซึ่งทำงานโดยปราศจากนามธรรมตัวนี้จะจมน้ำตายในกองกรณี
เครื่องมือแต่ละชิ้นได้รับการปฏิบัติเหมือนกัน: นิยาม ซึ่งตำราทุกเล่มมี; สัญญาณจำ ซึ่งตำราปล่อยไว้เป็นความรู้เงียบ — กลิ่น ที่จิตใจซึ่งฝึกมาแล้วสังเกตได้ บ่อยครั้งก่อนจะเป็นถ้อยคำเสียอีก ก่อนที่มือจะเอื้อมหยิบเครื่องมือ; โจทย์คู่ที่แก้ให้ดู ข้อหนึ่งสอนจบได้ในการนั่งครั้งเดียว (★★) อีกข้อระดับโอลิมปิกของแท้ (★★★★); และหนึ่งบรรทัดว่าเครื่องจักรรับมือกับมันได้แค่ไหน สัญญาณคือของจริงที่บทนี้ส่งมอบ เรียนรู้กลิ่นให้ได้ แล้วเครื่องมือจะลั่นไกเอง
หลักรังนกพิราบ
เครื่องมือ. ใส่วัตถุมากกว่า n ชิ้นลงกล่อง n ใบ แล้วกล่องใดกล่องหนึ่งจะมีอย่างน้อยสองชิ้น โดยทั่วไป วัตถุ n ชิ้นในกล่อง k ใบ ย่อมมีกล่องหนึ่งที่ได้อย่างน้อย ⌈n/k⌉ ชิ้น นั่นคือทฤษฎีบททั้งหมดแล้ว พลังของมันอาศัยอยู่ที่การเลือกกล่อง — ซึ่งโจทย์ไม่เคยให้มา มันต้องถูกประดิษฐ์ขึ้น
กลิ่น. "จงพิสูจน์ว่ามีสองตัวที่…" หรือ "จงแสดงว่ามีบางตัว…" โดยไม่มีการสร้างที่เห็นได้ชัด ปริมาณที่ถูกขีดขอบเขต: "ในบรรดาจำนวน 51 ตัวใดๆ…" "จุดห้าจุดใดๆ ในจัตุรัส…" การรับประกันที่ถูกเรียกร้องไม่ว่าปรปักษ์จะจัดเรียงอย่างไร รีเฟล็กซ์ที่ฝึกมา: ฉันบังคับวัตถุพวกนี้ให้ตกลงในหมวดหมู่เซตจำกัดแบบไหนได้บ้าง? ระยะทางชวนให้นึกถึงเซลล์เชิงเรขาคณิต การหารลงตัวชวนถึงเศษเหลือหรือส่วนคี่ ลำดับชวนถึงผลรวมนำหน้า (prefix sums) ชาวลอนดอนสองคนมีจำนวนเส้นผมบนหัวเท่ากัน — ประชากรเก้าล้าน แต่จำนวนเส้นผมที่เป็นไปได้มีอย่างมากราวหนึ่งล้านค่า กล่องคือค่าจำนวนเส้นผม จำนวนเต็ม 100 ตัวใดๆ มีบล็อกที่เรียงติดกันซึ่งผลรวมหารด้วย 100 ลงตัว — กล่องคือเศษเหลือของผลรวมนำหน้า 101 ตัว S₀, …, S₁₀₀; สองตัวย่อมชนกัน และบล็อกที่คั่นกลางระหว่างมันคือผลต่างของทั้งคู่ เมื่อเล็งไปที่คอนตินิวอัม บรรทัดเดียวกันนี้ก็ประดิษฐ์การประมาณด้วยจำนวนตรรกยะ: ทฤษฎีบทของ Dirichlet — สำหรับจำนวนจริง α ใดๆ มี q ≤ N บางค่าที่ |qα − p| < 1/N — คือส่วนเศษ (fractional parts) จำนวน N + 1 ค่า ตกลงในช่วง N ช่วง
★★ · ห้าจุดในจัตุรัส
จงพิสูจน์ว่าในบรรดาจุดห้าจุดใดๆ ในจัตุรัสหนึ่งหน่วยแบบปิด มีสองจุดที่อยู่ห่างกันไม่เกิน √2/2 ≈ 0.707
หยุดตรงนี้ก่อน หน้ากระดาษรอได้
เฉลย. ตัดจัตุรัสเป็นสี่ควอดแรนต์ขนาด ½ × ½ ห้าจุด สี่ควอดแรนต์: ควอดแรนต์หนึ่งย่อมถือสองจุด จุดสองจุดในจัตุรัส ½ × ½ ห่างกันได้อย่างมากเท่าเส้นทแยงมุม: √((½)² + (½)²) = √2/2 ∎
ไม่มีคำว่าควอดแรนต์อยู่ในโจทย์เลย นักแก้โจทย์ผลิตกล่องขึ้นมาเองเพื่อให้ "อยู่กล่องเดียวกัน" บังคับข้อสรุปออกมา — และการเลือกกล่องสี่ใบ ไม่ใช่เก้าไม่ใช่สอง ถูกวิศวกรรมย้อนกลับมาจากเลขห้า: กล่องน้อยกว่าจุดหนึ่งใบ
ท่า — ผลิตกล่องเอง. ทฤษฎีบทได้มาฟรี กล่องคือตัวงาน จงอ่านข้อสรุปที่คุณอยากได้ แล้วประดิษฐ์หมวดหมู่ที่การชนกันภายในส่งมอบข้อสรุปนั้นมาให้
★★★★ · ลำดับเรียงที่หนีไม่พ้น
จงพิสูจน์ว่าทุกลำดับของจำนวนจริงที่ต่างกันทั้งหมด n² + 1 ตัว ย่อมมีลำดับย่อยทางเดียว — เพิ่มขึ้นหรือลดลง — ที่ยาว n + 1
ลองก่อนอ่านต่อ กล่องซ่อนตัวไว้แนบเนียนทีเดียว
เฉลย. แปะป้ายสองตัวเลข (xᵢ, yᵢ) ให้แต่ละตำแหน่ง i: ความยาวของลำดับย่อยเพิ่มขึ้นที่ยาวที่สุดซึ่งจบที่ i และของลำดับย่อยลดลงที่ยาวที่สุดซึ่งจบตรงนั้น สมมุติว่าไม่มีลำดับย่อยทางเดียวใดยาวถึง n + 1 เมื่อนั้นทุก xᵢ และ yᵢ อยู่ใน {1, …, n}: ป้ายต่างกันได้อย่างมาก n² แบบ สำหรับ n² + 1 ตำแหน่ง หลักรังนกพิราบ: สองตำแหน่ง i < j ใช้ป้ายเดียวกัน แต่ตัวเลขต่างกันทั้งหมด ดังนั้นถ้าไม่ aᵢ < aⱼ — ซึ่งลำดับเพิ่มขึ้นยาวสุดที่จบที่ i ต่อท้ายด้วย aⱼ ได้ บังคับให้ xⱼ ≥ xᵢ + 1 — ก็ต้อง aᵢ > aⱼ บังคับให้ yⱼ ≥ yᵢ + 1 ไม่ว่าทางไหนป้ายย่อมต่างกัน ขัดแย้ง ∎
นี่คือ Erdős–Szekeres (1935) ซึ่งแบกสัญญาณบอกใบ้ของคนออกโจทย์จากบทที่ 8 มาเต็มตัว: "n² + 1 พจน์" คือความเป๊ะประหลาด — n² พจน์ยังหลบได้ ด้วยบล็อกลดลง n บล็อก บล็อกละ n ตัว โดยแต่ละบล็อกสูงกว่าบล็อกก่อนหน้า กล่องในที่นี้คือคู่สถิติเกี่ยวกับตัววัตถุเอง: ไม่มีใคร "เห็น" กล่อง n² ใบในโจทย์ นักแก้สร้างลายนิ้วมือสองพิกัดขึ้นมาโดยเจาะจงให้การชนกันเป็นไปไม่ได้ แล้วจึงนับลายนิ้วมือ คลาสสิกคู่หูที่วิ่งด้วยเชื้อเพลิงเดียวกัน: จำนวน n + 1 ตัวใดๆ จาก {1, …, 2n} มีตัวหนึ่งหารอีกตัวลงตัว — เขียนแต่ละตัวเป็น 2ᵏ·m โดย m เป็นจำนวนคี่ ส่วนคี่มีอยู่เพียง n แบบ สองจำนวนย่อมใช้ส่วนคี่ร่วมกัน และตัวที่กำลังต่ำกว่าหารอีกตัวลงตัว
ท่า — ประทับลายนิ้วมือแล้วบังคับชน. แปะสถิติทางเดียวจนกว่าการชนกันจะกลายเป็นเรื่องเหลวไหล แล้วบังคับให้ชนด้วยการนับ กลเม็ดป้ายคู่ตัวนี้โผล่ซ้ำทั่วคอมบินาทอริกส์
เครื่องจักรกับท่านี้. การตรวจบทพิสูจน์รังนกพิราบเป็นเรื่องจิ๊บจ๊อย แต่การหากล่องคือการประดิษฐ์เหนือปริภูมิอนันต์ของการแบ่งส่วน — และ Haken พิสูจน์ในปี 1985 ว่าระบบพิสูจน์แบบ resolution ซึ่งเป็นเครื่องยนต์ในตัวแก้ SAT แบบคลาสสิก ต้องใช้บทพิสูจน์ยาวเชิงเอ็กซ์โพเนนเชียลกับสูตรรังนกพิราบเสียเอง หนึ่งนามธรรมของมนุษย์ หนึ่งกำแพงเอ็กซ์โพเนนเชียลที่ถูกเดินอ้อม
ปริมาณไม่แปรเปลี่ยนและปริมาณวิ่งทางเดียว
เครื่องมือ. ปริมาณไม่แปรเปลี่ยน (invariant) คือปริมาณที่ไม่มีการเดินถูกกติกาครั้งใดเปลี่ยนแปลงมันได้ — ประจุอนุรักษ์ จะพิสูจน์ว่าเป้าหมายไปไม่ถึง จงแสดง invariant ที่มีค่าต่างกันระหว่างจุดตั้งต้นกับเป้าหมาย ส่วนปริมาณวิ่งทางเดียว (monovariant) เคลื่อนที่ทิศทางเดียวเท่านั้น ใช้มันพิสูจน์ว่ากระบวนการต้องหยุด และมองว่ามันจบลงตรงไหนได้บ้าง นี่คือท่าที่ฆ่าการสลับ 14–15 ในบทที่ 2: ภาวะคู่คี่ของการเรียงสับเปลี่ยนคูณภาวะคู่คี่ของแถวช่องว่างไม่มีวันเปลี่ยน เงินรางวัลพันดอลลาร์ของ Loyd จึงไม่เคยตกอยู่ในอันตราย
กลิ่น. โจทย์บรรยายการเดิน — "ลบตัวเลขสองตัวแล้วเขียน…" "กิ้งก่าสองตัวเจอกันแล้ว…" "พลิกแถวไหนก็ได้" — แล้วถามว่า ไปถึงตรงนี้ได้ไหม? มันหยุดไหม? จบแบบไหนได้บ้าง? ห่วงโซ่รีเฟล็กซ์: คำนวณปริมาณราคาถูกสักสองสามตัว (ผลรวม, ผลรวม mod 2, mod 3, เครื่องหมายของผลคูณ, จำนวนคู่สลับลำดับ) ก่อนและหลังการเดินทั่วไปหนึ่งครั้ง อะไรที่รอดมาโดยไม่เปลี่ยนคือผู้ท้าชิงของคุณ สำหรับเรื่องการยุติ จงล่าปริมาณมีขอบเขตที่ถูกบังคับให้วิ่งทางเดียว นิสัยชั้นลึก: เมินวิถีโคจรไปเลย แล้วศึกษาว่าพลวัตอนุรักษ์อะไรไว้ — สัญชาตญาณของ Noether ฉบับย่อส่วน
★★ · การลดทอนบนกระดานดำ
ตัวเลข 1 ถึง 10 ยืนเรียงอยู่บนกระดานดำ หนึ่งการเดิน: ลบสองตัวใดๆ a และ b ออก แล้วเขียน |a − b| แทน หลังเก้าการเดินจะเหลือตัวเลขตัวเดียว มันเป็น 0 ได้หรือไม่?
หยุดก่อน ลองเดินในหัวสักสองสามตา
เฉลย. ติดตาม S ผลรวมของทุกอย่างบนกระดาน mod 2 หนึ่งการเดินเปลี่ยนผลรวมไป (a + b) − |a − b| = 2·min(a, b) — จำนวนคู่ — ดังนั้น S mod 2 ไม่มีวันเปลี่ยน มันเริ่มที่ 1 + 2 + ⋯ + 10 = 55 ซึ่งเป็นจำนวนคี่ ตัวเลขสุดท้ายจึงเป็นคี่ และโดยเฉพาะอย่างยิ่ง ไม่มีทางเป็น 0 ∎ (การจบด้วยจำนวนคี่ทำได้จริงลงไปจนถึง 1; invariant ระบุเป๊ะว่าการจบแบบไหนถูกห้าม)
กราฟความไปถึงได้ของเกมนี้มีสถานะนับพัน invariant ยุบมันเหลือสอง
ท่า — หาประจุอนุรักษ์. ตัดสินความไปถึงได้โดยไม่ต้องสำรวจสักกิ่งเดียว: คำนวณสิ่งที่ทุกการเดินรักษาไว้ แล้วเทียบจุดตั้งต้นกับเป้าหมาย
★★★★ · ห้าเหลี่ยมที่ต้องหยุด
(IMO 1986 ข้อ 3.) จำนวนเต็ม x₁, …, x₅ ประจำอยู่ตามมุมของรูปห้าเหลี่ยม ผลรวมทั้งหมด s > 0 เมื่อใดที่ค่ามุมสักตัว y ติดลบ คุณสามารถแทนที่สามตัวเรียงติดกัน (x, y, z) ด้วย (x + y, −y, y + z) จงพิสูจน์ว่ากระบวนการนี้จำต้องยุติ
หยุดตรงนี้ — เช็กก่อนว่าการเดินหนึ่งครั้งปล่อยอะไรไว้ไม่แตะต้อง
เฉลย. การเดินอนุรักษ์ผลรวม: (x + y) + (−y) + (y + z) = x + y + z ผลรวมจึงคงอยู่ที่ s > 0 ตลอดกาล คราวนี้นิยาม f(x₁, …, x₅) = Σᵢ (xᵢ − xᵢ₊₂)² ดัชนีคิด mod 5 — จำนวนเต็มไม่เป็นลบ ใช้การเดินที่ตำแหน่ง 4 (สมมาตรเชิงวัฏจักรทำให้กรณีนี้เป็นตัวแทนได้) โดย y = x₄ < 0 สี่ในห้าพจน์ของ f เปลี่ยนไป; (x₃ − x₅)² รอด เพราะปลายทั้งสองข้างของมันเลื่อนไป y เท่ากัน กระจายกำลังสองสี่พจน์ที่ได้รับผลกระทบแล้วตัดทอนกัน:
Δf = [−2y(x₁ − x₃) + y²] + 4x₂y + 4x₁y + [2y(x₅ − x₂) + y²] = 2y(x₁ + x₂ + x₃ + x₅) + 2y² = 2y·s.
เนื่องจาก y < 0 < s ทุกการเดินจึงลดค่า f อย่างเคร่งครัด จำนวนเต็มไม่เป็นลบที่ลดลงอย่างเคร่งครัดยอมให้เดินได้เพียงจำกัดครั้ง ∎
คราวนี้ถึงส่วนที่ซื่อสัตย์: ไม่มีใครเสก f ออกมาด้วยรสนิยมล้วนๆ ในห้องสอบ คุณต้องล่า คุณต้องการจำนวนเต็มไม่เป็นลบที่พิสูจน์ได้ว่าตกลง ผลรวมและรูปเชิงเส้นถูกอนุรักษ์ — ใช้การไม่ได้ — คุณจึงลองรูปกำลังสองตามธรรมชาติ Σxᵢ², Σ(xᵢ − xᵢ₊₁)², Σ(xᵢ − xᵢ₊₂)² คำนวณ Δ ของแต่ละตัว จนกว่าจะมีตัวหนึ่งแยกตัวประกอบผ่าน s ได้ ในปี 1986 มีนักเรียนแก้ข้อนี้ได้เพียงสิบเอ็ดคน ช่องว่างระหว่าง*การตรวจ* invariant กับ*การประดิษฐ์*มัน คือช่องว่างระหว่าง ★★ กับ ★★★★
แบบฝึกคู่หู: กิ้งก่าแดง 13 เขียว 15 น้ำเงิน 17 ตัว เมื่อสองตัวต่างสีพบกัน ทั้งคู่เปลี่ยนเป็นสีที่สาม สีเดียวล้วนทั้งฝูงเป็นไปไม่ได้ — การพบกันทุกครั้งขยับผลต่างรายคู่ของจำนวนตัวไป 0 หรือ ±3 ผลต่าง mod 3 จึงถูกอนุรักษ์ พวกมันเริ่มที่ 2, 2, 1 ขณะที่สถานะสีเดียวล้วนต้องการเลข 0
ท่า — เมื่อไม่มีอะไรถูกอนุรักษ์ จงหาสิ่งที่เอาแต่ตก. การยุติต้องการปริมาณทางเดียวที่มีขอบเขต ล่ามันในครอบครัวฟังก์ชันที่ใส่พารามิเตอร์ไว้ แล้วปล่อยให้พีชคณิตเลือกสมาชิกให้เอง
เครื่องจักรกับท่านี้. การเช็ก invariant คือพีชคณิตบรรทัดเดียว การค้นพบมันคือการสังเคราะห์เหนือปริภูมิฟังก์ชันอนันต์ — ปัญหาเดียวกันในชื่อ loop-invariant inference ยังเป็นคอขวดเบนช์มาร์กในการทวนสอบโปรแกรม และโมเดลภาษาทำได้ดีกับ invariant ที่โด่งดัง แต่ทำได้แย่กับพลวัตที่เพิ่งถูกผลิตสดใหม่
หลักตัวสุดขั้ว
เครื่องมือ. สอบปากคำพยานตัวสุดขั้ว: ตัวใหญ่สุด เล็กสุด ตัวแรก ใกล้สุด กรณีขอบ โหมดหนึ่ง — โครงสร้าง: ความสุดขั้วของวัตถุตัวสุดขั้วห้ามโครงแบบบางอย่างรอบตัวมันไว้ ซึ่งคือคานงัดที่คุณต้องการพอดี โหมดสอง — ตัวอย่างค้านเล็กสุด, descente infinie ของ Fermat: สมมุติว่าตัวอย่างค้านมีอยู่ หยิบตัวเล็กสุด สร้างตัวที่เล็กกว่าขึ้นมา ดังนั้นย่อมไม่มีเลย การไต่ลงในหนึ่งลมหายใจ: ถ้า √2 = a/b โดย b เล็กสุด แล้ว a² = 2b² บังคับให้ a = 2c ตามมาด้วย 2c² = b² — และ (b, c) คือการแทนที่เล็กกว่าอย่างเคร่งครัด จบเห่ โครงกระดูกเดียวกันจัดการ x⁴ + y⁴ = z⁴ ผลงานโชว์ของ Fermat เอง
กลิ่น. "มีสมาชิกที่มีสมบัติ P" ในกองยุ่งเหยิงจำกัด — ถามก่อนว่าตัวมากสุดหรือน้อยสุดได้ P มาฟรีหรือเปล่า โครงแบบใดๆ ที่ "หยิบตัวการเลวร้ายที่สุดมาปรับปรุง" ดูจะทำได้ เรขาคณิตกับคู่ใกล้สุด วงกลมเล็กสุด มุมน้อยสุด ก่อนประดิษฐ์เครื่องจักรกลไก จงถามว่าสมาชิกตัวสุดขั้วรู้อะไรอยู่แล้วบ้าง: ตัวสุดขั้วแถมเครื่องผลิตข้อขัดแย้งมาให้ฟรี เพราะสิ่งที่สุดขั้วยิ่งกว่ามันเป็นไปไม่ได้โดยข้อกำหนด
★★ · ราชาแห่งทัวร์นาเมนต์
ในทัวร์นาเมนต์แบบพบกันหมด — ทุกคู่เล่นกันหนึ่งครั้ง ไม่มีเสมอ — จงพิสูจน์ว่ามีผู้เล่น v ที่ผู้เล่นอื่นทุกคนถ้าไม่แพ้ v เอง ก็แพ้ให้ใครสักคนที่แพ้ v
หยุดก่อน คุณจะเสนอชื่อใคร?
เฉลย. เสนอชื่อ v ผู้เล่นที่มีจำนวนชัยชนะมากที่สุด สมมุติว่ามี u ที่ไปถึงไม่ได้ในสองก้าว: เมื่อนั้น u ชนะ v และ u ยังชนะทุกคนที่ v เคยชนะด้วย — เพราะถ้า v ชนะ w และ w ชนะ u แล้ว u จะไปถึงได้ ดังนั้นรายชื่อเหยื่อของ u รวมเหยื่อทั้งหมดของ v บวกตัว v เอง: wins(u) ≥ wins(v) + 1 ขัดแย้งกับความมากสุด ∎
ไม่มีอุปนัยเชิงคณิตศาสตร์ ไม่มีการสร้าง ไม่มีอัลกอริทึม ตัวมากสุดถูก*บังคับ*ให้มีสมบัตินี้ เพราะการละเมิดจะผลิตบางสิ่งที่ยิ่งกว่าตัวมากสุดขึ้นมา
ท่า — ถามว่าตัวมากสุดรู้อะไรอยู่แล้ว. การเลือกตัวสุดขั้วเพียงครั้งเดียวแทนที่การค้นหาทั้งยวง
★★★★ · เส้นตรงของ Sylvester
เซตจำกัดของจุดบนระนาบ ซึ่งไม่ได้อยู่บนเส้นตรงเดียวกันทั้งหมด จงพิสูจน์ว่ามีเส้นตรงบางเส้นที่ผ่านจุดสองจุดของเซตโดยไม่มีจุดที่สามของเซตอยู่บนมัน (Sylvester ตั้งโจทย์นี้ในปี 1893 มันยืนเปิดอยู่ราวสี่สิบปี บทพิสูจน์ข้างล่างเป็นของ L. M. Kelly — ที่ถูกขนานนามกันกว้างขวางว่าเป็นบทพิสูจน์จาก The Book)
หยุดก่อน คุณจะเลือกทำอะไรให้น้อยสุด?
เฉลย. พิจารณาทุกคู่ (P, ℓ) โดย ℓ เป็นเส้นตรงที่ผ่านอย่างน้อยสองจุดของเซต และ P เป็นจุดของเซตที่ไม่อยู่บน ℓ คู่เช่นนี้มีอยู่จริง เพราะเซตไม่อยู่ร่วมเส้นเดียว และมีจำนวนจำกัด — จงเลือกคู่ที่ทำให้ระยะจาก P ถึง ℓ น้อยสุด ข้ออ้าง: ℓ บรรทุกจุดสองจุดพอดี สมมุติว่ามันบรรทุกสามจุด ลากเส้นตั้งฉากจาก P ลงบน ℓ ให้เท้าฉากคือ F ในสามจุดนั้น สองจุดย่อมอยู่ฝั่งปิดเดียวกันของ F: เรียกมัน A (ใกล้ F กว่า อาจอยู่ที่ F พอดี) กับ B (ไกลกว่า) ลำดับตามแนว ℓ จึงเป็น F, A, B โดยที่ A ≠ B ทั้งนี้ A ไม่อยู่บนเส้น PB — มิฉะนั้น PB จะตัด ℓ สองครั้งและ P จะต้องอยู่บน ℓ คราวนี้นับพื้นที่สามเหลี่ยม ABP สองทาง: ½·|AB|·d(P, ℓ) = ½·|PB|·d(A, PB) ดังนั้น d(A, PB) = d(P, ℓ)·|AB|/|PB| แต่ |PB| = √(PF² + FB²) > FB ≥ AB เพราะ P อยู่นอกเส้น (PF > 0) และ B อยู่พ้น A ออกไป (FB ≥ AB) เพราะฉะนั้น d(A, PB) < d(P, ℓ): คู่จุด–เส้นที่ใกล้กันยิ่งกว่าค่าน้อยสุด ขัดแย้ง ∎
สี่สิบปีของการบุกที่ล้มเหลว แล้วก็มาจบด้วยครึ่งหน้ากระดาษที่ไอเดียเดียวของมันคือ*การเลือกว่าจะทำอะไรให้น้อยสุด* — และฝีมือช่างอยู่ที่การเลือกนั้น: วัตถุร่วมจุด–เส้น ไม่ใช่อย่างใดอย่างหนึ่งโดดๆ "แล้วฉันจะไปหาสิ่งนี้เจอได้อย่างไร?" คำตอบซื่อๆ คือเช็กลิสต์ ที่รันแบบเดียวกับนักหมากรุกไล่รายการทางรุก: คู่ใกล้สุด? มุมเล็กสุด? พื้นที่น้อยสุด? ระยะจุด–เส้นน้อยสุด?
ท่า — เลือกว่าจะทำอะไรให้น้อยสุด. หลักตัวสุดขั้วแข็งแรงได้เพียงเท่าฟังก์ชันนัลที่คุณยื่นให้มัน จงไล่รายการผู้ท้าชิงอย่างจงใจ
เครื่องจักรกับท่านี้. การคำนวณ argmax เสร็จในพริบตา แต่การกวัดแกว่งความสุดขั้วเป็นคานงัดของบทพิสูจน์หมายถึงการประดิษฐ์สิ่งที่จะเอามาหาค่าสุดขั้ว — คอขวดกล่องรังนกพิราบตัวเดิมอีกครั้ง; ส่วนอันดับของการไต่ลงก็คือ "termination measures" ที่ตัวทวนสอบอัตโนมัติยังต้องพึ่งมนุษย์จัดหาให้
สมมาตรและการจับคู่
เครื่องมือ. ใช้ประโยชน์จากการแปลงที่รักษาโจทย์ไว้ไม่เปลี่ยน สามรูปแบบม้าใช้งาน การจับคู่: จับวัตถุเป็นคู่ให้แต่ละคู่แบกส่วนร่วมคงที่หรือหักล้างกันเอง การเล่นกระจก: ในเกม ตอบทุกการเดินของคู่ต่อสู้ผ่านสมมาตร อนาคตจึงถูกตอบไว้ล่วงหน้า การขโมยกลยุทธ์: สมมาตรระหว่างผู้เล่นทั้งสองแสดงว่าการเดินแถมของผู้เล่นแรกไม่มีทางเป็นโทษ — ชัยชนะของผู้เล่นแรกจึงมีอยู่ ไม่ว่าจะแสดงตัวมันออกมาได้หรือไม่ก็ตาม
กลิ่น. พจน์ที่มาเป็นคู่เติมเต็มกัน — k กับ n + 1 − k, สับเซตกับส่วนเติมเต็มของมัน, ตัวหาร d กับ n/d จุดศูนย์กลาง แกน อินโวลูชัน: ปฏิบัติการที่ย้อนคืนตัวเอง "ใครชนะเมื่อเล่นสมบูรณ์แบบ?" บนกระดานสมมาตร รีเฟล็กซ์: ล่าอินโวลูชันแล้วถามว่าจุดตรึงของมันคืออะไร ผลรวมยุบตัวลง บทพิสูจน์การมีอยู่หล่นออกมาจากสมาชิกที่ไร้คู่ (การจับคู่ที่โด่งดังที่สุดในคณิตศาสตร์คือตำนานห้องเรียนว่าด้วยเด็กชาย Gauss — ตัวเรื่องเล่า และสิ่งที่ผิดในเรื่องเล่านั้น ปิดท้ายบทที่ 11)
★★ · เหรียญบนโต๊ะกลม
ผู้เล่นสองคนผลัดกันวางเหรียญกลมแบบเดียวกันลงบนโต๊ะกลม ห้ามเหรียญซ้อนทับกัน ใครหมดที่วางก่อนแพ้ ใครชนะ?
หยุดก่อน โต๊ะกลมมาไม่ใช่เรื่องบังเอิญ
เฉลย. ผู้เล่นแรก — ด้วยการชิงยึดจุดสมมาตรกับตัวเองเพียงจุดเดียวที่มี การเดินที่ 1: วางเหรียญกลางโต๊ะเป๊ะ จากนั้นเล่นกระจก: เมื่อไรที่คู่ต่อสู้วางที่จุด S จงตอบที่ S′ ภาพหมุน 180° ของมันรอบจุดศูนย์กลาง invariant: หลังการเดินของคุณทุกครั้ง โครงแบบทั้งหมดสมมาตรใต้การหมุนนั้น ดังนั้นเมื่อคู่ต่อสู้หาที่วางถูกกติกา S ใดๆ ได้ กระจก S′ ของมันย่อมว่างอยู่ — เพราะตำแหน่งสมมาตรอยู่แล้วก่อนการเดินของเขา — และถูกกติกา เพราะมันพ้นภาพกระจกของทุกสิ่งที่ S พ้น; อีกทั้ง S′ ≠ S เพราะจุดตรึงเดียวของการหมุน คือจุดศูนย์กลาง ถูกยึดไปตั้งแต่การเดินที่หนึ่งแล้ว โต๊ะมีพื้นที่จำกัด สักคนย่อมหมดที่วาง และคนนั้นไม่มีวันเป็นคุณ ∎
ผู้เล่นสายกระจกไม่เคยต้องคำนวณ สมมาตรตอบทุกคำถามในอนาคตไว้ล่วงหน้า — กลยุทธ์ที่สมบูรณ์ถูกบีบอัดลงในประโยคเดียว
ท่า — ยึดจุดตรึง แล้วเล่นกระจก. ใครครองสมมาตร คนนั้นครองเกมช่วงปลายกระดาน
★★★ · นิม หรือกระจกที่ทำจากบิต
หินสามกอง: 3, 4, 5 หนึ่งการเดินหยิบหินจำนวนบวกเท่าไรก็ได้จากกองเดียวกองใดกองหนึ่ง ใครหยิบหินก้อนสุดท้ายชนะ ใครชนะ และชนะอย่างไร?
หยุดก่อน เล่นเวอร์ชันสองกองให้ดูก่อน — เช่น 2 กับ 2
เฉลย. สองกองเท่ากันพ่ายให้การเล่นกระจกล้วนๆ: ผู้เล่นที่สองเดินซ้ำทุกการเดินบนอีกกอง คืนสภาพ (n, n) หลังทุกเทิร์น — คำตอบมีอยู่เสมอ หินก้อนสุดท้ายจึงเป็นของเขา กองไม่เท่ากัน: ผู้เล่นแรกทำให้เท่า แล้วกลายเป็นกระจกเสียเอง
ทฤษฎีบทของ Bouton (Charles Bouton, 1901 — การวิเคราะห์ที่ก่อตั้งทฤษฎีเกมคอมบินาทอเรียล) วางนัยทั่วไปให้กระจกกับกองกี่กองก็ได้ เขียนขนาดกองเป็นเลขฐานสอง ตำแหน่งหนึ่งเป็นฝ่ายแพ้สำหรับผู้ถึงตาเดิน ก็ต่อเมื่อทุกหลักฐานสองมีเลข 1 เป็นจำนวนคู่ — สมมูลกับว่า XOR ของขนาดกองทั้งหมด หรือ nim-sum เท่ากับ 0 ทั้งสองทิศทางใช้ข้อสังเกตทิศละหนึ่ง จากตำแหน่งศูนย์ การเดินใดๆ แก้ไขกองเดียว พลิกอย่างน้อยหนึ่งบิต — บางหลักกลายเป็นคี่ สมดุลพังเสมอ จากตำแหน่งไม่เป็นศูนย์ จงมองหลักไม่สมดุลที่สูงที่สุด บางกองย่อมมี 1 ตรงนั้น การหดกองนั้นให้เหลือ (ตัวมันเอง XOR กับ nim-sum) จะคืนสมดุลให้ทุกหลัก — และมันเป็นการหดจริง เพราะบิตนำหน้าที่เปลี่ยนของมันพลิกจาก 1 เป็น 0 ตำแหน่งว่างเปล่ามี XOR เท่ากับ 0 และผู้ถึงตาเดินของมันแพ้ไปเรียบร้อยแล้ว นโยบายชนะจึงเรียบง่าย: ยื่นศูนย์ให้คู่ต่อสู้เสมอ
ที่นี่: 3, 4, 5 = 011, 100, 101 XOR ได้ 010 ≠ 0 ผู้เล่นแรกจึงชนะ หลักสองคือหลักที่ไม่สมดุล และมีเพียงกอง 3 ที่มี 1 ตรงนั้น: เล่น 3 → 3 ⊕ 2 = 1 ตรวจ: 001, 100, 101 — ทุกหลักเป็นคู่ นี่คือการเปิดเกมชนะ*เพียงหนึ่งเดียว* การจะคืนสมดุลผ่านกอง 4 หรือกอง 5 จะบังคับให้พวกมันต้องโตขึ้น ∎
กองเท่ากันคือกรณีพิเศษที่กระจกอธิบายได้: (n, n) สมดุลกันหลักต่อหลัก ศูนย์ของ Bouton คือการเล่นกระจกที่ถูกวางนัยทั่วไป — เมื่อกระดานไม่มีสมมาตรเชิงเรขาคณิตให้ใช้ จงสร้างสมมาตรเชิงเลขคณิตขึ้นมาเองแล้วรักษาสมดุลของมันไว้
ท่า — จับคู่บิต. อินโวลูชันอาศัยอยู่ในเลขคณิตได้ ไม่จำเป็นต้องอยู่บนกระดาน จงหาปริมาณที่สถานะสมดุลของมันคุณกู้คืนได้เสมอ ส่วนคู่ต่อสู้ไม่มีวันรักษาไว้ได้
★★★★ · ชอมป์ กับกลยุทธ์ที่ถูกขโมย
Chomp (David Gale, 1974): ช็อกโกแลตแท่งขนาด m × n, mn ≥ 2 โดยช่องมุมล่างซ้ายอาบยาพิษ หนึ่งการเดิน: เลือกช่องที่เหลืออยู่ช่องใดก็ได้ แล้วกินมันพร้อมทุกช่องที่อยู่เหนือและอยู่ขวาของมัน ใครกินช่องยาพิษแพ้ จงพิสูจน์ว่าผู้เล่นแรกชนะ — สำหรับทุกขนาดกระดาน — ทั้งที่ไม่มีใครรู้จักกลยุทธ์ชนะแบบทั่วไปเลย
หยุดตรงนี้ คุณจะหากลยุทธ์ไม่เจอหรอก นั่นแหละคือประเด็น
เฉลย. Chomp เป็นเกมจำกัด กำหนดแน่นอน สารสนเทศสมบูรณ์ และเสมอกันไม่ได้ — โดยการอุปนัยย้อนกลับ (Zermelo) จึงมีฝ่ายเดียวพอดีที่ครอบครองกลยุทธ์ชนะ สมมุติว่าเป็นผู้เล่นที่สอง ให้ผู้เล่นแรกเปิดเกมด้วยการแทะที่เล็กที่สุดเท่าที่เป็นไปได้: ช่องขวาบนเพียงช่องเดียว โดยข้อสมมุติ ผู้เล่นที่สองย่อมมีคำตอบชนะ Y ที่นำไปสู่ตำแหน่ง Q ซึ่งผู้ถึงตาเดิน — ผู้เล่นหนึ่ง — เป็นฝ่ายแพ้ แต่สังเกต: การเดินของ Chomp *ทุกการเดิน*ลบช่องขวาบนออกอยู่แล้ว Q จึงคือตำแหน่งเดียวกันเป๊ะกับที่จะได้ ถ้า Y ถูกเล่นเป็นการเปิดเกมเสียเอง ผู้เล่นหนึ่งจึงสามารถเปิดด้วย Y ได้ตั้งแต่แรก จับผู้เล่นสองไปนั่งฝั่งแพ้ของ Q ขัดแย้ง — ผู้ชนะคือผู้เล่นหนึ่ง ∎ บทพิสูจน์ไม่เอ่ยชื่อกลยุทธ์ใดเลย และสำหรับกระดานทั่วไป การเดินเปิดเกมที่ชนะยังคงไม่มีใครรู้ คำนวณสำเร็จเฉพาะกรณีเล็กๆ เท่านั้น
สมมาตรในที่นี้อยู่ระหว่าง*ผู้เล่น*ทั้งสอง: อะไรก็ตามที่คำตอบชนะของคุณทำสำเร็จ ฉันก็ทำสำเร็จได้ก่อนหนึ่งการเดิน โครงกระดูกเดียวกันให้ข้อโต้แย้งของ Nash สำหรับ Hex — หมากแถมไม่เคยเป็นโทษ — และให้ "ผู้เล่นแรกไม่แพ้" ของ tic-tac-toe
ท่า — ขโมยกลยุทธ์. พิสูจน์ว่าชัยชนะมีอยู่จริงด้วยการชิงตัดหน้ากลยุทธ์สมมุติของผู้เล่นที่สอง การมีอยู่โดยไม่ต้องแสดงตัวอย่าง
เครื่องจักรกับท่านี้. เอนจินตรวจจับและใช้ประโยชน์จากสมมาตรของกระดานเพื่อเล็มกิ่งการค้นหา แต่การขโมยกลยุทธ์คือบทพิสูจน์ที่ใช้การค้นหาเป็นศูนย์และให้นโยบายเป็นศูนย์ — reinforcement learner ฝึก*เล่น* Chomp จนช่ำชองได้ แต่ก็ยังบอกไม่ได้อยู่ดีว่าทำไมผู้เล่นหนึ่งถึงชนะ
การระบายสีและภาวะคู่คี่
บทที่ 6 จบลงบนกระดานหมากรุกพิการ: มุมตรงข้ามสองมุมหายไป โดมิโนสามสิบเอ็ดตัวถูกยื่นให้ และคำปฏิเสธความยาวสองประโยค — โดมิโนทุกตัวคลุมช่องเข้มหนึ่งช่องกับช่องสว่างหนึ่งช่อง และมุมที่หายไปทั้งสองเป็นสีเดียวกัน คราวนี้จงรับการวางนัยทั่วไปไป เพราะมันคือคลังแสงทั้งคลัง เครื่องมือ: กำหนดสีหรือน้ำหนักให้แต่ละช่อง เพื่อให้ (a) ทุกชิ้นส่วน ไม่ว่าลงจอดตรงไหน คลุมแบบแผนสีคงที่เสมอ ขณะที่ (b) ยอดนับสีรวมของกระดานเป็นยอดที่ชิ้นส่วนประกอบขึ้นมาไม่ได้ การระบายสีคือ homomorphism: มันส่งปริภูมิมโหฬารของความพยายามปูกระเบื้องลงบนเลขคณิตจิ๋ว — ยอดนับ mod k — ที่ซึ่งความเป็นไปไม่ได้กลายเป็นสิ่งมองเห็นได้ ข้อโต้แย้งภาวะคู่คี่คือกรณีพิเศษสองสี ทั้งอุปกรณ์นี้คือประจุอนุรักษ์ของบทนี้ฉบับเจาะจงสำหรับการปูกระเบื้อง — invariant ที่สวมเม็ดสี
กลิ่น. คำถามปูกระเบื้องและการคลุมพื้นที่ การท่องไปบนกริด — ทัวร์ม้าหมากรุก เกมสลับสถานะหลอดไฟ และเหนืออื่นใดคือลายเซ็นนี้: เลขคณิตพื้นที่บอกว่า*เป็นไปได้* ขณะที่ทุกความพยายามสร้างจริงพังไม่เป็นท่าอย่างดื้อรั้น ความดื้อรั้นนั้นคือกลิ่นของสิ่งกีดขวางที่ซ่อนอยู่ รีเฟล็กซ์: ลองสีแบบกระดานหมากรุก แล้วลายทาง แล้วทแยง mod k — โดยเลือก k ให้เข้าคู่กับความยาวกระเบื้อง จูนคาบของเม็ดสีให้เข้ากับรอยเท้าของชิ้นส่วน
★★ · ตัวทียี่สิบห้าตัว
T-tetromino ยี่สิบห้าตัวปูกระดาน 10 × 10 ได้หรือไม่? (เช็กพื้นที่: 25 × 4 = 100 เลขคณิตไม่มีข้อคัดค้าน)
หยุดก่อน ระบายสีก่อน แล้วค่อยนับ
เฉลย. ระบายสีกระดานแบบกระดานหมากรุก: ช่องเข้ม 50 ช่องสว่าง 50 ไม่ว่า T-tetromino ลงจอดที่ไหน มันคลุมสามช่องของสีหนึ่งกับหนึ่งช่องของอีกสี — จำนวนช่องเข้มที่คลุมเป็นคี่ไม่ว่าทางไหน ตัวทียี่สิบห้าตัวจึงคลุมช่องเข้มรวมเป็นผลบวกของจำนวนคี่ยี่สิบห้าจำนวน: คี่ แต่กระดานมีช่องเข้ม 50 ช่องพอดี — คู่ เป็นไปไม่ได้ ∎
ท่า — ให้ภาวะคู่คี่เห็นในสิ่งที่พื้นที่มองไม่เห็น. เมื่อยอดนับผ่านฉลุยแต่การสร้างพังครั้งแล้วครั้งเล่า การระบายสองสีมักรู้ว่าเพราะอะไร
★★★★ · สิบคูณสิบที่ไม่ยอมแพ้ใคร
จงพิสูจน์ว่ากระดาน 10 × 10 ไม่อาจปูด้วย straight tetromino — กระเบื้อง 1 × 4 — จำนวนยี่สิบห้าตัวได้ (เช็กพื้นที่ผ่านอีกเช่นเคย กับดักขึ้นลำพร้อมลั่น)
หยุดตรงนี้ เม็ดสีกระดานหมากรุกหยาบเกินไปสำหรับข้อนี้
เฉลย. ระบายสีช่อง (i, j) — นับแถวและคอลัมน์จาก 0 — ด้วย (i + j) mod 4: ลายทางทแยงคาบสี่ สมบัติกุญแจ: straight tetromino ไม่ว่าวางนอนหรือวางตั้ง ครอบครองสี่ช่องที่ค่า (i + j) เรียงติดกัน — จึงกินสีละหนึ่งช่องพอดีของสี 0, 1, 2, 3 กระเบื้องยี่สิบห้าตัวจึงต้องคลุมแต่ละสีสีละ 25 ครั้งพอดี: การปูที่สำเร็จบังคับให้ทุกสีมี 25 ช่อง คราวนี้ทำสำมะโนกระดาน ในบรรดา i ∈ {0, …, 9} เศษเหลือ 0 กับ 1 ปรากฏอย่างละสามครั้ง ({0, 4, 8} และ {1, 5, 9}) เศษเหลือ 2 กับ 3 อย่างละสองครั้ง เช่นเดียวกันสำหรับ j การนับช่องที่ (i + j) ≡ r คือการ convolve c = (3, 3, 2, 2) กับตัวมันเอง:
- สี 0: 3·3 + 3·2 + 2·2 + 2·3 = 25
- สี 1: 3·3 + 3·3 + 2·2 + 2·2 = 26
- สี 2: 3·2 + 3·3 + 2·3 + 2·2 = 25
- สี 3: 3·2 + 3·2 + 2·3 + 2·3 = 24
(เช็กสติ: 25 + 26 + 25 + 24 = 100 ✓) สี 1 กับสี 3 ถือ 26 และ 24 ช่อง — ไม่ใช่ 25 การปูจึงไม่มีทางดำรงอยู่ ∎
การระบายสีถูกวิศวกรรมมาให้เข้ากับตัวกระเบื้อง: ทแยงคาบสี่ก็*เพราะ*กระเบื้องยาวสี่และจำต้องกินสีละหนึ่งช่อง (ทฤษฎีบททั่วไปที่ซุ่มอยู่หลังกลเม็ดนี้ — de Bruijn, 1969: สี่เหลี่ยมผืนผ้า a × b ปูด้วย 1 × n ได้ก็ต่อเมื่อ n หาร a หรือ b ลงตัว) ทักษะระดับ ★★★★ ไม่ใช่การหยิบการระบายสีมาใช้ แต่คือการออกแบบการระบายสีที่กระเบื้องเคารพเลขคณิตของมัน ส่วนกระดานละเมิด
หนึ่งคำเตือนเรื่องขอบเขต: การระบายสีพิสูจน์ได้เพียงความเป็นไปไม่ได้ ความเป็นไปได้ต้องการการสร้าง — และบทที่ 10 เปิดฉากด้วยเครื่องจักรแห่งการสร้าง
ท่า — วิศวกรรมการระบายสีให้เข้ากับกระเบื้อง. จับคาบของเม็ดสีให้ตรงกับรอยเท้าของชิ้นส่วน แล้วนับสิ่งที่กระดานมีอยู่จริง
เครื่องจักรกับท่านี้. กระดานที่ปูไม่ได้คือกรณีเลวร้ายที่สุดของตัวแก้ SAT — John McCarthy เคยเวียนโจทย์กระดานหมากรุกพิการในฐานะ "tough nut" สำหรับกระบวนการพิสูจน์ — ทว่าใบรับรองด้วยการระบายสี เมื่อถูกเดาขึ้นมาแล้ว เครื่องเช็กได้ในหลักไมโครวินาที การเดามันขึ้นมาต่างหากคือส่วนของมนุษย์
ห้าท่า ในพริบตาเดียว
| ท่า | กลิ่น | ตราประจำ |
|---|---|---|
| ผลิตกล่องเอง | "จงพิสูจน์ว่าต้องมีสองตัวที่ร่วม…" | ห้าจุด, √2/2 |
| ประจุอนุรักษ์ / ปริมาณวิ่งทางเดียว | ให้การเดินมา; "ไปถึงได้ไหม? หยุดไหม?" | Δf = 2ys ของห้าเหลี่ยม |
| สอบปากคำตัวสุดขั้ว | "ต้องมีสมาชิกบางตัวที่…" | ราชาแห่งทัวร์นาเมนต์ |
| กระจก จับคู่ ขโมย | กระดานสมมาตร; เล่นสมบูรณ์แบบ; พจน์เป็นคู่ | หลักสมดุลของนิม |
| ระบายสีให้ขัดแย้ง | พื้นที่ว่าได้ ความพยายามว่าไม่ | สิบคูณสิบที่ไม่ยอมแพ้ใคร |
ห้าวิธีจบการต่อสู้ก่อนมันจะเริ่ม — แต่ละวิธีแทนที่การค้นหาด้วยข้อสังเกตหนึ่งข้อ ซึ่งคือเหตุผลเป๊ะๆ ว่าทำไมท่าพวกนี้จึงเป็นสิ่งที่เครื่องจักรริเริ่มเองได้ยากที่สุดแต่ตรวจได้ง่ายที่สุด เครื่องมือของบทถัดไปทำงานตรงกันข้าม พวกมันสร้าง
บทถัดไป · 15 / 21เครื่องมือนักสร้าง