นิม

thumb|ไม้ขีดไฟถูกตั้งไว้เล่นเกมนี้ ผู้เล่นจะนำไม้ขีดออกเท่าใดก็ได้
**นิม** () คือ เกมวางแผนทางคณิตศาสตร์เกมหนึ่ง ซึ่งมีผู้เล่น 2 คน และมีกติกาในการเล่นดังนี้

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

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

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

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

ตัวอย่างการเล่นนิมด้วยกติกาปกติ สมมติว่าเริ่มต้นด้วยกองหิน 3 กอง แต่ละกองมีก้อนหินอยู่ 3, 4, 5 ก้อน ตามลำดับ
 จำนวนก้อนหินในกอง     การหยิบ
 A B C
 &nbsp;
 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*&nbsp;⊕&nbsp;*y* ซึ่งต่างจากผลบวกธรรมดาที่เขียนแทนด้วย *x*&nbsp;+&nbsp;*y* ตัวอย่างการคำนวณของกองหินที่มีก้อนหินอยู่ 3, 4, 5 ก้อน มีดังนี้

 เลขฐานสอง  เลขฐานสิบ
 &nbsp;
     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&nbsp;=&nbsp;3&nbsp;⊕&nbsp;4&nbsp;⊕&nbsp;5&nbsp;=&nbsp;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 ผลบวกนิม
 &nbsp;
 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*&nbsp;=&nbsp;0 ด้วย

ให้ *x*1,&nbsp;...,&nbsp;*x<sub>n</sub>* คือ จำนวนก้อนหินในแต่ละกองก่อนการหยิบ และ *y*1,&nbsp;...,&nbsp;*y<sub>n</sub>* คือ จำนวนก้อนหินในแต่ละกองหลังการหยิบ ให้ *s*&nbsp;=&nbsp;*x*1&nbsp;⊕&nbsp;...&nbsp;⊕&nbsp;*x<sub>n</sub>* และ *t*&nbsp;=&nbsp;*y*1&nbsp;⊕&nbsp;...&nbsp;⊕&nbsp;*y<sub>n</sub>*. ถ้าเราหยิบกองที่ *k*, เราจะได้ *x<sub>i</sub>*&nbsp;=&nbsp;*y<sub>i</sub>* สำหรับ *i*&nbsp;≠&nbsp;*k*, และ *x<sub>k</sub>*&nbsp;&gt;&nbsp;*y<sub>k</sub>*. จากสมบัติของ ⊕ เราจะได้

     *t* = 0 ⊕ *t*
       = *s* ⊕ *s* ⊕ *t*
       = *s* ⊕ (*x*1 ⊕ ... ⊕ *x<sub>n</sub>*) ⊕ (*y*1 ⊕ ... ⊕ *y<sub>n</sub>*)
       = *s* ⊕ (*x*1 ⊕ *y*1) ⊕ ... ⊕ (*x<sub>n</sub>* ⊕ *y<sub>n</sub>*)
       = *s* ⊕ 0 ⊕ ... ⊕ 0 ⊕ (*x<sub>k</sub>* ⊕ *y<sub>k</sub>*) ⊕ 0 ⊕ ... ⊕ 0
       = *s* ⊕ *x<sub>k</sub>* ⊕ *y<sub>k</sub>*
 &nbsp;
 (*) *t* = *s* ⊕ *x<sub>k</sub>* ⊕ *y<sub>k</sub>*

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

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

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

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

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

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

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

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

* The hot game of Nim  
* เล่นนิมออนไลน์

หมวดหมู่:เกมคณิตศาสตร์
หมวดหมู่:ทฤษฎีเกมเชิงการจัด
หมวดหมู่:คณิตศาสตร์นันทนาการ