เครื่องมือนักสร้าง
ท่าสังหารจบปัญหาด้วยการสังเกตครั้งเดียว เครื่องมือทั้งห้าชิ้นนี้ทำงานตรงกันข้าม: มันสร้าง — คำตอบ การปูกระเบื้อง ตารางงาน กลยุทธ์ — ทีละชิ้น พร้อมบทพิสูจน์ติดรถมาด้วย รูปแบบเดิม: นิยาม สัญญาณ โจทย์คู่ฝึกมือ และเครื่องจักร
อุปนัย กับศิลปะแห่งการขอมากกว่าเดิม
เครื่องมือ. พิสูจน์กรณีฐาน แล้วพิสูจน์ว่าแต่ละกรณีบังคับกรณีถัดไป ฝีมือที่ไม่เห็นชัดอยู่สูงขึ้นไปหนึ่งชั้น: บางครั้งข้อความ P พิสูจน์ด้วยอุปนัยไม่ได้ แต่ข้อความที่*แรงกว่า*กลับแล่นฉลุย — เพราะขั้นอุปนัยได้*สมมุติ*สมมุติฐานมาใช้ และข้อความที่แรงกว่าก็คือเครื่องมือที่แรงกว่าด้วย Pólya (โพลยา) ตั้งชื่อปรากฏการณ์นี้ว่าปฏิทรรศน์นักประดิษฐ์ (inventor's paradox): พิสูจน์ให้มากกว่าอาจง่ายกว่า นี่คือคานงัดที่สวนสัญชาตญาณที่สุดเพียงหนึ่งเดียวในการเปลี่ยนผ่านจากมือใหม่สู่นักโอลิมปิก
กลิ่น. ข้อความใดๆ ที่มีพารามิเตอร์ n; โครงสร้างเวียนเกิดหรือคล้ายตัวเอง — ต้นไม้ การปูกระเบื้องบนกระดาน 2ⁿ นิพจน์ซ้อนกัน ตัวจุดชนวนของการเสริมแรงนั้นเฉพาะเจาะจงและควรค่าแก่การจำขึ้นใจ: ขั้นอุปนัยของคุณ*เกือบ*ทำงาน แต่สมมุติฐานอ่อนเกินกว่าจะดันให้ผ่าน — มันต้องการข้อเท็จจริงที่ข้อความฉบับธรรมดาไม่ได้แบกมา คำตอบไม่ใช่การทิ้งอุปนัย แต่คือบรรทุกสัมภาระที่ขาดหายลงไปในตัวข้อความ — ขอบเขตที่คมกว่า การจัดวางที่กว้างกว่า — แล้วรันใหม่
★★ · ผลบวกของจำนวนคี่
จงพิสูจน์ว่า 1 + 3 + 5 + ⋯ + (2n − 1) = n²
หยุดก่อน วาดรูปมันก่อนจะพิสูจน์มัน
เฉลย. ฐาน n = 1: 1 = 1² ขั้นอุปนัย: สมมุติว่าผลบวกถึง (2n − 1) เท่ากับ n²; บวกจำนวนคี่ตัวถัดไป: n² + (2n + 1) = (n + 1)² ∎ ภาพดีกว่าพีชคณิต: จัตุรัส n × n โตเป็นจัตุรัส (n + 1) × (n + 1) โดยห่อเปลือกรูปตัว L หนา 2n + 1 ช่องพอดีรอบสองด้าน อุปนัยในฐานะเรขาคณิตของการพอกพูน
ท่า — ไต่จาก n สู่ n + 1. เครื่องมือที่เรียบที่สุดในเล่ม — และเป็นโครงรถที่การขัดเกลาทุกชิ้นด้านล่างขันน็อตยึดเข้าใส่
★★★ · กระดานแหว่ง
จงพิสูจน์ว่ากระดาน 2ⁿ × 2ⁿ ที่หายไปหนึ่งช่องใดก็ตาม ปูเต็มได้ด้วย L-tromino (สามช่องเรียงเป็นรูปตัว L)
หยุดตรงนี้ บทที่ 9 พิสูจน์ว่ากระดานเป็นไปไม่ได้ คราวนี้จงสร้างขึ้นมาสักแผ่น
เฉลย. การเสริมแรงอยู่ในตัวโจทย์แล้ว — และนั่นแหละคือบทเรียน คำถามฉบับ "ธรรมชาติ" (*มุม*หายหนึ่งช่อง) กลับอุปนัยยากกว่า: กระดานที่ผ่าสี่ยื่นกระดานย่อยที่ไม่มีมุมแหว่งมาให้ และสมมุติฐานก็ไม่มีที่ให้เกาะ จงพิสูจน์ฉบับแรงกว่า "หายช่องไหนก็ได้" แทน ฐาน n = 1: กระดาน 2 × 2 ที่หายช่องใดช่องหนึ่ง*คือ* L-tromino หนึ่งตัวพอดี ขั้นอุปนัย: ผ่ากระดาน 2ⁿ⁺¹ เป็นสี่จตุภาคขนาด 2ⁿ; ช่องที่หายอยู่ในจตุภาคหนึ่ง วาง tromino ตัวเดียวตรงกลาง คลุมช่องมุมของ*อีกสามจตุภาค*ที่เหลือ จตุภาคละหนึ่งช่อง บัดนี้ทุกจตุภาคคือกระดาน 2ⁿ × 2ⁿ ที่หายไปหนึ่งช่องพอดี — ใช้สมมุติฐานฉบับแรงกว่าสี่ครั้ง ∎ (ตรวจนับ: (4ⁿ⁺¹ − 1)/3 = 4·(4ⁿ − 1)/3 + 1 — ผลิตรอยแหว่งให้สามจตุภาค จ่าย tromino ไปหนึ่งตัว ✓)
นี่คือฝาแฝดสายสร้างของการระบายสีในบทที่ 9: สีพิสูจน์ความเป็นไปไม่ได้ อุปนัยผลิตความเป็นไปได้
ท่า — วางนัยทั่วไปจนขั้นอุปนัยมีที่เกาะ. ข้อความที่ทั่วไปกว่ายื่นของให้ขั้นอุปนัยจับมากกว่า ถ้าการผ่าสี่ของปัญหาผลิตปัญหาย่อยที่สมมุติฐานของคุณแตะไม่ถึง จงขยายสมมุติฐานจนแตะถึง
★★★★ · เบาะรองที่ทำจากความว่างเปล่า
จงพิสูจน์ว่า 1/1² + 1/2² + ⋯ + 1/n² < 2 สำหรับทุก n
หยุดก่อน ลองอุปนัยแบบเห็นๆ แล้วดูมันตายต่อหน้า
เฉลย. อุปนัยแบบเห็นๆ: สมมุติ Sₙ < 2; แล้ว Sₙ₊₁ = Sₙ + 1/(n + 1)² < 2 + อะไรสักอย่าง ไม่มีที่ว่างเหลือ ข้อความนี้จริงแต่เป็นหมันเชิงอุปนัย — สมมุติฐานไม่เหลืออะไรไว้ดูดซับพจน์ใหม่
เสริมแรงมัน: พิสูจน์ Sₙ ≤ 2 − 1/n ฐาน n = 1: S₁ = 1 = 2 − 1 ขั้นอุปนัย: เมื่อได้ Sₙ ≤ 2 − 1/n เพียงพอที่จะแสดงว่า 1/(n + 1)² ≤ 1/n − 1/(n + 1) = 1/(n(n + 1)) นั่นคือ n(n + 1) ≤ (n + 1)² นั่นคือ n ≤ n + 1 ซึ่งจริง ดังนั้น Sₙ₊₁ ≤ 2 − 1/(n + 1) และโดยเฉพาะ Sₙ < 2 สำหรับทุก n ∎
ข้อความที่แรงกว่าแบกเชื้อเพลิงของตัวเองมาด้วย: พจน์ −1/n คือเบาะดูดซับที่ขั้นอุปนัยต้องการพอดิบพอดี (ภายหลัง Euler แสดงว่าลิมิตแท้จริงคือ π²/6 ≈ 1.645 — เบาะของเราห่างจากค่าคมลิบลับ และนั่นไม่เป็นไรเลย การเสริมแรงต้องเพียง*ปิดวงอุปนัยได้* ไม่จำเป็นต้องคม)
ท่า — เสริมแรงสมมุติฐาน. สมมุติฐานอุปนัยไม่ใช่สิ่งที่คุณต้องพิสูจน์ แต่คือสิ่งที่คุณได้หยิบมาใช้ เมื่อขั้นอุปนัยรั่ว จงถามคำถามกลับหัวของ Pólya: ข้อความที่แรงกว่าแบบไหนจะทำให้ขั้นนี้กลายเป็นเรื่องจิ๊บจ๊อย?
เครื่องจักรกับท่านี้. การเสริมแรงสมมุติฐานคือการประดิษฐ์บทตั้ง (lemma) — คอขวดคลาสสิกของการพิสูจน์ทฤษฎีบทอัตโนมัติ ซึ่งมีฮิวริสติกแต่ไม่มีวิธีที่วางใจได้ — และโมเดลเลียนแบบการเสริมแรงอันโด่งดังได้ดี แต่แทบไม่เคยให้กำเนิดการวางนัยทั่วไปที่ถูกต้องขึ้นสดๆ เอง; มนุษย์*รู้สึก*ได้ว่าขั้นอุปนัยรั่วตรงไหน แล้วปะที่ตัวข้อความ
การเวียนเกิด → Dynamic Programming
เครื่องมือ. เขียนคำตอบของปัญหาในรูปคำตอบของอินสแตนซ์ที่เล็กกว่า; เมื่อปัญหาย่อยซ้ำหน้าเดิม ก็แคชมันไว้ (memoization) หรือเติมจากล่างขึ้นบน (dynamic programming — DP) ตำราขาย DP ในฐานะเทคนิค แต่นักแข่งรู้จักมันในฐานะ*คำถามเชิงการแทน*: เลือกว่า "สถานะ" คืออะไร — บทสรุปย่อที่สุดของอดีตที่อนาคตต้องใช้ — แล้วความสัมพันธ์เวียนเกิดมักเขียนตัวมันเองออกมา บันไดคลาสสิกไต่ทีละมิติ: Fibonacci (หนึ่งมิติ — จำนวนวิธีปูแถบ 1 × n ด้วยชิ้นยาว 1 กับ 2), เส้นทางบนกริด (สองมิติ), knapsack (ทรัพยากร), bitmask DP (เซต), digit DP กับ tree DP (พรีฟิกซ์ที่มีโครงสร้าง)
กลิ่น. "นับจำนวนวิธี…" "ต้นทุนต่ำสุดที่จะ…" "ยาวที่สุด … บนลำดับ กริด ต้นไม้" ปัญหาแตกตัวตามคำถาม "ทางเลือกสุดท้ายคืออะไร?" Brute force เป็นเอกซ์โพเนนเชียล แต่อดีตที่*เกี่ยวข้องจริง*มีขนาดเล็ก เช็กลิสต์ของมืออาชีพ เรียงตามลำดับ: การตัดสินใจคืออะไรบ้าง? หลังพรีฟิกซ์ของการตัดสินใจชุดหนึ่ง อนาคตต้องรู้อะไรจริงๆ? — นั่นแหละคือสถานะ ทรานซิชันคือการตัดสินใจหนึ่งครั้ง; ต้นทุนคือ #สถานะ × ต้นทุนทรานซิชัน; และถ้ามันใหญ่เกินไป แปลว่าสถานะกำลังแบกขยะ — บีบอัดมันซะ
★★ · ยี่สิบเส้นทาง
มีเส้นทางโมโนโทน — เดินขวากับลงเท่านั้น — กี่เส้น จากมุมบนซ้ายสู่มุมล่างขวาของแลตทิซโหนดขนาด 4 × 4 จาก (0,0) ถึง (3,3)?
หยุดก่อน แก้มุมบนซ้ายของคำถามเสียก่อน
เฉลย. สถานะ: f(i, j) = จำนวนเส้นทางโมโนโทนที่มาถึงโหนด (i, j) คุณมาจากข้างบนหรือจากซ้าย ดังนั้น f(i, j) = f(i−1, j) + f(i, j−1) โดยตลอดขอบเป็น 1 ทั้งหมด เติมตาราง:
| j=0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| i=0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 |
| 2 | 1 | 3 | 6 | 10 |
| 3 | 1 | 4 | 10 | 20 |
คำตอบ: 20 และมองตารางสิ — มันคือสามเหลี่ยม Pascal วางเอียง: f(i, j) = C(i+j, i) ที่นี่ C(6,3) = 20 ✓ ∎
ท่า — ตั้งชื่อสถานะ แล้วเติมตาราง. การเวียนเกิด ("ก้าวสุดท้ายมาจากซ้ายหรือบน") นั้นจิ๊บจ๊อย; รางวัลคือรูปปิดที่ผุดเป็นตัวขึ้นมาจากตาราง dynamic programming ในฐานะคณิตศาสตร์เชิงทดลอง
★★★★ · Knapsack ตั้งแต่ต้นจนจบ
ความจุ W = 8 สิ่งของ: A (น้ำหนัก 2, มูลค่า 3), B (3, 4), C (4, 5), D (5, 8) จงทำมูลค่ารวมให้มากที่สุดภายในความจุ — และจงรู้*ว่าทำไม*อัลกอริทึมตะกละ (greedy) จึงพลาด
หยุดตรงนี้ ลองตะกละดูก่อน โดยเจตนา
เฉลย. ตะกละตามความหนาแน่นมูลค่า: D = 1.6, A = 1.5, B ≈ 1.33, C = 1.25 ความตะกละคว้า D (น้ำหนัก 5) แล้วคว้า A (น้ำหนัก 2) — มูลค่า 11 น้ำหนัก 7 ไม่มีชิ้นไหนใส่ลงได้อีก 11 ไม่ใช่ค่าเหมาะที่สุด
ทีนี้ DP สถานะ: dp[c] = มูลค่าดีที่สุดที่ทำได้ภายในความจุ c เมื่อคิดเฉพาะสิ่งของที่ประมวลมาแล้ว; ประมวลสิ่งของทีละชิ้น กวาด c จากมากลงน้อยเพื่อให้แต่ละชิ้นถูกใช้ได้อย่างมากหนึ่งครั้ง เริ่มต้นเป็นศูนย์ทั้งหมด
- หลัง A: dp = [0, 0, 3, 3, 3, 3, 3, 3, 3]
- หลัง B: dp = [0, 0, 3, 4, 4, 7, 7, 7, 7] (เช่น dp[5] = max(3, dp[2] + 4) = 7)
- หลัง C: dp = [0, 0, 3, 4, 5, 7, 8, 9, 9] (dp[6] = max(7, dp[2] + 5) = 8; dp[7] = max(7, dp[3] + 5) = 9)
- หลัง D: dp = [0, 0, 3, 4, 5, 8, 8, 11, 12] (dp[7] = max(9, dp[2] + 8) = 11; dp[8] = max(9, dp[3] + 8) = 12)
ค่าเหมาะที่สุดคือ 12 = B + D: น้ำหนัก 3 + 5 = 8 มูลค่า 4 + 8 — เลข 11 ของความตะกละแพ้ 12 (ทวนสอบกับการแจกแจงครบทั้ง 2⁴ สับเซต: ตัวเต็งที่เป็นไปได้คือ A+D = 11, B+D = 12, B+C = 9, A+C = 8) ต้นทุน: 4 ชิ้น × 9 ระดับความจุ ≈ 36 การอัปเดตช่องตาราง แทนการเช็ก 16 สับเซต — และที่ n = 100, W = 100,000 ตารางแบบเดียวกันนี้แทนที่ 2¹⁰⁰ สับเซต คำเตือนซื่อตรงหนึ่งข้อ: O(nW) เป็น pseudo-polynomial — W เป็นเอกซ์โพเนนเชียลในจำนวนหลักของตัวมันเอง — knapsack จึงยังเป็น NP-hard ∎
ท่า — บีบอัดประวัติศาสตร์ให้เหลือสถิติที่พอเพียง. สถานะ*ไม่ใช่* "หยิบชิ้นไหนไปแล้วบ้าง" (2ⁿ สถานะ) แต่คือ "ใช้ความจุไปเท่าไร" — เพราะมูลค่าคือทั้งหมดที่อนาคตต้องการ และความจุคือทั้งหมดที่พันธนาการอนาคต DP ยากทุกข้อยากตรงนี้แหละ: longest-increasing-subsequence บีบ "พรีฟิกซ์ทั้งก้อน" เหลือ "หางเล็กสุดต่อความยาว"; DP ของ traveling-salesman บีบ "เส้นทางที่ผ่านมา" เหลือ "(เซตที่เยือนแล้ว, เมืองปัจจุบัน)"; digit DP บีบ "ตัวเลขที่สร้างมา" เหลือ "(ตำแหน่ง, ยังชิดขอบบนอยู่ไหม?, สมบัติที่สะสมมา)" ท่าเดียวกัน ไต่ขึ้นบันไดไปเรื่อยๆ
เครื่องจักรกับท่านี้. เครื่องมือที่เป็นมิตรกับเครื่องจักรที่สุดในคลังแสง — พอสถานะถูกนิยามแล้ว การเติมตารางคือสิ่งที่คอมพิวเตอร์*เป็น*อยู่แล้วโดยกำเนิด และบันไดคลาสสิกก็อิ่มตัวอยู่ในข้อมูลฝึกของพวกมัน; ขอบที่เหลือของมนุษย์คือการ*ประดิษฐ์*สถานะ — การมองออกว่าประวัติศาสตร์หน้าตาพิสดารยุบลงเหลือสถิติพอเพียงตัวเล็กๆ ได้
อัลกอริทึมตะกละ กับการพิสูจน์แบบสลับชิ้น
เครื่องมือ. อัลกอริทึมตะกละ (greedy) เลือกทางที่ดีที่สุดเฉพาะหน้าแล้วไม่หวนกลับมาแก้ ความตะกละมักผิด; ยามใดที่มันถูก บทพิสูจน์มาตรฐานคือการพิสูจน์แบบสลับชิ้น (exchange argument): หยิบคำตอบเหมาะที่สุด OPT ใดๆ มา แสดงว่าสลับตัวเลือกหนึ่งของมันเป็นตัวเลือกของตะกละได้โดยไม่แย่ลง แล้วอุปนัยต่อ — ผลลัพธ์ของตะกละจึงทาบเท่า OPT (ฉบับโครงสร้างลึกบอกว่าตะกละเหมาะที่สุดพอดีเป๊ะบน matroid; นักแข่งส่วนใหญ่ควงบทตั้งสลับชิ้นกันตรงๆ)
กลิ่น. จัดตารางเวลา คัดเลือก ผสาน เรียงลำดับ — ที่ใดก็ตามที่ sort ตามกุญแจที่ถูกต้อง ฟังดูมีเค้า และอนาคตขึ้นกับอดีตผ่านแค่ยอดสะสมหรือแนวหน้าเท่านั้น รีเฟล็กซ์ที่มีวินัยต้องสองด้าน: ล่าการสลับชิ้น และ ล่าตัวอย่างค้านด้วยพลังงานเท่ากัน — n เล็กๆ น้ำหนักเจตนาร้าย ถ้าสิบนาทีแล้วไม่มีฝ่ายไหนชนะ ให้สงสัยว่าเป็น DP แทน และจงพกกระสุนเตือนที่นักแข่งทุกคนเคยโดนมาแต่หัดใหม่: เหรียญ {1, 3, 4} จำนวนเงิน 6 ตะกละ: 4 + 1 + 1 สามเหรียญ เหมาะที่สุด: 3 + 3 สองเหรียญ ตะกละพร้อมบทพิสูจน์เท่านั้น ไม่งั้นไม่ต้องส่ง
★★ · เลือกนัดประชุม
จากช่วง [0,2), [1,3), [2,4), [3,5), [4,6) จงเลือกจำนวนช่วงมากที่สุดที่ไม่ทับซ้อนกันเป็นคู่ๆ
หยุดก่อน คุณจะ sort ด้วยกุญแจไหน?
เฉลย. กฎตะกละ: หยิบช่วงที่จบเร็วที่สุดในบรรดาช่วงที่เข้ากันได้กับที่ถืออยู่ ทำซ้ำไปเรื่อยๆ ไล่รอย: หยิบ [0,2); ข้าม [1,3); หยิบ [2,4); ข้าม [3,5); หยิบ [4,6) — 3 การประชุม และ 3 คือค่ามากที่สุด (ช่วงยาว 2 สี่ช่วงที่ไม่ทับกันเป็นคู่ ต้องกินความยาวรวม 8 ในพิสัยแค่ 6)
บทพิสูจน์สลับชิ้นของกฎ: ให้ g₁ เป็นช่วงที่จบเร็วที่สุดในทั้งหมด และ o₁ เป็นสมาชิกที่เริ่มเร็วที่สุดของเซตเหมาะที่สุด OPT ใดๆ แล้ว finish(g₁) ≤ finish(o₁) ดังนั้น OPT − {o₁} + {g₁} ยังไม่ทับกันเป็นคู่อยู่ดี — g₁ จบไม่ช้ากว่า o₁ จึงชนกับสมาชิกที่เหลือของ OPT ไม่ได้ — และมีขนาดเท่าเดิม จึงมีคำตอบเหมาะที่สุดสักชุดที่เริ่มต้นด้วยตัวเลือกของตะกละ; เวียนทำต่อบนพิสัยที่เหลือ ∎
ท่า — ปั้น OPT ให้กลายร่างเป็นตะกละ. บทพิสูจน์ไม่เคยพูดว่าตะกละชนะ OPT มันพูดว่า OPT ถูกปั้นรูปใหม่ให้เป็นตะกละได้ ทีละการสลับที่ไม่เสียอะไรเลย — แม่แบบที่หยิบใช้ซ้ำได้ครึ่งวงการอัลกอริทึม
★★★★ · จำนวนที่ใหญ่ที่สุด
กำหนดจำนวนเต็มบวก — เช่น {9, 5, 34, 3, 30} — จงเรียงพวกมันเป็นแถว ให้การนำหลักฐานสิบมาต่อกันได้จำนวนที่ใหญ่ที่สุดเท่าที่เป็นไปได้
หยุดตรงนี้ sort แบบเห็นๆ นั้นผิด จงหาตัวเปรียบเทียบที่ถูก
เฉลย. Sort ด้วยตัวเปรียบเทียบ: ให้ x มาก่อน y เมื่อผลต่อ xy มากกว่า yx (เทียบกันในฐานะจำนวน) ไล่รอย: 9 กับ 5 → "95" > "59"; 34 กับ 3 → "343" > "334" ดังนั้น 34 นำหน้า 3; 3 กับ 30 → "330" > "303" ดังนั้น 3 นำหน้า 30 ลำดับ: 9, 5, 34, 3, 30 — คำตอบ 9534330 (ชนะ ตัวอย่างเช่น 9, 5, 3, 34, 30 → 9533430)
ทำไมท่านี้จึงชอบธรรม — หนี้สองก้อนที่นักแก้ส่วนใหญ่เบี้ยว:
- ตัวเปรียบเทียบเป็นอันดับรวมของแท้ เขียน X แทนค่าของ x และ ℓₓ แทนจำนวนหลักของมัน: xy > yx ⟺ X·10^ℓʸ + Y > Y·10^ℓˣ + X ⟺ X(10^ℓʸ − 1) > Y(10^ℓˣ − 1) ⟺ X/(10^ℓˣ − 1) > Y/(10^ℓʸ − 1) กฎจับคู่หน้าตาพิลึกนี้แอบเป็นการ sort ตามกุญแจจำนวนจริงตัวเดียว κ(x) = X/(10^ℓˣ − 1) — จึงถ่ายทอดได้ จึงเป็น sort ที่ใช้การได้ และ κ มีคำอ่านน่ารัก: κ(34) = 34/99 = 0.343434…, κ(3) = 3/9 = 0.333… — หลักของแต่ละจำนวนวนซ้ำไปชั่วนิรันดร์ การจัดเรียงนี้ sort ตาม*สิ่งที่คุณจะกลายเป็น หากทำซ้ำตัวเองไม่รู้จบ*
- สลับชิ้นเพื่อความเหมาะที่สุด ในการจัดเรียงใดๆ ถ้ามีคู่*ติดกัน*สักคู่วางค้านตัวเปรียบเทียบ (…yx… ทั้งที่ xy > yx) การสลับสองตัวนั้นเปลี่ยนแค่รอยต่อจุดนั้น — หลักอื่นทุกหลักคงตำแหน่งเดิม — และทำให้จำนวนทั้งก้อนใหญ่ขึ้นโดยแท้ การจัดเรียงใดที่ไม่เรียงตาม sort ย่อมมีคู่ติดกันที่กลับลำดับเช่นนี้ จึงไม่เหมาะที่สุด; การจัดเรียงตาม sort คือค่ามากที่สุด โดยตัวที่ κ เท่ากันสลับกันได้ ∎
ท่า — พิสูจน์หนี้ทั้งสองก้อน. กฎตะกละติดหนี้อยู่สองก้อน: ความคงเส้นคงวา (ตัวเปรียบเทียบต้องถ่ายทอดได้ — และภาษาโปรแกรมยินดีจะ "sort" ด้วยตัวเปรียบเทียบที่ไม่ถ่ายทอดออกมาเป็นความไร้สาระ) และ*เสถียรภาพต่อการสลับชิ้น* จ่ายให้ครบทั้งคู่ ไม่งั้นอย่าส่งคำตอบ
เครื่องจักรกับท่านี้. โมเดลภาษาเสนอกฎตะกละได้คล่องปาก และแต่งเรื่อง (hallucinate) ความถูกต้องของมันขึ้นมาเอง; รีเฟล็กซ์ {1, 3, 4} — โจมตีกฎของตัวเองก่อนจะเชื่อมัน — คือนิสัยปรปักษ์ที่ต้องฝึกฝน ไม่ใช่ค่าโรงงาน
ไบนารีเสิร์ชบนคำตอบ
เครื่องมือ. จะหาค่าเหมาะที่สุดของปริมาณที่คำนวณตรงๆ ยาก ให้พลิกคำถาม: มีคำตอบที่ค่าอย่างน้อย x ไหม? ถ้าความเป็นไปได้โมโนโทนใน x — เป็นไปได้ที่ x แปลว่าเป็นไปได้ตลอดทั้งซีกหนึ่ง — ค่าเหมาะที่สุดก็คือธรณีประตู และไบนารีเสิร์ชหามันเจอด้วยการเรียกกระบวนการ*ตัดสิน*เพียง O(log พิสัย) ครั้ง คุณเพิ่งแลก "หาค่าเหมาะที่สุด" กับ "ตัดสิน" และการตัดสินแทบจะง่ายกว่าเสมอ: greedy สักตัว หรือเช็กกราฟสักรอบ
กลิ่น. คาถาวิเศษ: ทำค่ามากสุดให้น้อยสุด, ทำค่าน้อยสุดให้มากสุด — "ระยะห่างต่ำสุดที่ใหญ่ที่สุด" "เวลาน้อยที่สุดที่งานทุกชิ้นเสร็จครบ" อีกกลิ่น: คำตอบเป็นตัวเลขตัวเดียวในพิสัยจำกัด และการเช็กผู้สมัครนั้นง่าย แม้การผลิตตัวที่ดีที่สุดจะยาก รีเฟล็กซ์: ถามว่า "ถ้าออราเคิลกระซิบคำตอบ x มาให้ ฉันทวนสอบคำตอบที่ระดับ x ได้ถูกๆ ไหม?" ถ้าใช่ และโมโนโทน — ปัญหาแก้เสร็จแล้ว เหลือแค่ซับรูทีนเช็กความเป็นไปได้
★★ · โรงเลื่อย
ต้นไม้สูง 20, 15, 10, 17 ใบเลื่อยตั้งที่ความสูง H จะตัดทุกอย่างที่อยู่เหนือ H เก็บไม้ได้ Σ max(0, hᵢ − H) หน่วย จงหาจำนวนเต็ม H ที่ใหญ่ที่สุดที่เก็บไม้ได้อย่างน้อย 7 หน่วย (โจทย์คลาสสิกจากเว็บฝึกซ้อม รู้จักกันในชื่อ EKO)
หยุดก่อน อย่าหาค่าเหมาะที่สุด เดาแล้วเช็ก — อย่างมีประสิทธิภาพ
เฉลย. ความเป็นไปได้ f(H) = "wood(H) ≥ 7" ปริมาณไม้ไม่เพิ่มตาม H ดังนั้น f โมโนโทน: จริงข้างล่าง เท็จข้างบน ไบนารีเสิร์ชบน [0, 20]:
- H = 10: ไม้ = 10 + 5 + 0 + 7 = 22 ≥ 7 ✓ → ขยับสูงขึ้น, [10, 20]
- H = 15: ไม้ = 5 + 0 + 0 + 2 = 7 ≥ 7 ✓ → [15, 20]
- H = 18: ไม้ = 2 + 0 + 0 + 0 = 2 ✗ → [15, 17]
- H = 16: ไม้ = 4 + 0 + 0 + 1 = 5 ✗ → [15, 15]
คำตอบ H = 15 (wood(15) = 7 ✓, wood(16) = 5 ✗) การเรียกตัดสินห้าครั้งแทนการกวาดทุกความสูง; ถ้าความสูงไปได้ถึง 10⁹ ก็ราวสามสิบครั้ง ลอการิทึมคือโมเดลธุรกิจทั้งหมดของท่านี้ ∎
ท่า — ซักถามผู้สมัคร ไม่ใช่ค่าเหมาะที่สุด. ถ้าคำตอบที่ถูกกระซิบมาจะเช็กได้ง่าย จงเลิกพยายามคำนวณมัน แล้วเริ่มผ่าครึ่งไล่หามัน
★★★★ · วัวจอมห้าว
คอกอยู่ที่ตำแหน่ง 1, 2, 4, 8, 9 บนเส้นตรง จงวางวัว 3 ตัวลงคอก ให้ระยะห่างต่ำสุดระหว่างวัวคู่ใดๆ ใหญ่ที่สุดเท่าที่เป็นไปได้ (ฉบับคลาสสิกรู้จักกันในชื่อ AGGRCOW)
หยุดตรงนี้ เครื่องมือสองชิ้นกำลังจะต้องประกอบร่างกัน
เฉลย. ฉบับตัดสิน: วางวัว 3 ตัวให้ทุกคู่ห่างกันอย่างน้อย d ได้ไหม? เช็กด้วยตะกละ: วางวัวตัวแรกที่คอกซ้ายสุด แล้วหยิบคอกถัดไปที่ห่างจากวัวตัวก่อนอย่างน้อย d เสมอ; นับจำนวนที่วางได้ ตัวเช็กนี้ต้องการบทพิสูจน์สลับชิ้นเล็กๆ ของตัวเอง: ถ้ามีการวาง k ตัวที่ช่องไฟ d แบบใช้ได้จริงอยู่สักแบบ การเลื่อนวัวซ้ายสุดของมันไปคอกซ้ายสุด และวัวตัวถัดๆ ไป ไปยังคอกเร็วที่สุดที่ ≥ d เลยตัวก่อนหน้า มีแต่จะเลื่อนวัวไปทางซ้ายหรืออยู่ที่เดิม ไม่มีวันละเมิด d — การวางแบบตะกละ-ชิดซ้ายจึงนั่งวัวได้ไม่น้อยกว่าแบบไหนๆ ดังนั้น "ตะกละนั่งได้ ≥ 3" สมมูลกับความเป็นไปได้ ความเป็นไปได้โมโนโทน — d ยิ่งใหญ่ยิ่งยาก — จึงไบนารีเสิร์ช d บน [1, 8]:
- d = 4: วางที่ 1 → ถัดไป ≥ 5 → 8 → ถัดไป ≥ 12 → ไม่มี ได้วัวสองตัว < 3 ✗ → [1, 3]
- d = 2: 1 → 4 → 8 วัวสามตัว ✓ → [2, 3]
- d = 3: 1 → 4 → 8 ช่องไฟ 3 กับ 4 วัวสามตัว ✓ → [3, 3]
คำตอบ d = 3 โดยแสดงแล้วว่า d = 4 เป็นไปไม่ได้ ∎
เนื้อหาระดับ ★★★★ อยู่ที่ตัวกรอบ: นักแก้ไม่เคยหาค่าเหมาะที่สุดของอะไรเลยสักอย่าง "ทำค่าน้อยสุดให้มากสุด" ละลายหายกลายเป็น (ก) การมองเห็นความโมโนโทน (ข) ตัวเช็กตัดสินแบบตะกละที่พกบทพิสูจน์สลับชิ้นของตัวเองมาด้วย (ค) การทำซ้ำแค่หลักลอการิทึมครั้ง เครื่องมือประกอบเครื่องมือ — หมวดนี้อยู่เปลือกนอก หมวดก่อนหน้าอยู่ไส้ใน
ท่า — ละลาย "ทำค่าน้อยสุดให้มากสุด" ให้เป็นความเป็นไปได้. ค่าเหมาะที่สุดคือธรณีประตู; จงล่าธรณีประตู ไม่ใช่ล่าคำตอบ
เครื่องจักรกับท่านี้. กลไกล้วนๆ ทันทีที่ความโมโนโทนถูก*ประกาศ*ไว้ — นี่อาจเป็นแพตเทิร์นที่พบบ่อยที่สุดในข้อมูลฝึกสายแข่งเขียนโปรแกรมของโมเดล; ขั้นตอนของมนุษย์คือการรับรองความโมโนโทนบนปัญหารกๆ ที่ซึ่ง "โมโนโทนชัดๆ" บางทีก็ไม่โมโนโทน จงพิสูจน์นัยหนึ่งบรรทัดนั้นก่อนจะเชื่อการเสิร์ช
คิดย้อนจากปลายทาง
เครื่องมือ. เริ่มจากสถานะเป้าหมายแล้วคำนวณตัวก่อนหน้า แทนการสำรวจเดินหน้าจากจุดเริ่ม ในเกมนี่คืออุปนัยย้อนกลับ (backward induction): ป้ายตำแหน่งจบเกมว่า ชนะ หรือ แพ้ แล้วแพร่ป้ายออกไป — ตำแหน่งหนึ่งเป็นฝ่ายชนะถ้ามีสักท่าเดินที่พาไปถึงตำแหน่งซึ่งแพ้สำหรับคู่ต่อสู้ เป็นฝ่ายแพ้ถ้าทุกท่าเดินพาไปถึงตำแหน่งชนะทั้งหมด ในปริศนามันคือ "ก้าวสุดท้ายจำต้องเป็นอะไร?" — ก้าวสุดท้ายมักถูกบีบรัดยิ่งกว่าก้าวแรกมาก ต้นไม้จากปลายด้านนั้นจึงผอมกว่า
กลิ่น. เป้าหมายระบุชัดแต่จุดเริ่มพร่ามัว: "ไปให้ถึง 100 พอดี" "จบด้วยโทเคนหนึ่งอัน" "รุกฆาตในสามตา" เกมข้อมูลสมบูรณ์ — "เล่นดีที่สุดแล้วใครชนะ?" ท่าเดินที่กลับทิศได้ง่ายกว่าเลือกเดินหน้า รีเฟล็กซ์: เมื่อการแตกกิ่งไปข้างหน้ากว้างแต่เป้าหมายแคบ จงปลูกต้นไม้จากปลายด้านแคบ — หรือจากทั้งสองปลายพร้อมกัน หั่นเลขชี้กำลังลงครึ่งหนึ่ง
★★ · วิ่งสู่ 100
สองโจทย์คลาสสิก โครงกระดูกเดียวกัน (ก) หิน 21 ก้อน; ผู้เล่นผลัดกันหยิบ 1, 2 หรือ 3 ก้อน; ใครหยิบก้อนสุดท้ายชนะ (ข) ผู้เล่นผลัดกันบวก 1 ถึง 10 เข้ายอดรวมที่เริ่มจาก 0; ใครพูด 100 ชนะ ใครชนะในแต่ละเกม และชนะอย่างไร?
หยุดก่อน เริ่มจากตอนจบ — ตามตัวอักษรเลย
เฉลย. (ก) ป้ายย้อนกลับ เผชิญหิน 0 ก้อนคือคุณแพ้ไปแล้ว — ผู้เล่นก่อนหน้าหยิบก้อนสุดท้ายไป เผชิญ 1–3 คุณชนะ (หยิบหมดกำมือ) เผชิญ 4 ทุกท่าเดินยื่นชัยชนะให้คู่ต่อสู้: 4 คือฝ่ายแพ้ แพร่ป้ายต่อไป ตำแหน่งแพ้คือพหุคูณของ 4 พอดิบพอดี — จาก 4k การหยิบ t ใดๆ เหลือจำนวนที่ไม่ใช่พหุคูณ; จาก 4k + r (r = 1, 2, 3) จงหยิบ r เนื่องจาก 21 ≡ 1 (mod 4) ผู้เล่นคนแรกชนะ: หยิบ 1 แล้วตอบทุก t ด้วย 4 − t คืนสภาพพหุคูณของ 4 เสมอ (ข) เครื่องยนต์เดียวกัน ฉบับบวกเลข: เป้าที่ต้อง*ยื่นให้คู่ต่อสู้*ไล่ย้อนจาก 100 ทีละ 11 — 100, 89, 78, …, 12, 1 — เพราะ k ของคู่ต่อสู้ถูกตอบด้วย 11 − k ของคุณ ผู้เล่นคนแรกพูด 1 แล้วไต่ 12, 23, …, 89, 100 ∎
เล่นเดินหน้าที่ 21 เห็นต้นไม้พุ่มหนาทึบ; การป้ายย้อนกลับให้ทฤษฎีทั้งหมดออกมาเป็นลำดับเลขคณิตเดียว มันยังปลูกมโนทัศน์ทั่วไปไว้ด้วย — ตำแหน่งเย็น (แพ้สำหรับผู้ถึงตาเดิน) ปะทะตำแหน่งร้อน — โครงกระดูกเป็นคาบที่รองรับทฤษฎีเกมตระกูล Nim: คอลัมน์สมดุลของบทที่ 9 ก็คือตำแหน่งเย็นของ Nim เป๊ะๆ และทฤษฎีฉบับทั่วไป (Sprague–Grundy) ก็งอกจากเมล็ดนี้
ท่า — ป้ายจากตอนจบ. เป้าหมายคือสถานะเดียว จุดเริ่มมีนับไม่ถ้วน จงคำนวณ ชนะ/แพ้ กระจายออกจากเป้าหมาย แล้วอ่านคำตอบออกจากตารางของคุณเอง
★★★★ · เกมของ Wythoff กับอัตราส่วนทอง
กองหินสองกอง ท่าเดิน: หยิบจำนวนบวกเท่าใดก็ได้จากกองเดียว หรือ หยิบจำนวนบวก*เท่ากัน*จากทั้งสองกอง หินก้อนสุดท้ายเป็นของผู้ชนะ จงบรรยายลักษณะตำแหน่งแพ้ทั้งหมด
หยุดตรงนี้ บดกรณีเล็กๆ ก่อนจะตั้งทฤษฎี
เฉลย. ป้ายย้อนกลับสถานะเล็กๆ นับคู่แบบไม่จัดอันดับ (0,0) คือแพ้ — ผู้ถึงตาเดินเผชิญความว่างเปล่า ผู้เล่นก่อนหน้าหยิบก้อนสุดท้ายไปแล้ว ทุกอย่างที่ไปถึง (0,0) ได้ในหนึ่งท่า — ทุก (k,0) และ (k,k) — คือชนะ กวาดขึ้นไปหาสถานะถัดไปที่ทางออกทุกทางเป็นชนะ: (1,2) ท่าเดินของมันไปถึง (0,2), (1,1), (1,0) และทางทแยง (0,1) — แต่ละตัวชนะ (แต่ละตัวถึง (0,0) ได้ในหนึ่งท่า) ดังนั้น (1,2) แพ้ ตัดทุกอย่างที่ไปถึง (0,0) หรือ (1,2) ได้ทิ้งไป ผู้สมัครถัดไปคือ (3,5) ท่ากองเดียวของมันไปถึง (0,5), (1,5), (2,5), (3,4), (3,3), (3,2), (3,1), (3,0); ท่าทแยงไปถึง (2,4), (1,3), (0,2) ทุกตัวชนะหมด: (0,5), (3,0), (0,2) แตะ (0,0) ได้ตรงๆ และ (3,3) แตะได้ทางทแยง; (1,5) → (1,2) โดยหยิบ 3; (2,5) → (2,1) โดยหยิบ 4; (3,2) → (1,2) โดยหยิบ 2; (1,3) → (1,2) โดยหยิบ 1; (3,1) → (2,1) โดยหยิบ 1; (3,4) → (1,2) ด้วยทแยง −2; (2,4) → (2,1) โดยหยิบ 3 (คู่ไม่จัดอันดับ: (2,1) ก็คือ (1,2)) ดังนั้น (3,5) แพ้ ตะแกรงร่อนต่อไป: (0,0), (1,2), (3,5), (4,7), (6,10), (8,13), …
ข้อเท็จจริงเชิงโครงสร้างสองข้อร่วงออกมาจากตาราง: จำนวนเต็มบวกทุกตัวปรากฏในคู่แพ้เพียงคู่เดียวพอดี และคู่ตัวที่ k ต่างกัน k พอดี รูปปิด (Wythoff, 1907): ตำแหน่งแพ้ตัวที่ k คือ (⌊kφ⌋, ⌊kφ²⌋) โดย φ = (1 + √5)/2 ตรวจ — k = 1: (1, 2); k = 2: (⌊3.236⌋, ⌊5.236⌋) = (3, 5); k = 3: (⌊4.854⌋, ⌊7.854⌋) = (4, 7) ✓ ทำไมต้องอัตราส่วนทอง: ทฤษฎีบทของ Beatty กล่าวว่าลำดับ ⌊kα⌋ กับ ⌊kβ⌋ แบ่งกั้นเซตจำนวนเต็มบวกพอดี ก็ต่อเมื่อ 1/α + 1/β = 1 — และ 1/φ + 1/φ² = 1; ขณะที่ φ² = φ + 1 ทำให้ช่องว่างของคู่ตัวที่ k เท่ากับ k พอดี สมบัติสองข้อนี้คือกฎของตะแกรงเป๊ะๆ: คู่แพ้ใหม่แต่ละคู่ใช้จำนวนเต็มตัวเล็กสุดที่ยังไม่ถูกใช้ (สมบัติการแบ่งกั้น) พร้อมช่องว่าง k (สมบัติท่าทแยง) ∎
การวิเคราะห์ถอยหลัง (retrograde analysis) คือการทดลอง; อัตราส่วนทองคือทฤษฎี เวิร์กโฟลว์ที่ซื่อตรง — บดตารางย้อนกลับ จ้องมอง ตั้งข้อคาดการณ์ แล้วพิสูจน์ผ่าน Beatty — คือวิธีที่ผลลัพธ์นี้ถูกค้นพบจริงๆ ในประวัติศาสตร์ และมันจำลองเครื่องยนต์สองจังหวะที่หนังสือเล่มนี้พบเจอซ้ำแล้วซ้ำเล่า: เครื่องจักรผลิตข้อมูล; การจดจำบีบอัดมัน; บทพิสูจน์รับรองมัน
ท่า — บดตารางก่อน แล้วค่อยคู่ควรกับสูตร. อุปนัยย้อนกลับให้ความจริงโดยไร้การปิ๊ง; การบีบอัดตารางให้เป็นรูปปิดคือการปิ๊ง — และจากนั้นมันต้องถูกพิสูจน์ ไม่ใช่จับแพตเทิร์นเอาเฉยๆ
เครื่องจักรกับท่านี้. การวิเคราะห์ถอยหลังคือสนามเหย้าของเครื่องจักร — ตารางจบเกมหมากรุก (endgame tablebase) ที่ทุกตำแหน่งซึ่งเหลือหมากเจ็ดตัวหรือน้อยกว่าถูกแก้ย้อนหลังจนหมด คืออนุสาวรีย์อุตสาหกรรมของมัน; จังหวะของมนุษย์คือการบีบตารางให้เหลือ φ ซึ่งไม่มี tablebase ตัวไหนจะอาสาบอกให้เด็ดขาด
ห้าท่า ในพริบตาเดียว
| ท่า | กลิ่น | ตราประจำท่า |
|---|---|---|
| เสริมแรงสมมุติฐาน | ขั้นอุปนัยเกือบจะทำงาน | เบาะ 2 − 1/n |
| บีบอัดประวัติศาสตร์เป็นสถานะ | นับ/หาค่าเหมาะที่สุดบนลำดับ; อดีตที่เกี่ยวข้องมีขนาดเล็ก | 12 ของ knapsack ชนะ 11 ของตะกละ |
| การพิสูจน์แบบสลับชิ้น | sort ตามกุญแจสักตัวฟังดูมีเค้า | 9534330 |
| ไบนารีเสิร์ชบนคำตอบ | ทำค่ามากสุดให้น้อยสุด | วัวที่ d = 3 |
| ป้ายจากตอนจบ | เป้าหมายแคบ จุดเริ่มพร่ามัว | φ ของ Wythoff |
ทั้งห้าคือนักสร้าง: แต่ละท่าคืนให้ไม่ใช่แค่คำตอบ แต่คือสิ่งก่อสร้างพร้อมใบรับประกัน เหลืออีกหนึ่งตระกูล — เครื่องมือที่เปลี่ยนว่าปัญหา*คือ*อะไร ก่อนที่ใครจะเริ่มลงมือแก้
บทถัดไป · 16 / 21สายตานักจำลองแบบ