9 กรกฎาคม 1918 — นิโคลาส เดอ บรอยน์: ลำดับวงกลมที่บรรจุทุกรหัสผ่านไว้ในตัวเอง
วันนี้ในประวัติศาสตร์คณิตศาสตร์ | 9 กรกฎาคม ค.ศ. 1918
บทนำ: ปัญหาของขโมยที่ฉลาด
สมมติว่าประตูห้องนิรภัยใช้รหัส 4 หลัก แต่ละหลักเป็นเลข 0–9 และประตูจะเปิดทันทีที่ 4 ตัวอักษรล่าสุดที่กด ตรงกับรหัส (ไม่มีปุ่ม Enter ไม่มีการล็อกหลังกดผิด)
ถ้าลองทุกรหัสแยกกัน ต้องกด $10{,}000 \times 4 = 40{,}000$ ครั้ง
แต่ถ้ากดอย่างชาญฉลาด — ให้รหัสถัดไป เหลื่อมทับ กับรหัสก่อนหน้า — จะต้องกดกี่ครั้ง?
คำตอบ: 10,003 ครั้ง และกุญแจของคำตอบนั้นชื่อว่า ลำดับเดอ บรอยน์ (de Bruijn sequence)
ผู้ตั้งชื่อนี้คือ นิโคลาส โกเวิร์ต เดอ บรอยน์ (Nicolaas Govert “Dick” de Bruijn, 1918–2012) นักคณิตศาสตร์ชาวดัตช์ที่เกิดในวันนี้ที่กรุงเฮก
1. นิยามและความมหัศจรรย์
นิยาม ลำดับเดอ บรอยน์อันดับ $n$ บนตัวอักษรขนาด $k$ เขียนแทนด้วย $B(k,n)$ คือลำดับวงกลม (cyclic sequence) ที่มีความยาว $k^n$ ซึ่งบล็อกย่อยความยาว $n$ ที่เป็นไปได้ทั้ง $k^n$ แบบ ปรากฏขึ้น แบบละครั้งพอดี
ตัวอย่าง $B(2,3)$:
$$ \mathbf{00010111} $$
อ่านเป็นวงกลม (ต่อหางกับหัว) แล้วเลื่อนหน้าต่างขนาด 3 ไปทีละตำแหน่ง:
| ตำแหน่ง | บล็อก |
|---|---|
| 1 | 000 |
| 2 | 001 |
| 3 | 010 |
| 4 | 101 |
| 5 | 011 |
| 6 | 111 |
| 7 | 110 (วนกลับ) |
| 8 | 100 (วนกลับ) |
ครบทั้ง 8 บล็อก ไม่ซ้ำเลยแม้แต่บล็อกเดียว — สวยงามอย่างน่าอัศจรรย์
จำนวนลำดับเดอ บรอยน์ที่แตกต่างกัน สำหรับ $B(k,n)$ คือ
$$ \frac{(k!)^{,k^{,n-1}}}{k^{,n}} $$
2. เคล็ดลับ: แปลงเป็นปัญหากราฟ
นี่คือส่วนที่งดงามที่สุด และเหมาะกับการสอนทฤษฎีกราฟมาก
สร้าง กราฟเดอ บรอยน์ $G$ ดังนี้
- จุดยอด (vertex): ทุกสตริงความยาว $n-1$ (มี $k^{n-1}$ จุด)
- เส้นเชื่อม (edge): จากจุด $a_1a_2\cdots a_{n-1}$ ไปยัง $a_2a_3\cdots a_{n-1}b$ สำหรับทุก $b$ ในตัวอักษร (มี $k^n$ เส้น)
สังเกตว่า แต่ละเส้นเชื่อมสอดคล้องกับบล็อกความยาว $n$ หนึ่งบล็อกพอดี
ดังนั้น ลำดับเดอ บรอยน์ = วงจรออยเลอร์ (Eulerian circuit) บนกราฟนี้
และเพราะทุกจุดยอดมี in-degree $= k$ และ out-degree $= k$ เท่ากัน อีกทั้งกราฟเชื่อมโยงกันแบบ strongly connected → ทฤษฎีบทออยเลอร์รับประกันว่าวงจรออยเลอร์มีอยู่จริงเสมอ $\blacksquare$
ปัญหาที่ดูเหมือนการนับที่ซับซ้อน กลายเป็นทฤษฎีบทที่ออยเลอร์พิสูจน์ไว้แล้วตั้งแต่ปี 1736 เพียงแค่เรามองมันในกราฟที่ถูกต้อง
หมายเหตุประวัติศาสตร์: เดอ บรอยน์เองเป็นคนแรกที่ยอมรับต่อสาธารณะ (ในรายงานเทคนิคปี 1975) ว่านักคณิตศาสตร์ชาวฝรั่งเศส C. Flye Sainte-Marie ได้นับลำดับเหล่านี้ไว้ตั้งแต่ ค.ศ. 1894 แล้ว — ความซื่อสัตย์ทางวิชาการที่น่าเคารพ
3. ที่ใช้จริงในโลกปัจจุบัน
- การเจาะรหัสประตู / การทดสอบระบบ: ดังตัวอย่างข้างต้น
- หุ่นยนต์ระบุตำแหน่ง: พิมพ์ลำดับเดอ บรอยน์ลงบนแถบ แล้วเซนเซอร์อ่านแค่ $n$ ตำแหน่งก็รู้ทันทีว่าอยู่ที่ไหนบนแถบ
- การประกอบจีโนม (genome assembly): อัลกอริทึม de Bruijn graph assembly เป็นวิธีมาตรฐานในการต่อชิ้นส่วน DNA สั้น ๆ ให้เป็นลำดับยาว
- การเขียนโปรแกรมระดับบิต: เทคนิค de Bruijn multiplication หาตำแหน่งบิต 1 ที่ต่ำที่สุดใน word ได้ในไม่กี่คำสั่ง (ใช้ในโปรแกรมหมากรุกคอมพิวเตอร์)
- มายากลไพ่: ผู้เล่นเปิดไพ่ 5 ใบติดกัน นักมายากลบอกได้ทันทีว่าเป็นใบใด
4. ชายผู้ทำงานข้ามศาสตร์อย่างไม่หยุดยั้ง
เดอ บรอยน์เกิดที่กรุงเฮก เข้าเรียนคณิตศาสตร์ที่ Leiden University ในปี 1936 แต่สงครามโลกครั้งที่สองทำให้การเรียนสะดุด เขาไปเป็นผู้ช่วยเต็มเวลาที่ Delft ตั้งแต่ปี 1939 (ซึ่งช่วยให้เขารอดพ้นจากการถูกเกณฑ์ไปใช้แรงงานในเยอรมนี) และได้ปริญญาเอกในปี 1943
ผลงานของเขากระจายไปทั่วคณิตศาสตร์อย่างน่าทึ่ง
| ปี | ผลงาน | สาขา |
|---|---|---|
| 1946 | ลำดับเดอ บรอยน์ | คณิตศาสตร์เชิงการจัด |
| 1948 | ทฤษฎีบทเดอ บรอยน์–แอร์ดิช | ทฤษฎีกราฟ / เรขาคณิตเชิงตกกระทบ |
| 1958 | หนังสือ Asymptotic Methods in Analysis | การวิเคราะห์ |
| 1967– | โครงการ AUTOMATH | ตรรกศาสตร์ / วิทยาการคอมพิวเตอร์ |
| 1972 | de Bruijn index | แคลคูลัสแลมบ์ดา |
| 1981 | การสร้างการปูกระเบื้องเพนโรสด้วย pentagrid | ควอไซคริสตัล |
AUTOMATH สมควรได้รับความสนใจเป็นพิเศษ ในปี 1967 ขณะอายุ 49 ปี เดอ บรอยน์ตัดสินใจเปลี่ยนทิศทางไปสร้าง ระบบตรวจสอบบทพิสูจน์ด้วยคอมพิวเตอร์เครื่องแรกของโลก เขาต้องการภาษาที่เขียนคณิตศาสตร์ทั้งเล่มลงไปได้แล้วให้เครื่องตรวจสอบความถูกต้องทุกบรรทัด
นั่นคือบรรพบุรุษโดยตรงของ Coq, Lean, Isabelle ที่นักคณิตศาสตร์ยุคนี้ใช้พิสูจน์ทฤษฎีบทระดับสี่สีและ Kepler conjecture
5. ทฤษฎีบทเดอ บรอยน์–แอร์ดิช (ฉบับเรขาคณิต)
ถ้ามีจุด $n$ จุดบนระนาบที่ ไม่ได้เรียงอยู่บนเส้นตรงเดียวกันทั้งหมด แล้วเส้นตรงที่ลากผ่านจุดเหล่านั้นอย่างน้อยสองจุด จะมีอย่างน้อย $n$ เส้น
บทพิสูจน์ใช้อุปนัยและหลักการคู่ควบ (duality) เป็นตัวอย่างชั้นเยี่ยมของ combinatorial geometry ที่นักเรียนมัธยมปลายเข้าใจได้
กิจกรรมชวนคิด
- สร้าง $B(2,4)$ ด้วยมือ (ความยาว 16) โดยวาดกราฟเดอ บรอยน์ที่มี 8 จุดยอดแล้วเดินหาวงจรออยเลอร์
- เขียนโปรแกรมสร้าง $B(10,4)$ แล้วยืนยันว่ามีความยาว 10,000 และเมื่อเติมอีก 3 ตัวที่หัวไปต่อท้าย จะเป็นสตริงเชิงเส้นยาว 10,003 ที่บรรจุทุกรหัส 4 หลัก
- พิสูจน์ว่ากราฟเดอ บรอยน์ $G(k, n)$ มีวงจรออยเลอร์เสมอ โดยตรวจสอบเงื่อนไข in-degree = out-degree
- ค้นคว้า: อัลกอริทึม de Bruijn graph ใช้ประกอบจีโนมอย่างไร? เหตุใดจึงเหมาะกับ short reads?
- ให้ $n = 3$ จุดบนระนาบที่ไม่เรียงเป็นเส้นตรง นับเส้นตรงที่ได้ แล้วตรวจสอบทฤษฎีบทเดอ บรอยน์–แอร์ดิช สำหรับ $n = 4, 5$
เอกสารอ้างอิง
- de Bruijn, N. G. (1946). A combinatorial problem. Koninklijke Nederlandse Akademie v. Wetenschappen, 49, 758–764.
- de Bruijn, N. G., & Erdős, P. (1948). On a combinatorial problem. Indagationes Mathematicae, 10, 421–423.
- de Bruijn, N. G. (1958). Asymptotic Methods in Analysis. North-Holland. (ต่อมาพิมพ์ซ้ำโดย Dover)
- de Bruijn, N. G. (1975). Acknowledgement of priority to C. Flye Sainte-Marie… Technical Report, TH Eindhoven.
- Nederpelt, R., Geuvers, H., & de Vrijer, R. (eds.) (1994). Selected Papers on Automath. North-Holland.
- O’Connor, J. J., & Robertson, E. F. Nicolaas de Bruijn. MacTutor History of Mathematics Archive.
ชุดบทความ “วันนี้ในประวัติศาสตร์คณิตศาสตร์” — เผยแพร่ 9 กรกฎาคม 2569
