2025-11-19T22:58:13.964427

A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence

Komak, Miyadera, Murakami
In this paper, we study a variant of the classical Wythoff's game. The classical form is played with two piles of stones, from which two players take turns to remove stones from one or both piles. When removing stones from both piles, an equal number must be removed from each. The player who removes the last stone or stones is the winner. Equivalently, we consider a single chess queen placed somewhere on a large grid of squares. Each player can move the queen toward the upper-left corner of the grid, either vertically, horizontally, or diagonally, in any number of steps. The winner is the player who moves the queen into the upper-left corner, the position (0,0) in our coordinate system. We call (0,0) the terminal position of Wythoff's game. In our variant of Wythoff's game, we have a set of positions {(0,0),(1,0),(0,1),(1,1),(2,0),(0,2)} as the terminal set. If a player moves the queen into this terminal set, that player is the winner of the game. The P-positions of this variant are described by the P-positions of Wythoff's game and Hofstadter's G-Sequence. This variant has two remarkable properties. For a position (x,y) with x >= 8 or y >= 8, the Grundy number of the position (x,y) is 1 in this variant if and only if (x,y) is a P-position of Wythoff's game. There is another remarkable property.For a position (x,y) with x >= 8 or y >= 8, (x,y) is a P-position of of the misere version of this variant if and only if (x,y) is a P-position of of Wythoff's game.
academic

متغير من لعبة Wythoff المعرّف بواسطة متتالية Hofstadter's G

المعلومات الأساسية

  • معرّف الورقة: 2510.11767
  • العنوان: متغير من لعبة Wythoff المعرّف بواسطة متتالية Hofstadter's G
  • المؤلفون: Kahori Komaki, Ryohei Miyadera, Aoi Murakami
  • التصنيف: math.CO (الرياضيات التوافقية)
  • تاريخ النشر: 13 أكتوبر 2025 (نسخة arXiv المسبقة)
  • رابط الورقة: https://arxiv.org/abs/2510.11767

الملخص

تدرس هذه الورقة متغيراً من لعبة Wythoff الكلاسيكية. تتضمن لعبة Wythoff الكلاسيكية كومتين من الحصى، حيث يتناوب اللاعبان على إزالة الحصى من كومة واحدة أو كومتين، وعند الإزالة من كومتين يجب إزالة نفس العدد. يفوز اللاعب الذي يزيل آخر حصاة أو آخر عدة حصيات. بشكل مكافئ، يمكن اعتبارها كحركة ملكة الشطرنج على شبكة كبيرة، حيث يمكن لكل لاعب تحريك الملكة أي عدد من الخطوات عمودياً أو أفقياً أو قطرياً نحو الزاوية العلوية اليسرى (0,0).

في متغير هذه الورقة، تُوسّع مجموعة المواضع النهائية إلى {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)}. يتم وصف مواضع P في هذا المتغير من خلال مواضع P في لعبة Wythoff ومتتالية Hofstadter's G. يتمتع هذا المتغير بخاصيتين بارزتين: بالنسبة للمواضع (x,y) حيث x≥8 أو y≥8، فإن رقم Grundy للموضع (x,y) في هذا المتغير يساوي 1 إذا وفقط إذا كان (x,y) موضع P في لعبة Wythoff؛ وبالنسبة للمواضع (x,y) حيث x≥8 أو y≥8، يكون (x,y) موضع P في نسخة misère من هذا المتغير إذا وفقط إذا كان (x,y) موضع P في لعبة Wythoff.

الخلفية البحثية والدافع

تعريف المشكلة

يهدف هذا البحث إلى تحليل وحل متغير جديد من لعبة Wythoff الكلاسيكية، حيث تُوسّع الشروط النهائية من موضع واحد (0,0) إلى مجموعة تحتوي على ستة مواضع. يبدو هذا التوسيع بسيطاً، لكنه يغير بشكل كبير التعقيد والبنية الاستراتيجية للعبة.

