นิม

นิม (อังกฤษ: Nim) คือ เกมวางแผนทางคณิตศาสตร์เกมหนึ่ง ซึ่งมีผู้เล่น 2 คน และมีกติกาในการเล่นดังนี้

1. มีกองหินอยู่หลายกอง แต่ละกองมีก้อนหินอยู่
2. ผู้เล่นจะผลัดกันหยิบก้อนหิน
3. ในการหยิบแต่ละครั้ง ผู้เล่นจะต้องหยิบก้อนหินออกจากกองหินกองใดกองหนึ่ง และต้องหยิบอย่างน้อย 1 ก้อน
4. ผู้เล่นที่หยิบก้อนหิน ก้อนหินก้อนสุดท้าย จะเป็นผู้ชนะ (ผู้ที่หยิบหินก่อนสุดท้ายจะเป็นผู้แพ้)

ไม้ขีดไฟถูกตั้งไว้เล่นเกมนี้ ผู้เล่นจะนำไม้ขีดออกเท่าใดก็ได้

มีการเล่นนิมมาตั้งแต่สมัยโบราณแล้ว บางคนกล่าวว่านิมมีต้นกำเนิดจากจีน แต่ความจริงแล้ว ยังไม่มีใครรู้ได้ จากหลักฐานของชาวยุโรป พบว่า นิมมีมาตั้งแต่คริสต์ศตวรรษที่ 16 Charles L. Bouton แห่งมหาวิทยาลัยฮาร์วาร์ดเป็นผู้ตั้งชื่อเกมนี้ว่า นิม และได้พัฒนาทฤษฎีเกี่ยวกับเกมนี้ตั้งแต่ปี ค.ศ. 1901 แต่ชื่อเดิมของเกมนี้ยังไม่มีใครรู้ บางทีมันอาจมาจากภาษาเยอรมันคำว่า nimm! ซึ่งแปลว่า take! หรืออาจจะมาจากภาษาอังกฤษเก่า ซึ่งก็แปลว่า take เหมือนกัน มีการตั้งข้อสังเกตว่าเมื่อเราหมุนคำว่า NIM เราจะได้คำว่า WIN ซึ่งอาจเป็นเพียงความบังเอิญ

นอกจากนี้ ยังมีผู้นิยมเล่นเกมนิมในแบบตรงกันข้ามคือ ผู้เล่นที่หยิบก้อนหินก้อนสุดท้าย จะเป็นผู้แพ้ แต่โดยทั่วไป เรานิยมเล่นโดยใช้กติกาแบบแรกมากกว่า

ตัวอย่างการเล่น

ตัวอย่างการเล่นนิมด้วยกติกาปกติ สมมติว่าเริ่มต้นด้วยกองหิน 3 กอง แต่ละกองมีก้อนหินอยู่ 3, 4, 5 ก้อน ตามลำดับ

จำนวนก้อนหินในกอง การหยิบ A B C   3 4 5  เราหยิบก้อนหิน 2 ก้อน ออกจาก A 1 4 5  คุณหยิบก้อนหิน 3 ก้อน ออกจาก C 1 4 2  เราหยิบก้อนหิน 1 ก้อน ออกจาก B 1 3 2  คุณหยิบก้อนหิน 1 ก้อน ออกจาก B 1 2 2  เราหยิบก้อนหิน ออกจาก A 0 2 2  คุณหยิบก้อนหิน 1 ก้อน ออกจาก B 0 1 2  เราหยิบก้อนหิน 1 ก้อน ออกจาก C (แต่ถ้าใช้กติกาแบบที่สอง เราจะหยิบก้อนหิน 2 ก้อนออกจาก C ทำให้เหลือ (0, 1, 0)  ) 0 1 1  คุณหยิบก้อนหิน 1 ก้อน ออกจาก B 0 0 1  เราหยิบก้อนหิน ออกจาก C ดังนั้น เราจึงเป็นผู้ชนะ 

ทฤษฎีทางคณิตศาสตร์

