مسئله: اعداد طبیعی روی صفحهٔ شطرنجی نامتناهی

آیا می‌توان در هر خانه از یک صفحهٔ شطرنجی نامتناهی یک عدد طبیعی نوشت،
به‌طوری که:

1. هر عدد طبیعی دقیقاً در یک خانه نوشته شده باشد (هیچ عددی تکرار نشود و هیچ عددی جا نماند)،

2. عدد نوشته‌شده در هر خانه، مقسوم‌علیه مجموع چهار عدد مجاور خود باشد
   (چهار خانهٔ بالا، پایین، چپ و راست).

المپیاد ریاضی لهستان، ۲۰۰۷

---

پاسخ

مسئله یک شرط محلی دارد: در هر خانه فقط مجموع چهار همسایهٔ همان خانه مهم است. این جملهٔ ساده، جهت حل را پیشنهاد می‌کند:

اگر بتوانیم یک «قطعه»‌ی محدود بسازیم که در آن،
خانه‌هایی که واقعاً چهار همسایه دارند شرط را درست ارضا کنند،
آن‌وقت می‌توانیم این قطعه را بزرگ‌تر و بزرگ‌تر کنیم و هر بار فقط روی «مرزِ جدید» کنترل داشته باشیم.

---

ایدهٔ کلی: ساختن و رشد دادن

چیزی که به ذهن می‌رسد این است که:

1. ابتدا یک جدول محدود طراحی کنیم که درونش (خانه‌های داخلی) شرط دقیقاً برقرار باشد؛
   اما خانه‌های مرزی را فعلاً جدی نگیریم (چون در مرحلهٔ بعد قرار است همسایه‌های جدید پیدا کنند).

2. سپس این جدول را داخل یک جدول بزرگ‌تر قرار دهیم و مرز را با اعداد تازه «ترمیم» کنیم؛
   به‌طوری که حالا خانه‌هایی که قبلاً مرزی بودند، به خانه‌های داخلی تبدیل شوند و شرط برای آن‌ها هم برقرار شود.

3. این کار را مرحله‌به‌مرحله ادامه دهیم؛
   در هر مرحله، یک ناحیهٔ بزرگ‌تر از صفحه را «قطعی» می‌کنیم (یعنی خانه‌های داخلی‌اش دیگر هیچ‌وقت در مراحل بعد دست نمی‌خورند).

در نهایت، اگر این فرایند طوری طراحی شود که:

• در هر مرحله فقط از اعداد طبیعیِ تازه استفاده کنیم (بدون تکرار)،
• و هر عدد طبیعی بالاخره در یکی از مراحل وارد جدول شود (بدون جا ماندن)،

آن‌وقت در حد نهایی، کل صفحهٔ نامتناهی پر می‌شود و شرط مسئله در همه‌جا برقرار خواهد بود.

---

نخستین تلاش

نخستین مسیری که من به سراغش رفتم و به بن‌بست خوردم این بود که برای $n$های فرد یک جدول $n\times n$ بسازیم که:

• اعداد $1,2,\dots,n^2$ را دقیقاً یک‌بار در خودش داشته باشد،
• و شرط مسئله برای خانه‌های داخلی برقرار باشد
  (یعنی برای خانه‌هایی که چهار همسایه دارند).

خانه‌های مرزی را فعلاً نادیده می‌گرفتیم، چون امید این بود که در مرحلهٔ بعد با بزرگ‌تر کردن جدول، آن‌ها هم چهار همسایه پیدا کنند.

تلاش کردم در مثال‌های کوچک نظمی برای گسترش چنین جدول‌هایی پیدا کنم، اما به یک قاعدهٔ پایدار نرسیدم.

ایده‌ی زیر از آقای سامان فرحت این مشکل را حل می‌کند.

---

ایدهٔ اصلی: رها کردن یک قید اضافی

در تلاش قبلی، خودمان را به یک قید غیرضروری مقید کرده بودیم: این‌که در یک جدول $n\times n$ دقیقاً اعداد $1,2,\dots,n^2$ ظاهر شوند.

در اینجا این قید را کنار می‌گذاریم.

کاری که می‌خواهیم انجام دهیم این است:

• یک جدول $n\times n$ بسازیم که شرط مسئله را برای خانه‌های داخلی ارضا کند،
• عددی در جدول تکرار نشود،
• اما لازم نیست مجموعهٔ اعداد ظاهرشده دقیقاً ${1,\dots,n^2}$ باشد.

این آزادیِ اضافی، دست ما را برای طراحی ساختاری باز می‌کند که شرطِ مقسوم‌علیه بودن به‌صورت ذاتی در آن برقرار باشد.

---

گسترش جدول: اضافه کردن یک نوار

فرض کنید در یک مرحله، یک جدول $n\times n$ داریم (با $n$ فرد) که در آن:

• هیچ عددی تکرار نشده است،
• و شرط مسئله برای تمام خانه‌های داخلیِ این جدول برقرار است.

برای رفتن به مرحلهٔ بعد، یک نوارِ یک‌خانه‌ای دور جدول می‌کشیم و جدول را به $(n+2)\times(n+2)$ بزرگ می‌کنیم.

این نوار را به دو بخش تقسیم می‌کنیم:

1. چهار خانهٔ گوشه (قرمز‌)،
2. خانه‌های غیرگوشهٔ نوار (سفید) (خانه‌هایی که روی ضلع‌ها قرار می‌گیرند).

