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

হফস্টাডটারের জি-সিকোয়েন্স দ্বারা সংজ্ঞায়িত উইথফ গেমের একটি রূপান্তর

মৌলিক তথ্য

পেপার আইডি: 2510.11767
শিরোনাম: A Variant of Wythoff's Game Defined by Hofstadter's G-Sequence
লেখক: কাহোরি কোমাকি, রিয়োহেই মিয়াডেরা, আই মুরাকামি
শ্রেণীবিভাগ: math.CO (সমন্বয় গণিত)
প্রকাশনার সময়: ২০২৫ সালের ১৩ অক্টোবর (arXiv প্রি-প্রিন্ট)
পেপার লিঙ্ক: https://arxiv.org/abs/2510.11767

সারসংক্ষেপ

এই পেপারটি ক্লাসিক্যাল উইথফ গেমের একটি রূপান্তর অধ্যয়ন করে। ক্লাসিক্যাল উইথফ গেমে দুটি পাথরের স্তূপ জড়িত থাকে, যেখানে দুই জন খেলোয়াড় পালাক্রমে একটি বা উভয় স্তূপ থেকে পাথর সরিয়ে নেয়, এবং উভয় স্তূপ থেকে সরিয়ে নেওয়ার সময় সমান সংখ্যক পাথর সরাতে হয়। শেষ পাথর বা শেষ কয়েকটি পাথর সরিয়ে নেওয়া খেলোয়াড় জয়ী হয়। সমতুল্যভাবে, এটিকে একটি বৃহৎ গ্রিডে আন্তর্জাতিক দাবার রানী সরানোর মতো দেখা যায়, যেখানে প্রতিটি খেলোয়াড় রানীকে উল্লম্ব, অনুভূমিক বা তির্যক দিকে যেকোনো সংখ্যক ধাপ বাম উপরের কোণ (0,0) এর দিকে সরাতে পারে।

এই পেপারের রূপান্তরে, টার্মিনাল অবস্থানের সেট {(0,0), (1,0), (0,1), (1,1), (2,0), (0,2)} এ প্রসারিত হয়। এই রূপান্তরের পি-অবস্থানগুলি উইথফ গেমের পি-অবস্থান এবং হফস্টাডটারের জি-সিকোয়েন্সের মাধ্যমে বর্ণনা করা হয়। এই রূপান্তরটির দুটি উল্লেখযোগ্য বৈশিষ্ট্য রয়েছে: x≥8 বা y≥8 এর অবস্থানের জন্য (x,y), এই রূপান্তরে অবস্থান (x,y) এর গ্রান্ডি সংখ্যা 1 যদি এবং শুধুমাত্র যদি (x,y) উইথফ গেমের একটি পি-অবস্থান হয়; x≥8 বা y≥8 এর অবস্থানের জন্য, (x,y) এই রূপান্তরের মিজেরে সংস্করণের একটি পি-অবস্থান যদি এবং শুধুমাত্র যদি (x,y) উইথফ গেমের একটি পি-অবস্থান হয়।

গবেষণার পটভূমি এবং প্রেরণা

সমস্যার সংজ্ঞা

এই গবেষণা ক্লাসিক্যাল উইথফ গেমের একটি নতুন রূপান্তর বিশ্লেষণ এবং সমাধান করার লক্ষ্য রাখে, যেখানে টার্মিনাল শর্ত একক অবস্থান (0,0) থেকে ছয়টি অবস্থান সম্বলিত একটি সেটে প্রসারিত হয়। এই সম্প্রসারণ সরল মনে হলেও, গেমের জটিলতা এবং কৌশলগত কাঠামোকে উল্লেখযোগ্যভাবে পরিবর্তন করে।

গুরুত্ব

তাত্ত্বিক তাৎপর্য: উইথফ গেম সমন্বয় খেলা তত্ত্বের একটি ক্লাসিক সমস্যা, এর পি-অবস্থান স্বর্ণ অনুপাত φ=(1+√5)/2 এর সাথে ঘনিষ্ঠভাবে সম্পর্কিত। এর রূপান্তর অধ্যয়ন সমন্বয় খেলার কাঠামোগত বৈশিষ্ট্য গভীরভাবে বোঝাতে সহায়তা করে।
গাণিতিক সংযোগ: এই গবেষণা হফস্টাডটারের জি-সিকোয়েন্স এবং সমন্বয় খেলা তত্ত্বের মধ্যে নতুন সংযোগ স্থাপন করে, যা পূর্ববর্তী গবেষণায় কম অন্বেষণ করা হয়েছে।
পদ্ধতিগত উদ্ভাবন: g(n) ফাংশন এবং হফস্টাডটারের জি-সিকোয়েন্স প্রবর্তন করে, জটিল টার্মিনাল শর্ত সহ সমন্বয় খেলা বিশ্লেষণের জন্য নতুন গাণিতিক সরঞ্জাম প্রদান করে।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