นิมเป็นเกมที่แก้ด้วยคณิตศาสตร์ได้ และสามารถคำนวณได้ง่ายว่าผู้เล่นคนใดจะชนะ,ต้องหยิบอย่างไรถึงจะชนะ ตัวอย่างเช่น เกมที่เริ่มต้นด้วยกองหินที่มีก้อนหินอยู่ 3, 4, 5 ก้อน ผู้เล่นที่เล่นคนแรกจะชนะเสมอ ถ้าเขาเล่นด้วยกลยุทธ์ที่ถูกต้อง และไม่ขึ้นกับว่ากติกาจะเป็นแบบปกติหรือแบบที่สองก็ตาม

หัวใจของทฤษฎีของเกมนี้ก็คือ ผลบวกเลขโดดฐานสอง (binary digital sum) ซึ่งเป็นผลบวกในเลขฐานสองที่ไม่มีการทด การดำเนินการนี้เรียกว่าการ exclusive or (xor) ในทฤษฎีเกมเชิงการจัดจะเรียกว่า ผลบวกนิม (nim-sum) ผลบวกนิมของ x และ y เขียนแทนด้วย x ⊕ y ซึ่งต่างจากผลบวกธรรมดาที่เขียนแทนด้วย x + y ตัวอย่างการคำนวณของกองหินที่มีก้อนหินอยู่ 3, 4, 5 ก้อน มีดังนี้

เลขฐานสอง เลขฐานสิบ   0112 310 กอง A 1002 410 กอง B 1012 510 กอง C --- 0102 210 ดังนั้น ผลบวกนิมของกอง A, B, C เท่ากับ 3 ⊕ 4 ⊕ 5 = 2 

หรือจะคำนวณแบบนี้ก็ได้ ให้เขียนจำนวนก้อนหินในแต่ละกองให้อยู่ในรูปผลบวกของเลขกำลังสอง จากนั้นให้ตัดคู่ที่เท่ากันออกไป ถ้าตัดไม่ได้แล้ว ให้บวกเลขที่เหลือเข้าด้วยกัน ก็จะได้ผลลัพธ์ เช่น

3 = 2 + 1 = 2 + 1 กอง A 4 = 4 = 4 กอง B 5 = 4 + 1 = 4 + 1 กอง C --- 2 = 2 ผลลัพธ์ที่ได้จากการตัดคู่เลข 1 กับ คู่เลข 4 

กลยุทธ์ในการเล่นให้ชนะคือ ทำผลบวกนิมให้เท่ากับ 0 เสมอ. ซึ่งถ้าผลบวกนิมก่อนที่คุณจะหยิบไม่เท่ากับ 0 แล้ว จะมีวิธีที่ทำให้ผลบวกนิมเท่ากับ 0 ได้เสมอ. ถ้าคุณไม่เล่นพลาดเลยสักตา ผู้เล่นอีกฝ่ายจะเป็นฝ่ายแพ้. เพื่อหาว่าจะต้องหยิบก้อนหินจากกองใดจำนวนเท่าไร เราจะให้ X คือผลบวกนิมของจำนวนก้อนหินทุกกอง ให้หาผลบวกนิมของจำนวนก้อนหินในแต่ละกอง กับ X. กลยุทธ์คือ คุณจะต้องทำให้จำนวนก้อนหินในกองใดกองหนึ่ง เหลือเท่ากับผลบวกนิมของจำนวนหินเดิมในกองนั้นกับ X. จากตัวอย่างข้างบน ผลบวกนิมของทุกกองเท่ากับ X = 3 ⊕ 4 ⊕ 5 = 2 ผลบวกนิมของจำนวนก้อนหินในกอง A=3, B=4, C=5 กับ X เท่ากับ

A ⊕ X = 3 ⊕ 2 = 1

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

มีเพียงกองเดียวที่สามารถลดจำนวนก้อนหินให้เท่ากับค่าที่ต้องการได้ คือ กอง A (เราสามารถลดก้อนหินในกอง A จาก 3 ก้อนเป็น 1 ก้อนได้ แต่ไม่สามารถลดกอง B จาก 4 ก้อนเป็น 6 ก้อนได้ และไม่สามารถลดกอง C จาก 5 ก้อนเป็น 7 ก้อนได้) ดังนั้น การเล่นที่ถูกคือต้องลดจำนวนก้อนหินในกอง A ให้เท่ากับ 1 (หยิบหินออกจากกอง A ออกไป 2 ก้อน)

