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

เกม Fibonacci nim เล่นโดยผู้เล่นสองคน โดยผลัดกันหยิบเหรียญหรือตัวนับอื่นๆ ออกจากกอง ในการเล่นครั้งแรก ผู้เล่นไม่ได้รับอนุญาตให้หยิบเหรียญทั้งหมด และในการเล่นครั้งต่อๆ ไป จำนวนเหรียญที่หยิบออกสามารถเป็นจำนวนใดก็ได้ที่ไม่เกินสองเท่าของจำนวนเหรียญที่หยิบได้ในการเล่นครั้งก่อน ตามธรรมเนียมการเล่นปกติผู้เล่นที่หยิบเหรียญสุดท้ายได้จะเป็นผู้ชนะ^{[ 1 ]}

เกมนี้ได้รับการอธิบายครั้งแรกโดย Michael J. Whinihan ในปี 1963 โดยให้เครดิตการคิดค้นแก่ Robert E. Gaskell นักคณิตศาสตร์จาก มหาวิทยาลัย Oregon State Universityเกมนี้เรียกว่า Fibonacci nim เพราะตัวเลขฟิโบนาชชีมีบทบาทสำคัญในการวิเคราะห์^{[ 2 ]}

เกมนี้ควรแยกออกจากเกมอื่นที่เรียกว่า Fibonacci nim ซึ่งผู้เล่นสามารถนำเหรียญจำนวน Fibonacci ออกได้ในแต่ละตา^{[ 3 ]}

กลยุทธ์สำหรับการเล่นที่ดีที่สุดในเกม Fibonacci nim เกี่ยวข้องกับการคิดว่าจำนวนเหรียญปัจจุบันเป็นผลรวมของตัวเลขฟิโบนาชชี [ ^{2 ] มี}หลายวิธีในการแสดงตัวเลขเป็นผลรวมของตัวเลขฟิโบนาชชี แต่มีเพียงการแสดงเพียงวิธีเดียวที่ใช้ตัวเลขฟิโบนาชชีแต่ละตัวไม่เกินหนึ่งครั้ง และหลีกเลี่ยงคู่ตัวเลขฟิโบนาชชีที่ติดกัน การแสดงที่ไม่ซ้ำกันนี้เรียกว่าการแสดงแบบ Zeckendorfตัวอย่างเช่น การแสดงแบบ Zeckendorf ของ 10 คือ 8 + 2 แม้ว่า 10 จะสามารถแสดงเป็นผลรวมของตัวเลขฟิโบนาชชีได้ด้วยวิธีอื่น เช่น 5 + 5 หรือ 5 + 3 + 2 แต่วิธีเหล่านั้นไม่ตรงตามเงื่อนไขของการใช้ตัวเลขฟิโบนาชชีแต่ละตัวเพียงครั้งเดียวและหลีกเลี่ยงคู่ตัวเลขฟิโบนาชชีที่ติดกัน เช่น คู่ 2, 3 และ 3, 5 การแสดงแบบ Zeckendorf ของตัวเลขใด ๆ สามารถหาได้โดยอัลกอริทึมแบบโลภที่ลบตัวเลขฟิโบนาชชีที่ใหญ่ที่สุดที่เป็นไปได้ซ้ำ ๆ จนกว่าจะถึงศูนย์^{[ 4 ]}

กลยุทธ์ของเกมยังเกี่ยวข้องกับตัวเลขที่เรียกว่า "โควต้า" ซึ่งอาจแสดงด้วยqนี่คือจำนวนเหรียญสูงสุดที่สามารถนำออกได้ในขณะนี้ ในการเคลื่อนไหวครั้งแรก สามารถนำเหรียญออกได้ทั้งหมด ยกเว้นหนึ่งเหรียญ ดังนั้นหากจำนวนเหรียญคือnโควต้าคือq = n − 1ในการเคลื่อนไหวครั้งต่อๆ ไป โควต้าจะเป็นสองเท่าของการเคลื่อนไหวครั้งก่อน^{[ 2 ]}

จากคำจำกัดความเหล่านี้ ผู้เล่นที่กำลังจะเดินหมากสามารถชนะได้เมื่อใดก็ตามที่qมากกว่าหรือเท่ากับจำนวนฟิโบนาชชีที่เล็กที่สุดในการแสดงผลแบบ Zeckendorf และจะแพ้ (หากคู่ต่อสู้เล่นได้ดีที่สุด) ในกรณีอื่น ๆ ในตำแหน่งที่ชนะ การนำเหรียญทั้งหมดออก (หากอนุญาต) หรือการนำเหรียญออกจำนวนเท่ากับจำนวนฟิโบนาชชีที่เล็กที่สุดในการแสดงผลแบบ Zeckendorf ถือเป็นการเดินหมากที่ชนะเสมอ เมื่อเป็นไปได้ ผู้เล่นฝ่ายตรงข้ามจะตกอยู่ในตำแหน่งที่แพ้ เนื่องจากโควต้าใหม่จะน้อยกว่าจำนวนฟิโบนาชชีที่เล็กที่สุดในการแสดงผลแบบ Zeckendorf ของจำนวนเหรียญที่เหลืออยู่^{[ 2 ]}อาจมีการเดินหมากที่ชนะอื่น ๆ ได้เช่นกัน^{[ 5 ]}อย่างไรก็ตาม จากตำแหน่งที่แพ้ การเดินหมากทั้งหมดจะนำไปสู่ตำแหน่งที่ชนะ^{[ 2 ]}