الأهمية

  1. الأهمية النظرية: لعبة Wythoff هي مشكلة كلاسيكية في نظرية الألعاب التوافقية، وترتبط مواضع P فيها ارتباطاً وثيقاً بالنسبة الذهبية φ=(1+√5)/2. يساعد دراسة متغيراتها على فهم أعمق لخصائص البنية في الألعاب التوافقية.
  2. الاتصال الرياضي: يؤسس هذا البحث اتصالاً جديداً بين متتالية Hofstadter's G ونظرية الألعاب التوافقية، وهو ما لم يتم تناوله كثيراً في الأبحاث السابقة.
  3. الابتكار المنهجي: من خلال إدخال الدالة g(n) ومتتالية Hofstadter's G، يوفر أدوات رياضية جديدة لتحليل الألعاب التوافقية ذات الشروط النهائية المعقدة.

قيود الطرق الموجودة

لمواضع P في لعبة Wythoff الكلاسيكية تعبيرات شكلية مغلقة واضحة، لكن عندما تصبح الشروط النهائية مجموعة من المواضع المتعددة، يصعب تطبيق طرق التحليل التقليدية بشكل مباشر. تفتقر نظرية الألعاب التوافقية الموجودة إلى طريقة منهجية للتعامل مع هذه الأنواع من الشروط النهائية الموسعة.

المساهمات الأساسية

  1. تعريف متغير لعبة جديد: توسيع مواضع النهاية في لعبة Wythoff من نقطة واحدة (0,0) إلى المجموعة {(x,y): x+y≤2}
  2. إنشاء توصيف كامل لمواضع P: من خلال إدخال الدالة g(n) ومتتالية Hofstadter's G، تقديم صيغة دقيقة لمواضع P في هذا المتغير
  3. اكتشاف خاصيتين مهمتين:
    • بالنسبة للمواضع حيث x≥8 أو y≥8، رقم Grundy في هذا المتغير يساوي 1 إذا وفقط إذا كان الموضع موضع P في لعبة Wythoff الأصلية
    • بالنسبة للمواضع حيث x≥8 أو y≥8، يكون الموضع موضع P في نسخة misère إذا وفقط إذا كان موضع P في لعبة Wythoff الأصلية
  4. إنشاء اتصال مع متتالية Hofstadter G: إثبات أن الدالة g(n) يمكن تعريفها بشكل تكراري من خلال متتالية Hofstadter's G

شرح الطريقة

تعريف المهمة

الإدخال: موضع اللعبة (x,y)، حيث x,y∈ℤ≥0 الإخراج: تحديد ما إذا كان الموضع موضع P (موضع فوز اللاعب السابق) أم موضع N (موضع فوز اللاعب التالي) القيود: قواعد الحركة هي نفسها في لعبة Wythoff الكلاسيكية، لكن المجموعة النهائية هي {(x,y): x+y≤2}

الإطار الرياضي الأساسي

1. تعريف الدالة g(n)

g(0) = 1, g(1) = 0
g(n) = {
  1 - g(m)  إذا كان ⌊nφ⌋ = ⌊m(φ+1)⌋ + 1 لبعض m∈ℤ≥0
  1         حالات أخرى
}

2. توصيف مجموعة مواضع P

P₁ = P₁,₁ ∪ P₁,₂ ∪ {(0,0)}، حيث:

  • P₁,₁ = {(⌊nφ⌋ + g(n) - 1, ⌊n(φ+1)⌋ + g(n)) : n ∈ ℤ≥0}
  • P₁,₂ = {(⌊n(φ+1)⌋ + g(n), ⌊nφ⌋ + g(n) - 1) : n ∈ ℤ≥0}

3. الاتصال مع متتالية Hofstadter G

بالنسبة لـ n≥2:

g(n) = {
  1 - g(h(n-1))  إذا كان h(n-2) < h(n-1)
  1              حالات أخرى
}

حيث h هي متتالية Hofstadter's G: h(0)=0, h(n)=n-h(h(n-1))

نقاط الابتكار التقني

  1. تقنية تحليل المتتالية: من خلال تحليل الأعداد الطبيعية إلى متتالية Wythoff السفلى A₁={⌊nφ⌋} ومتتالية Wythoff العليا A₂={⌊n(φ+1)⌋}، يتم إنشاء إطار تحليلي منهجي.
  2. تصميم الدالة التكرارية: يلتقط تصميم الدالة g(n) بذكاء تأثير توسيع المجموعة النهائية على توزيع مواضع P.
  3. تحليل رقم Grundy: من خلال حساب أرقام Grundy، يتم إنشاء اتصال عميق بين هذا المتغير واللعبة الأصلية.

إعداد التجربة

طريقة التحقق النظري