ক্লাসিক্যাল উইথফ গেমের পি-অবস্থানের স্পষ্ট বন্ধ-ফর্ম অভিব্যক্তি রয়েছে, কিন্তু যখন টার্মিনাল শর্ত একাধিক অবস্থানের সেটে পরিণত হয়, তখন ঐতিহ্যবাহী বিশ্লেষণ পদ্ধতি সরাসরি প্রয়োগ করা কঠিন। বিদ্যমান সমন্বয় খেলা তত্ত্ব এই ধরনের সম্প্রসারিত টার্মিনাল শর্ত পরিচালনার জন্য একটি পদ্ধতিগত পদ্ধতির অভাব রয়েছে।

মূল অবদান

নতুন গেম রূপান্তর সংজ্ঞায়িত করা: উইথফ গেমের টার্মিনাল অবস্থান একক বিন্দু (0,0) থেকে সেট {(x,y): x+y≤2} এ প্রসারিত করা
পি-অবস্থানের সম্পূর্ণ চিত্রকল্প প্রতিষ্ঠা করা: g(n) ফাংশন এবং হফস্টাডটারের জি-সিকোয়েন্স প্রবর্তন করে, এই রূপান্তরের পি-অবস্থানের নির্ভুল সূত্র প্রদান করা
দুটি গুরুত্বপূর্ণ বৈশিষ্ট্য আবিষ্কার করা:
- x≥8 বা y≥8 এর অবস্থানের জন্য, এই রূপান্তরের গ্রান্ডি সংখ্যা 1 যদি এবং শুধুমাত্র যদি অবস্থানটি মূল উইথফ গেমের পি-অবস্থান হয়
- x≥8 বা y≥8 এর অবস্থানের জন্য, অবস্থানটি মিজেরে সংস্করণের পি-অবস্থান যদি এবং শুধুমাত্র যদি এটি মূল উইথফ গেমের পি-অবস্থান হয়
হফস্টাডটার জি-সিকোয়েন্সের সাথে সংযোগ স্থাপন করা: প্রমাণ করা যে g(n) ফাংশন হফস্টাডটারের জি-সিকোয়েন্সের মাধ্যমে পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত করা যায়

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