در این بخش فقط خانه‌های غیرگوشهٔ نوار را پر می‌کنیم.

---

خانه‌های غیرگوشهٔ نوار (سفید)

یک خانهٔ غیرگوشهٔ نوار را با $x$ نشان می‌دهیم. این خانه دقیقاً با یک خانه از جدول قبلی همسایه است؛ آن همسایه را $a$ می‌نامیم.

سه همسایهٔ دیگرِ $a$ (در جدول قبلی) از قبل مشخص‌اند؛ آن‌ها را $b,c,d$ می‌نامیم. پس در لحظه‌ای که می‌خواهیم $x$ را انتخاب کنیم، مقدار

$$S := b+c+d$$

عدد ثابتی است.

شرط مسئله برای خانهٔ $a$ در جدولِ بزرگ‌شده این است که:

$$a \mid (b+c+d+x) \qquad\Longleftrightarrow\qquad x \equiv -S \pmod a.$$

پس مقدار $x$ به پیمانهٔ $a$ کاملاً تعیین شده است.

---

قانون انتخاب: «کمترین عضوِ استفاده‌نشده در یک پیمانه»

باقی می‌ماند این‌که از میان تمام اعداد طبیعی که هم‌نهشتِ $-S$ به پیمانهٔ $a$ هستند، یکی را انتخاب کنیم که با اعداد قبلی تداخل نداشته باشد.

برای این کار، برای هر پیمانهٔ $a$ و هر باقی‌ماندهٔ $r$، مجموعهٔ کاندیداها را در نظر بگیرید:

$$\mathcal{C}(a,r)=\{\, r+ka \mid k\ge 0 \,\}.$$

اکنون برای خانهٔ $x$ که باید $x \equiv r \pmod a \quad (r\equiv -S\pmod a)$ باشد، مقدار $x$ را این‌گونه تعریف می‌کنیم:

$x$ را برابر کمترین عدد در $\mathcal{C}(a,r)$ بگیرید که تا این لحظه در جدول به کار نرفته باشد.

به بیان دقیق‌تر: اگر $\mathcal{U}$ مجموعهٔ اعدادی باشد که تا این لحظه در جدول نوشته‌ایم، آنگاه

$$x := \min\big(\mathcal{C}(a,r)\setminus \mathcal{U}\big).$$

---

این انتخاب دو خاصیت را همزمان تضمین می‌کند:

• شرطِ لازم برای خانهٔ $a$ برقرار می‌ماند (چون $x$ دقیقاً در پیمانهٔ درست انتخاب شده)،
• و هیچ عددی تکرار نمی‌شود (چون $x$ از ابتدا خارج از $\mathcal{U}$ انتخاب شده است).

---

مشکلِ «جا ماندن» و نقشِ چهار خانهٔ گوشه

قانونی که برای خانه‌های غیرگوشهٔ نوار گفتیم، دو چیز را تضمین می‌کند:

• شرطِ مقسوم‌علیه بودن برای خانه‌های داخلیِ مرحلهٔ قبل خراب نمی‌شود،
• و هیچ عددی تکرار نمی‌شود.

اما یک نگرانی باقی می‌ماند:
ممکن است بعضی اعداد طبیعی هیچ‌وقت انتخاب نشوند؛ چون ما هر بار فقط از چند تصاعد حسابیِ خاص انتخاب می‌کنیم.

اینجاست که چهار خانهٔ گوشه به کمک ما می‌آیند.

---

قانونِ گوشه‌ها

در پایان هر مرحله (پس از پر کردن خانه‌های غیرگوشهٔ نوار)، به سراغ اعدادِ هنوز-استفاده‌نشده می‌رویم و:

چهار عددِ کوچکِ استفاده‌نشده را برداشته و در چهار خانهٔ گوشه می‌نویسیم.

چرا این کار شرطی را خراب نمی‌کند؟

چون در این مرحله، تنها خانه‌هایی که ممکن است شرطشان تحت تأثیر قرار بگیرد، خانه‌های کنارِ گوشه‌ها هستند، و این خانه‌ها (در لحظهٔ پر شدنشان) هنوز جزو «خانه‌های داخلیِ قطعی» نیستند و در مرحله‌ی بعد شرطشان ارضا می‌شود.

---

چرا هیچ عددی جا نمی‌ماند؟

در هر مرحله دقیقاً چهار عددِ جدید (کوچک‌ترین‌های باقی‌مانده) را با قانونِ گوشه‌ها وارد جدول می‌کنیم. پس اگر عددی تا مرحله‌ای وارد نشده باشد، در میان اعدادِ استفاده‌نشده حضور دارد، و چون همیشه کوچک‌ترین‌ها را برمی‌داریم، دیر یا زود نوبتش می‌رسد.

به طور مشخص:

هر عدد طبیعی در حداکثر $\frac{n}{4}$ مرحله حتماً نوشته می‌شود.

---

نتیجه

پس الگوریتم ساخت ما سه ویژگی را همزمان دارد:

1. هیچ عددی تکرار نمی‌شود،
2. هر عدد طبیعی بالاخره وارد جدول می‌شود،
3. و شرطِ مسئله در حد نهایی (روی صفحهٔ نامتناهی) برقرار است.

بنابراین پاسخ سؤال بله است:
چنین چیدمانی روی صفحهٔ شطرنجی نامتناهی وجود دارد.