تستخدم هذه الورقة طريقة إثبات نظرية بحتة، من خلال الخطوات التالية للتحقق من النتائج:

  1. إثبات الاكتمال: إثبات أنه من أي موضع غير P يمكن الانتقال إلى موضع P
  2. إثبات الاتساق: إثبات أنه من موضع P لا يمكن الانتقال إلى موضع P آخر
  3. التحقق الحسابي: إجراء تحقق شامل للحالات الصغيرة

نطاق التحقق المحدد

  • تم إجراء تحليل شامل لجميع الحالات حيث إحداثيات الموضع x,y≤7
  • بالنسبة للحالات حيث x≥8 أو y≥8، يتم إنشاء علاقة تكافؤ مع لعبة Wythoff الأصلية من خلال الإثبات النظري

نتائج التجربة

النتائج النظرية الرئيسية

النظرية 1: التوصيف الكامل لمواضع P

المجموعة P₁ هي مجموعة مواضع P لمتغير هذه اللعبة، وهذا يتم إثباته من خلال Lemma 8 و Lemma 12:

  • Lemma 8: من موضع في P₁ لا يمكن الانتقال إلى موضع آخر في P₁
  • Lemma 12: من أي موضع ليس في P₁ يمكن الانتقال إلى موضع ما في P₁

النظرية 2: العلاقة مع لعبة Wythoff الأصلية

بالنسبة للمواضع (x,y) حيث x≥8 أو y≥8:

  • G₂(x,y,1)=0 في هذا المتغير إذا وفقط إذا كان G₀(x,y)=0 في اللعبة الأصلية
  • هذا يؤسس تكافؤاً بين اللعبتين في المواضع "الكبيرة"

النظرية 3: خصائص نسخة Misère

مواضع P في نسخة Misère (اللاعب الذي يدخل المجموعة النهائية يخسر) هي نفسها مواضع P في لعبة مجموع اللعبة الأصلية مع كومة حصى واحدة.

نتائج التحقق على نطاق صغير

من خلال التحقق الشامل، تم تحديد مجموعات مواضع P الصغيرة التالية:

  • المجموعة A: {(0,0,1), (0,1,1), (0,2,1), (1,0,1), (1,1,1), (2,0,1), (3,6,1), (6,3,1), (4,8,1), (8,4,1)}
  • المجموعة B: {(0,3,1), (1,2,1), (2,1,1), (3,0,1), (4,4,1), (5,7,1), (7,5,1)}
  • المجموعة C: {(0,0), (1,2), (2,1), (3,5), (5,3), (4,7), (7,4)}

الاكتشافات الرئيسية

  1. تأثيرات الحدود: في النطاق x,y≤7، يختلف توزيع مواضع P بشكل كبير عن لعبة Wythoff الأصلية
  2. السلوك المقارب: عندما تكون الإحداثيات كبيرة بما يكفي، يتقارب سلوك هذا المتغير مع لعبة Wythoff الأصلية
  3. خصائص المتتالية: نمط قيم الدالة g(n) يرتبط ارتباطاً وثيقاً بخصائص النمو لمتتالية Hofstadter G

الأعمال ذات الصلة

نظرية لعبة Wythoff

قدمت لعبة Wythoff الكلاسيكية من قبل W.A. Wythoff عام 1907، وتعتبر العلاقة بين مواضع P والنسبة الذهبية نتيجة كلاسيكية في الرياضيات التوافقية. تشمل الأبحاث ذات الصلة:

  • نظرية Rayleigh: تؤسس خصائص التقسيم لمتتاليات Wythoff السفلى والعليا
  • أبحاث حول متغيرات مختلفة من لعبة Wythoff

نظرية متتاليات Hofstadter

عرّف Hofstadter في كتابه "Gödel, Escher, Bach" عدة متتاليات تكرارية، حيث تتمتع متتالية G بخصائص نظرية أعداد خاصة:

  • أبحاث Gault و Clint (1988) حول الدوال التكرارية
  • تحليل Granville و Rasson (1988) للعلاقات التكرارية الشاذة

نظرية الألعاب التوافقية

