لعبة غروندي

لعبة غروندي هي لعبة استراتيجية رياضية ثنائية اللاعبين. تبدأ اللعبة بمجموعة واحدة من الأشياء، ويتناوب اللاعبان على تقسيمها إلى مجموعتين مختلفتي الحجم. تنتهي اللعبة عندما لا يتبقى سوى مجموعتين أو أقل، ولا يمكن تقسيم أي منهما بشكل غير متساوٍ. تُلعَب اللعبة عادةً كلعبة عادية ، أي أن آخر لاعب يقوم بحركة مسموحة يفوز.

في لعبة اللعب العادية التي تبدأ بمجموعة واحدة من 8 قطع، يفوز اللاعب الأول بشرط أن يبدأ بتقسيم المجموعة إلى مجموعتين من 7 و 1:

اللاعب 1: 8 → 7+1

أمام اللاعب الثاني الآن ثلاثة خيارات: تقسيم الكومة المكونة من 7 قطع إلى 6 + 1، أو 5 + 2، أو 4 + 3. في كل حالة من هذه الحالات، يمكن للاعب الأول أن يضمن أنه في النقلة التالية يعيد إلى خصمه كومة بحجم 4 بالإضافة إلى أكوام بحجم 2 وأصغر:

اللاعب 2: 7+1 → 6+1+1 اللاعب 2: 7+1 → 5+2+1 اللاعب 2: 7+1 → 4+3+1 اللاعب 1: 6+1+1 → 4+2+1+1 اللاعب 1: 5+2+1 → 4+1+2+1 اللاعب 1: 4+3+1 → 4+2+1+1

الآن يتعين على اللاعب الثاني تقسيم الكومة المكونة من 4 قطع إلى 3 + 1، ثم يقوم اللاعب الأول بتقسيم الكومة المكونة من 3 قطع إلى 2 + 1:

اللاعب الثاني: 4+2+1+1 → 3+1+2+1+1 اللاعب 1: 3+1+2+1+1 → 2+1+1+2+1+1 لم يتبق لدى اللاعب الثاني أي حركات، فخسر.

يمكن تحليل اللعبة باستخدام نظرية سبراغ-غروندي . يتطلب ذلك ربط أحجام الكومة في اللعبة بأحجام الكومة المكافئة في لعبة نيم . هذا الربط مُسجّل في الموسوعة الإلكترونية لتسلسلات الأعداد الصحيحة تحت الرمز OEIS : A002188  :

حجم الذاكرة المخصصة: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... كومة نيم المكافئة: 0 0 0 1 0 2 1 0 2 1 0 2 1 3 2 1 3 2 4 3 0 ...

باستخدام هذا الربط، يمكن تطبيق استراتيجية لعبة نيم على لعبة غروندي. يبقى السؤال مطروحًا حول ما إذا كانت سلسلة قيم نيم في لعبة غروندي ستصبح دورية أم لا. وقد افترض كل من إلوين بيرلكامب ، وجون هورتون كونواي، وريتشارد غاي ^{[ 1 ]} أن السلسلة ستصبح دورية في نهاية المطاف، ولكن على الرغم من حساب أول 235 ^قيمة بواسطة أخيم فلامنكامب ، إلا أن المسألة لم تُحسم بعد.

• نيم
• نظرية سبريج-جروندي
• لعبة ويثوف
• اطرح مربعًا

• لعبة غروندي على موقع ماث وورلد
• قيم سبراغ-غراندي للعبة غراندي من تأليف أ. فلامنكامب