การแสดงผลแบบ Zeckendorf ของจำนวนฟิโบนาชชีประกอบด้วยจำนวนนั้นเพียงจำนวนเดียว ดังนั้นเมื่อกองเหรียญเริ่มต้นมีจำนวนฟิโบนาชชีnจำนวนฟิโบนาชชีที่เล็กที่สุดในการแสดงผลแบบ Zeckendorf ก็คือnซึ่งมากกว่าโควต้าเริ่มต้นn − 1ดังนั้น จำนวนฟิโบนาชชีเป็นกองเหรียญเริ่มต้นจึงทำให้ผู้เล่นคนแรกแพ้และผู้เล่นคนที่สองชนะ อย่างไรก็ตาม จำนวนเหรียญเริ่มต้นที่ไม่ใช่จำนวนฟิโบนาชชีจะมีจำนวนฟิโบนาชชีที่เล็กกว่าในการแสดงผลแบบ Zeckendorf จำนวนเหล่านี้ไม่มากกว่าโควต้าเริ่มต้น ดังนั้นเมื่อใดก็ตามที่จำนวนเหรียญเริ่มต้นไม่ใช่จำนวนฟิโบนาชชี ผู้เล่นคนแรกจึงสามารถชนะได้เสมอ^{[ 1 ]}

ตัวอย่างเช่น สมมติว่าตอนแรกมีเหรียญอยู่ 10 เหรียญ^{[ 6 ]}

• การแทนเลข 10 ด้วยวิธี Zeckendorf คือ 10 = 8 + 2 และจำนวนเหรียญเริ่มต้นคือ 9 ซึ่งมากกว่าเลขฟิโบนาชชีที่เล็กที่สุดคือ 2 ในการแทนเลขด้วยวิธี Zeckendorf ดังนั้นผู้เล่นคนแรกจึงมีโอกาสชนะ การเดินหมากที่ทำให้ผู้เล่นคนแรกชนะคือการนำเลขฟิโบนาชชีที่เล็กที่สุดในวิธีแสดงเลขนี้ออกไป คือ 2 เหลือเหรียญไว้ 8 เหรียญ
• หลังจากเดินหมากครั้งนี้ จะเหลือเหรียญ 8 เหรียญ โดยในระบบ Zeckendorf แสดงค่าเป็น 8 และโควต้าใหม่คือ 4 หมายความว่าผู้เล่นคนที่สองสามารถนำเหรียญออกได้มากที่สุด 4 เหรียญ ซึ่งไม่เพียงพอที่จะถึงจำนวนที่น้อยที่สุดในระบบ Zeckendorf การนำเหรียญออก 3 หรือ 4 เหรียญจะทำให้ผู้เล่นคนแรกชนะทันที สมมติว่าผู้เล่นคนที่สองนำเหรียญออก 2 เหรียญ
• เหลือเหรียญ 6 = 5 + 1 เหรียญ โดยมีโควต้า 4 ซึ่งมากกว่า 1 ในการแสดงผลแบบ Zeckendorf ผู้เล่นคนแรกสามารถเลือกเลขฟิโบนาชชีที่เล็กที่สุดในการแสดงผลนี้ได้อีกครั้ง คือ 1 ทำให้เหลือเหรียญ 5 เหรียญ
• เมื่อมีเหรียญอยู่ 5 เหรียญ การแสดงผลแบบ Zeckendorf คือ 5 แต่โควต้าคือ 2 ซึ่งเป็นจำนวนที่น้อยกว่า ผู้เล่นคนที่สองสามารถหยิบเหรียญได้สองเหรียญ แต่ก็จะแพ้ทันที ดังนั้นสมมติว่าผู้เล่นคนที่สองหยิบเพียงเหรียญเดียว
• หลังจากเดินหมากนี้ จำนวนเหรียญจะเหลือ 4 = 3 + 1 และโควต้าคือ 2 ผู้เล่นคนแรกจะหยิบเลขฟิโบนาชชีที่เล็กที่สุดในรูปแบบเซ็กเคนดอร์ฟอีกครั้ง ซึ่งก็คือ 1 ทำให้เหลือเหรียญ 3 เหรียญ
• ไม่ว่าผู้เล่นคนที่สองจะหยิบเหรียญหนึ่งหรือสองเหรียญ ผู้เล่นคนแรกก็จะชนะเกมในตาต่อไปอยู่ดี

ฟิโบนาชชีนิมเป็นเกมที่เป็นกลางเนื่องจากการเคลื่อนไหวที่สามารถทำได้จากตำแหน่งใดๆ ก็ตามไม่ขึ้นอยู่กับตัวตนของผู้เล่นที่กำลังจะเคลื่อนไหว ดังนั้นทฤษฎีบทสปราก-กรุนดีจึงสามารถใช้ในการวิเคราะห์ส่วนขยายของเกมที่มีกองเหรียญหลายกอง และการเคลื่อนไหวแต่ละครั้งจะนำเหรียญออกจากกองเดียวเท่านั้น (อย่างมากที่สุดสองเท่าของการเคลื่อนไหวครั้งก่อนจากกองเดียวกัน) สำหรับส่วนขยายนี้ จำเป็นต้องคำนวณค่านิมของแต่ละกอง ค่าของเกมหลายกองคือผลรวมนิมของค่านิมเหล่านี้ อย่างไรก็ตาม คำอธิบายที่สมบูรณ์ของค่าเหล่านี้ยังไม่เป็นที่รู้จัก^{[ 7 ]}

รูปแบบเกมแบบกองหลายกองที่แตกต่างกันซึ่งได้รับการศึกษาเช่นกันนั้นจำกัดจำนวนหินในแต่ละตาเดินให้เป็นสองเท่าของจำนวนหินในตาเดินก่อนหน้า โดยไม่คำนึงว่าตาเดินก่อนหน้านั้นจะอยู่ในกองเดียวกันหรือไม่^{[ 8 ]}