ইনপুট: গেম অবস্থান (x,y), যেখানে x,y∈ℤ≥0 আউটপুট: নির্ধারণ করা যে অবস্থানটি পি-অবস্থান (পূর্ববর্তী খেলোয়াড়ের জয়ী অবস্থান) নাকি এন-অবস্থান (পরবর্তী খেলোয়াড়ের জয়ী অবস্থান) সীমাবদ্ধতা: চলার নিয়ম ক্লাসিক্যাল উইথফ গেমের মতো, কিন্তু টার্মিনাল সেট {(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₁,₂ ∪ {(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. হফস্টাডটার জি-সিকোয়েন্সের সাথে সংযোগ

n≥2 এর জন্য:

g(n) = {
  1 - g(h(n-1))  যদি h(n-2) < h(n-1)
  1              অন্যথায়
}

যেখানে h হফস্টাডটারের জি-সিকোয়েন্স: h(0)=0, h(n)=n-h(h(n-1))

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

সিকোয়েন্স বিয়োজন কৌশল: প্রাকৃতিক সংখ্যাকে নিম্ন উইথফ সিকোয়েন্স A₁={⌊nφ⌋} এবং উচ্চ উইথফ সিকোয়েন্স A₂={⌊n(φ+1)⌋} এ বিয়োজন করে, একটি পদ্ধতিগত বিশ্লেষণ কাঠামো প্রতিষ্ঠা করা।
পুনরাবৃত্তিমূলক ফাংশন ডিজাইন: g(n) ফাংশনের ডিজাইন চতুরতার সাথে টার্মিনাল সেট সম্প্রসারণের পি-অবস্থান বিতরণে প্রভাব ক্যাপচার করে।
গ্রান্ডি সংখ্যা বিশ্লেষণ: গ্রান্ডি সংখ্যা গণনা করে, এই রূপান্তর এবং মূল গেমের মধ্যে গভীর সংযোগ প্রতিষ্ঠা করা।

পরীক্ষামূলক সেটআপ

তাত্ত্বিক যাচাইকরণ পদ্ধতি

এই পেপারটি বিশুদ্ধ তাত্ত্বিক প্রমাণ পদ্ধতি গ্রহণ করে, নিম্নলিখিত পদক্ষেপের মাধ্যমে ফলাফল যাচাই করে:

সম্পূর্ণতা প্রমাণ: যেকোনো অ-পি অবস্থান থেকে পি-অবস্থানে চলা যায় তা প্রমাণ করা
সামঞ্জস্য প্রমাণ: পি-অবস্থান থেকে অন্য পি-অবস্থানে চলা যায় না তা প্রমাণ করা
গণনামূলক যাচাইকরণ: ছোট-স্কেল ক্ষেত্রে সম্পূর্ণ পরিমাপ বিশ্লেষণ সম্পাদন করা

নির্দিষ্ট যাচাইকরণ পরিসীমা

অবস্থান স্থানাঙ্ক x,y≤7 এর সমস্ত ক্ষেত্রে সম্পূর্ণ পরিমাপ বিশ্লেষণ সম্পাদন করা হয়েছে
x≥8 বা y≥8 এর ক্ষেত্রে, তাত্ত্বিক প্রমাণের মাধ্যমে মূল উইথফ গেমের সাথে সমতুল্য সম্পর্ক প্রতিষ্ঠা করা হয়েছে

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য 1: পি-অবস্থানের সম্পূর্ণ চিত্রকল্প

সেট P₁ এই গেম রূপান্তরের পি-অবস্থান সেট, যা লেমা 8 এবং লেমা 12 দ্বারা প্রমাণিত:

লেমা 8: P₁ এর অবস্থান থেকে P₁ এর অন্য অবস্থানে চলা যায় না
লেমা 12: P₁ এর বাইরে যেকোনো অবস্থান থেকে P₁ এর কোনো অবস্থানে চলা যায়

উপপাদ্য 2: মূল উইথফ গেমের সাথে সম্পর্ক

x≥8 বা y≥8 এর অবস্থানের জন্য (x,y):

এই রূপান্তরে G₂(x,y,1)=0 যদি এবং শুধুমাত্র যদি মূল গেমে G₀(x,y)=0
এটি দুটি গেমের মধ্যে "বড়" অবস্থানে সমতুল্যতা প্রতিষ্ঠা করে

উপপাদ্য 3: মিজেরে সংস্করণের বৈশিষ্ট্য

মিজেরে সংস্করণ (টার্মিনাল সেট ইনপুট করা খেলোয়াড় পরাজিত হয়) এর পী-অবস্থান মূল গেম যোগ একক পাথরের স্তূপের পি-অবস্থানের সমান।

ছোট-স্কেল যাচাইকরণ ফলাফল

পরিমাপ যাচাইকরণের মাধ্যমে, নিম্নলিখিত ছোট-স্কেল পী-অবস্থান সেট নির্ধারণ করা হয়েছে:

সেট 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)}

মূল আবিষ্কার

সীমানা প্রভাব: x,y≤7 পরিসরে, পী-অবস্থান বিতরণ মূল উইথফ গেম থেকে উল্লেখযোগ্যভাবে আলাদা
অ্যাসিম্পটোটিক আচরণ: যখন স্থানাঙ্ক যথেষ্ট বড় হয়, এই রূপান্তরের আচরণ মূল উইথফ গেমে রূপান্তরিত হয়
সিকোয়েন্স বৈশিষ্ট্য: g(n) ফাংশনের মূল্য প্যাটার্ন হফস্টাডটার জি-সিকোয়েন্সের বৃদ্ধির বৈশিষ্ট্যের সাথে ঘনিষ্ঠভাবে সম্পর্কিত

উপসংহার এবং আলোচনা

প্রধান উপসংহার

সম্পূর্ণ সমাধান: উইথফ গেম সম্প্রসারিত টার্মিনাল রূপান্তরের পী-অবস্থানের সম্পূর্ণ চিত্রকল্প প্রদান করা
গভীর সংযোগ: এই রূপান্তর এবং হফস্টাডটার জি-সিকোয়েন্সের মধ্যে অপরিহার্য সংযোগ প্রকাশ করা
অ্যাসিম্পটোটিক সমতুল্যতা: বড় স্থানাঙ্কের ক্ষেত্রে এই রূপান্তর এবং মূল গেমের সমতুল্য সম্পর্ক প্রমাণ করা

সীমাবদ্ধতা

জটিলতা: g(n) ফাংশনের সংজ্ঞা অপেক্ষাকৃত জটিল, মূল উইথফ গেমের বন্ধ-ফর্ম সমাধানের মতো মার্জিত নয়
গণনামূলক দক্ষতা: পী-অবস্থান নির্ধারণের জন্য হফস্টাডটার সিকোয়েন্স গণনা প্রয়োজন, সম্ভাব্য গণনামূলক জটিলতা সমস্যা থাকতে পারে
সাধারণীকরণযোগ্যতা: পদ্ধতি অন্যান্য টার্মিনাল সেটে সাধারণীকরণ করা যায় কিনা তা অস্পষ্ট

ভবিষ্যত দিকনির্দেশনা

আরও সাধারণ টার্মিনাল সেট: যেকোনো টার্মিনাল সেটের উইথফ গেম রূপান্তর অধ্যয়ন করা
অ্যালগরিদম অপ্টিমাইজেশন: পী-অবস্থান নির্ধারণের জন্য আরও দক্ষ অ্যালগরিদম উন্নয়ন করা
অন্যান্য পুনরাবৃত্তিমূলক সিকোয়েন্স: সমন্বয় খেলায় অন্যান্য বিখ্যাত পুনরাবৃত্তিমূলক সিকোয়েন্সের প্রয়োগ অন্বেষণ করা

গভীর মূল্যায়ন

শক্তি

তাত্ত্বিক গভীরতা: সমন্বয় খেলা তত্ত্ব এবং পুনরাবৃত্তিমূলক সিকোয়েন্স তত্ত্বের মধ্যে নতুন সংযোগ প্রতিষ্ঠা করে, গুরুত্বপূর্ণ তাত্ত্বিক মূল্য রয়েছে
পদ্ধতিগত উদ্ভাবন: g(n) ফাংশনের ডিজাইন চতুর, পুনরাবৃত্তিমূলক সংজ্ঞার মাধ্যমে জটিল গেম কাঠামো ক্যাপচার করে
প্রমাণ সম্পূর্ণতা: সম্পূর্ণ গাণিতিক প্রমাণ প্রদান করে, অসংখ্য প্রযুক্তিগত লেমার বিস্তারিত যুক্তি সহ
ফলাফল গভীরতা: আবিষ্কৃত অ্যাসিম্পটোটিক সমতুল্যতা বৈশিষ্ট্য জটিল সমন্বয় খেলা বোঝার জন্য নতুন দৃষ্টিভঙ্গি প্রদান করে

অপূর্ণতা

অভিব্যক্তি জটিলতা: g(n) ফাংশনের সংজ্ঞা অপেক্ষাকৃত বিমূর্ত, ফলাফলের স্বজ্ঞাত বোঝাপড়াকে প্রভাবিত করতে পারে
সীমিত ব্যবহারিকতা: যদিও তাত্ত্বিকভাবে সম্পূর্ণ, বাস্তব প্রয়োগে এর মূল্য অস্পষ্ট
সাধারণীকরণ অসুবিধা: পদ্ধতির বিশেষত্ব অন্যান্য সমস্যায় এর প্রয়োগ সীমিত করতে পারে

প্রভাব

একাডেমিক মূল্য: সমন্বয় বোগেম তত্ত্ব এবং পুনরাবৃত্তিমূলক সিকোয়েন্স তত্ত্বের ক্রস-ডিসিপ্লিনারি গবেষণার জন্য নতুন দিকনির্দেশনা খুলে দেয়
পদ্ধতিগত অবদান: জটিল টার্মিনাল শর্ত সহ সমন্বয় খেলা বিশ্লেষণের জন্য নতুন সরঞ্জাম প্রদান করে
তাত্ত্বিক সম্পূর্ণতা: উইথফ গেম রূপান্তরের তাত্ত্বিক ব্যবস্থা সমৃদ্ধ করে

প্রযোজ্য পরিস্থিতি

তাত্ত্বিক গবেষণা: সমন্বয় গণিত এবং খেলা তত্ত্বের তাত্ত্বিক গবেষণার জন্য উপযুক্ত
অ্যালগরিদম ডিজাইন: সম্পর্কিত গেমের সর্বোত্তম কৌশল অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক ভিত্তি প্রদান করে
শিক্ষা প্রয়োগ: পুনরাবৃত্তিমূলক সিকোয়েন্স এবং সমন্বয় সমস্যার সংযোগ প্রদর্শনের জন্য একটি চমৎকার কেস হিসাবে কাজ করতে পারে

সংদর্ভ

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

এই পেপারটি সমন্বয় বোগেম তত্ত্বের ক্ষেত্রে গুরুত্বপূর্ণ তাত্ত্বিক অবদান করে, হফস্টাডটার জি-সিকোয়েন্সকে চতুরতার সাথে একত্রিত করে, জটিল টার্মিনাল শর্ত সহ উইথফ গেম রূপান্তর বিশ্লেষণের জন্য একটি সম্পূর্ণ গাণিতিক কাঠামো প্রদান করে। যদিও ব্যবহারিক দিক থেকে নির্দিষ্ট সীমাবদ্ধতা রয়েছে, তবে এর তাত্ত্বিক গভীরতা এবং পদ্ধতিগত উদ্ভাবন এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ গবেষণা ফলাফল করে তোলে।