ในกรณีที่มีกองหินอยู่ 2 กอง จะมีกลยุทธ์ที่ง่ายกว่าคือ ให้ลดก้อนหินของกองที่ใหญ่กว่า ให้เท่ากับอีกกองหนึ่ง หลังจากนั้น ไม่ว่าผู้เล่นอีกฝ่ายจะหยิบจำนวนก้อนหินเท่าใด คุณก็หยิบก้อนหินจำนวนเท่ากันจากอีกกอง วิธีนี้จะรับประกันว่าคุณจะเป็นผู้หยิบก้อนหินก้อนสุดท้ายเสมอ

ถ้าเล่นกติกาแบบที่สอง กลยุทธ์ในการเล่นยังคงเหมือนกัน ยกเว้น ในกรณีที่การหยิบจะทำให้กองหินทุกกองมีก้อนหินน้อยกว่า 2 ก้อน ในกรณีนี้ การหยิบที่ถูกต้องคือหยิบให้เหลือจำนวนกองที่มีก้อนหิน 1 ก้อน อยู่เป็นจำนวนคี่ (ซึ่งถ้าเล่นกติกาปกติ การหยิบที่ถูกต้องคือหยิบให้เหลือจำนวนกองที่มีก้อนหิน 1 ก้อน อยู่เป็นจำนวนคู่)

ในการเล่นกติกาแบบที่สอง ซึ่งเริ่มต้นด้วยกองหินที่มีก้อนหินอยู่ 3, 4, 5 ก้อน จะมีกลยุทธ์ในการเล่นเป็นดังนี้

A B C ผลบวกนิม   3 4 5 0102=210 เราหยิบก้อนหิน 2 ก้อน ออกจาก A ทำให้ผลบวกนิมเท่ากับ 000 ดังนั้น เราจะชนะ 1 4 5 0002=010 คุณหยิบก้อนหิน 2 ก้อน ออกจาก C 1 4 3 1102=610 เราหยิบก้อนหิน 2 ก้อน ออกจาก B 1 2 3 0002=010 คุณหยิบก้อนหิน 1 ก้อน ออกจาก C 1 2 2 0012=110 เราหยิบก้อนหิน 1 ก้อน ออกจาก A 0 2 2 0002=010 คุณหยิบก้อนหิน 1 ก้อน ออกจาก C 0 2 1 0112=310 ในการเล่นแบบปกติ เราจะหยิบก้อนหิน 1 ก้อนออกจากกอง B  ทำให้เหลือกองที่มีหิน 1 ก้อน อยู่เป็นจำนวนคู่    ในการเล่นแบบกติกาที่สอง เราจะหยิบก้อนหินทั้งหมดออกจากกอง B  ทำให้เหลือกองที่มีหิน 1 ก้อน อยู่เป็นจำนวนคี่ 0 0 1 0012=110 คุณหยิบก้อนหิน 1 ก้อน ออกจาก C ดังนั้น คุณจึงแพ้ 

การพิสูจน์

C. Bouton เป็นผู้อธิบายกลยุทธ์ในการเล่นให้ชนะเสมอ และให้บทพิสูจน์ดังนี้

ทฤษฎีบท. ในเกมนิมแบบปกติ ผู้เล่นคนแรกจะมีกลยุทธ์ในการเล่นให้ชนะเสมอ ก็ต่อเมื่อ ผลบวกนิมของจำนวนก้อนหินทุกกองไม่เท่ากับ 0. มิฉะนั้นแล้ว ผู้เล่นคนที่สองจะมีกลยุทธ์ในการเล่นให้ชนะเสมอ

พิสูจน์: ผลบวกนิม (⊕) มีสมบัติการเปลี่ยนหมู่ และการสลับที่ และยังมีสมบัติ x = 0 ด้วย

ให้ x₁, ..., x_n คือ จำนวนก้อนหินในแต่ละกองก่อนการหยิบ และ y₁, ..., y_n คือ จำนวนก้อนหินในแต่ละกองหลังการหยิบ ให้ s = x₁ ⊕ ... ⊕ x_n และ t = y₁ ⊕ ... ⊕ y_n. ถ้าเราหยิบกองที่ k, เราจะได้ x_i = y_i สำหรับ i ≠ k, และ x_k > y_k. จากสมบัติของ ⊕ เราจะได้

 t = 0 ⊕ t = s ⊕ s ⊕ t = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn) = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn) = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0 = s ⊕ xk ⊕ yk   (*) t = s ⊕ xk ⊕ yk 