تندرج هذه الورقة ضمن نطاق نظرية الألعاب التوافقية العادلة:

  • نظرية Sprague-Grundy وتطبيقاتها
  • طرق تحديد مواضع P ومواضع N
  • الإطار النظري للألعاب Misère

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. حل كامل: توفير توصيف كامل لمواضع P في متغير لعبة Wythoff ذو الشروط النهائية الموسعة
  2. اتصالات عميقة: الكشف عن الاتصال الجوهري بين هذا المتغير ومتتالية Hofstadter G
  3. التكافؤ المقارب: إثبات العلاقة التكافؤية بين هذا المتغير واللعبة الأصلية في حالة الإحداثيات الكبيرة

القيود

  1. التعقيد: تعريف الدالة g(n) معقد نسبياً، وليس أنيقاً مثل الحل الشكلي المغلق للعبة Wythoff الأصلية
  2. الكفاءة الحسابية: يتطلب تحديد مواضع P حساب متتالية Hofstadter، وقد توجد مشاكل في التعقيد الحسابي
  3. قابلية التعميم: ما إذا كانت الطريقة قابلة للتعميم على مجموعات نهائية أخرى لا تزال غير واضحة

الاتجاهات المستقبلية

  1. مجموعات نهائية أكثر عمومية: دراسة متغيرات لعبة Wythoff مع مجموعات نهائية عشوائية
  2. تحسين الخوارزمية: تطوير خوارزميات أكثر كفاءة لتحديد مواضع P
  3. متتاليات تكرارية أخرى: استكشاف تطبيقات متتاليات تكرارية شهيرة أخرى في الألعاب التوافقية

التقييم المتعمق

المميزات

  1. العمق النظري: إنشاء اتصال جديد بين نظرية الألعاب التوافقية ونظرية المتتاليات التكرارية، ذو قيمة نظرية مهمة
  2. الابتكار المنهجي: تصميم الدالة g(n) ذكي، حيث يلتقط البنية المعقدة للعبة من خلال التعريف التكراري
  3. الإثبات الكامل: توفير إثبات رياضي كامل، بما في ذلك حجج تفصيلية لعدد كبير من الليمات التقنية
  4. النتائج العميقة: الخصائص التكافؤية المقاربة المكتشفة توفر منظوراً جديداً لفهم الألعاب التوافقية المعقدة

أوجه القصور

  1. التعبير المعقد: تعريف الدالة g(n) مجرد نسبياً، وقد يؤثر على الفهم الحدسي للنتائج
  2. الفائدة العملية محدودة: على الرغم من الاكتمال النظري، فإن القيمة في التطبيقات العملية لا تزال غير واضحة
  3. صعوبة التعميم: قد تحد الخصوصية النسبية للطريقة من تطبيقها على مشاكل أخرى

التأثير

  1. القيمة الأكاديمية: فتح اتجاه جديد للبحث المتقاطع بين نظرية الألعاب التوافقية ونظرية المتتاليات التكرارية
  2. مساهمة منهجية: توفير أدوات جديدة لتحليل الألعاب التوافقية ذات الشروط النهائية المعقدة
  3. الاكتمال النظري: إثراء النظام النظري لمتغيرات لعبة Wythoff

السيناريوهات المناسبة

  1. البحث النظري: مناسبة للبحث النظري في الرياضيات التوافقية ونظرية الألعاب
  2. تصميم الخوارزميات: توفير أساس نظري لتصميم خوارزميات الاستراتيجية المثلى للألعاب ذات الصلة
  3. التطبيقات التعليمية: يمكن استخدامها كحالة ممتازة لعرض الاتصال بين المتتاليات التكرارية والمشاكل التوافقية

المراجع

  1. M.H. Albert, R.J. Nowakowski, and D. Wolfe: Lessons In Play, A K Peters/CRC Press, 2007
  2. D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, 1980
  3. W.A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wiskd, 7 (1907), 199-202
  4. V. Granville and J.-P. Rasson, A strange recursive relation, J. Number Theory 30 (1988), 238–241

قدمت هذه الورقة مساهمة نظرية مهمة في مجال نظرية الألعاب التوافقية، حيث وفرت إطاراً رياضياً كاملاً لتحليل متغيرات لعبة Wythoff ذات الشروط النهائية المعقدة من خلال الجمع الذكي بين متتالية Hofstadter G. على الرغم من وجود بعض القيود من حيث الفائدة العملية، فإن عمقها النظري وابتكارها المنهجي يجعلانها نتيجة بحثية مهمة في هذا المجال.