เราจะพิสูจน์ทฤษฎีบทนี้ ด้วยการอุปนัยจากบทตั้งทั้ง 2 ข้อต่อไปนี้

บทตั้งที่ 1. ถ้า s = 0 แล้ว t ≠ 0 เสมอ ไม่ขึ้นอยู่กับว่าจะหยิบแบบใด

พิสูจน์: ถ้าไม่มีก้อนหินเหลืออยู่ บทตั้งนี้จะถือว่าเป็นจริง (และผู้เล่นคนแรกก็จะเป็นผู้แพ้ตามนิยามของเกม) แต่ถ้ามีก้อนหินเหลืออยู่ การหยิบก้อนหินออกจากกองที่ k จะทำให้ t = x_k ⊕ y_k จาก (*) ซึ่งค่านี้จะไม่เท่ากับศูนย์เพราะ x_k ≠ y_k

บทตั้งที่ 2. ถ้า s ≠ 0 แล้ว จะมีวิธีหยิบที่ทำให้ t = 0 เสมอ

พิสูจน์: ให้ d เป็นบิตที่ไม่เป็นศูนย์ที่อยู่ซ้ายสุดของ s, เลือก k ที่ x_k บิตที่ d ไม่เป็นศูนย์ (ต้องมี k อยู่ มิฉะนั้นแล้ว s บิตที่ d จะเป็น 0) ให้ y_k = s ⊕ x_k เรารับประกันได้ว่า y_k < x_k เพราะว่า x_k กับ y_k จะมีบิตที่อยู่ทางซ้ายบิตที่ d เหมือนกัน แต่ y_k บิตที่ d จะเปลี่ยนจาก 1 เป็น 0 (ค่าลดไป 2^k) และ การเปลี่ยนแปลงในบิตที่เหลือ จะมีค่าไม่เกิน 2^k−1 ดังนั้น ผู้เล่นคนแรกจึงสามารถหยิบก้อนหิน x_k − y_k ก้อน ออกจากกองที่ k ได้ จะได้

t = s ⊕ xk ⊕ yk  (จาก (*)) = s ⊕ xk ⊕ (s ⊕ xk) = 0 

การเล่นแบบอื่น ๆ

มีการเล่นนิมในอีกลักษณะหนึ่งคือ แทนที่จะหยิบก้อนหินจำนวนเท่าใดก็ได้ ให้เปลี่ยนเป็นหยิบก้อนหินได้จำกัด นั่นคือ ผู้เล่นจะหยิบก้อนหินออกได้ 1 หรือ 2 หรือ ... หรือ k ก้อนต่อการหยิบหนึ่งครั้งเท่านั้น (ซึ่งควรเรียกว่า เกมการลบ S (1,2,...,k) มากกว่า) โดยทั่วไป เกมนี้จะเล่นแค่กองหินกองเดียว

กลยุทธ์ในการเล่นจะไม่แตกต่างจากการเล่นแบบเดิม ยกเว้น ก่อนที่เราจะหาค่าผลบวกนิม เราจะต้องลดขนาดของกองหิน ด้วยการมอดุโลกับ k + 1 ก่อน. ถ้าทุกกองมอดุโลแล้วได้ 0 (สำหรับกติกาแบบที่สอง) ให้หยิบก้อนหิน k ก้อน ออกจากกองใดกองหนึ่งก็ได้ ถ้าเล่นจนเหลือกองเดียวและมีก้อนหินเหลือ n ก้อน ผู้เล่นคนที่สองจะชนะได้ ก็ต่อเมื่อ

n ≡ 0  (mod k+1) (สำหรับกติกาแบบปกติ) , หรือ

n ≡ 1  (mod k+1) (สำหรับกติกาแบบที่สอง)

แหล่งข้อมูลอื่น

• The hot game of Nim 2008-08-20 ที่ เวย์แบ็กแมชชีน
• เล่นนิมออนไลน์