کاشی‌کاری و ریشه‌های واحد

رنگ‌آمیزی با اعداد مختلط

در برگهٔ ریشه‌های واحد دیدیم که جمعِ ریشه‌های $n$-اُم واحد صفر است. در این برگه این حقیقت را برای حل چند مسئله‌ی رنگ‌آمیزی به‌کار می‌بریم. اگر با اعداد مختلط آشنا نیستید، مجموعهٔ اعداد مختلط همه‌چیز را از صفر می‌سازد.

---

مسئله

مسئله. آیا می‌توان صفحهٔ شطرنجیِ $10 \times 10$ را با کاشی‌های $1 \times 4$ فرش کرد؟ هر کاشی چهار خانهٔ متوالی را در یک سطر یا یک ستون می‌پوشاند؛ کاشی‌ها نه روی هم می‌روند و نه از صفحه بیرون می‌زنند.

پیش از خواندنِ ادامه، چند کاشی روی کاغذ بچینید و ببینید کار کجا گیر می‌کند.

---

بررسی‌های اولیه

اولین بررسی‌ای که به ذهن می‌رسد مساحت است: هر کاشی چهار خانه را می‌پوشاند، پس تعدادِ خانه‌های صفحه باید مضربِ ۴ باشد. و هست: $100 = 4 \times 25$. یعنی از نظرِ شمارش، ۲۵ کاشی دقیقاً جا می‌شود.

تلاشِ بعدی رنگ‌آمیزیِ شطرنجیِ صفحه است، سیاه و سفید یک‌درمیان. اما هر کاشی $1 \times 4$ — افقی یا عمودی — دقیقاً دو خانهٔ سیاه و دو خانهٔ سفید می‌پوشاند، و صفحه هم ۵۰ سیاه و ۵۰ سفید دارد. پس دو طرف همیشه می‌خوانند و تناقضی به دست نمی‌آید.

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

---

چهار رنگ به‌جای دو

خانهٔ سطرِ $r$ و ستونِ $c$ را $(r, c)$ بنامیم؛ سطرها را از بالا و ستون‌ها را از چپ، از ۱ تا ۱۰ شماره می‌دهیم. رنگِ هر خانه را باقی‌ماندهٔ $r + c$ بر ۴ می‌گیریم: چهار رنگ که روی هر قطر ثابت‌اند و از قطری به قطرِ بعد یکی جلو می‌روند.

رنگِ خانهٔ $(r, c)$ باقی‌ماندهٔ $r + c$ بر ۴ است؛ رنگ‌ها راه‌راهِ قطری می‌سازند. دو کاشیِ نمونه — یکی افقی، یکی عمودی — هر کدام از هر چهار رنگ دقیقاً یک خانه می‌پوشانند.

چرا این رنگ‌آمیزی به دردِ کاشیِ $1 \times 4$ می‌خورد؟ چون کاشی — افقی یا عمودی — چهار خانه‌ای را می‌پوشاند که $r + c$شان چهار عددِ پیاپی است، و چهار عددِ پیاپی چهار باقی‌ماندهٔ متفاوت دارند. پس هر کاشی، هر جا که بنشیند، از هر رنگ دقیقاً یک خانه برمی‌دارد.

در یک فرشِ کامل ۲۵ کاشی داریم و هر کاشی از هر رنگ یکی دارد؛ پس از هر چهار رنگ باید دقیقاً ۲۵ خانه داشته باشیم. حالا بشمارید (زیرِ شکل آمده): اندازهٔ کلاس‌های رنگی، به‌ترتیب برای باقی‌مانده‌های $0, 1, 2, 3$، برابر است با ۲۵، ۲۴، ۲۵ و ۲۶. برابر نیستند — و همین، مانع است.

صفحهٔ $10 \times 10$ با کاشی $1 \times 4$ فرش نمی‌شود.

مسئله حل شد. اما یک مسئلهٔ خوب معمولاً بیش از یک راه دارد، و دیدنش از زاویهٔ دوم لذتِ خودش را: در گام بعد همین رنگ‌آمیزی را یک بار دیگر می‌نویسیم، این بار با اعداد مختلط — به‌جای رنگ، به هر خانه یک وزن می‌دهیم. زبانِ تازه‌ای است برای همان ایده، و بعدتر می‌بینیم که در مسئله‌های دیگر هم به کار می‌آید.

---

وزن به‌جای رنگ

رنگ‌ها اسم‌اند و اسم‌ها را نمی‌شود جمع زد. پس به هر رنگ یک عدد نسبت می‌دهیم — اما نه هر چهار عددی: چهار عددی که جمعشان صفر باشد، تا «از هر رنگ یکی» به «جمعِ صفر» ترجمه شود. ریشه‌های چهارمِ واحد دقیقاً همین‌اند.

$\omega$ را نخستین ریشهٔ چهارمِ واحد پس از ۱ بگیرید: نقطه‌ای روی دایرهٔ واحد با اندازهٔ $\lvert \omega \rvert = 1$ و زاویهٔ یک‌چهارمِ دور، یعنی $\tfrac{2\pi}{4} = \tfrac{\pi}{2}$ یا ۹۰ درجه. پس

$$\omega = \cos\frac{\pi}{2} + i \sin\frac{\pi}{2} = i$$

توان‌هایش هر بار ۹۰ درجه می‌چرخند و در چهار قدم به خانهٔ اول برمی‌گردند: $\omega^4 = 1$. و همان حقیقتی که از برگهٔ ریشه‌های واحد آورده‌ایم:

$$1 + \omega + \omega^2 + \omega^3 = 0$$

از این‌جا به بعد با نمادِ $\omega$ کار می‌کنیم و به مقدارش کاری نداریم؛ فقط همین دو خاصیت لازم است: $\omega^4 = 1$، و صفر بودنِ جمعِ چهار توانِ پیاپی. (سودش را در بخشِ بعد می‌بینید: استدلال، بی‌یک کلمه تغییر، برای هر $k$ کار می‌کند.)

حالا به‌جای رنگ، وزن می‌گذاریم:

$$w(r, c) = \omega^{\,r+c}$$

این دقیقاً همان رنگ‌آمیزیِ قبل است — هم‌رنگ‌ها هم‌وزن‌اند — فقط چهار اسم جای خود را به چهار عدد دادند:

همان صفحه و همان چهار کلاس؛ فقط به‌جای نامِ رنگ، وزنِ $\omega^{\,r+c}$. جمعِ وزن‌های هر کاشیِ نمونه $1 + \omega + \omega^2 + \omega^3$ است.

و این است سودِ عددی‌شدن: جمعِ وزن‌های هر کاشی صفر است. کاشیِ افقی که از خانهٔ $(r, c)$ شروع شود:

$$\omega^{\,r+c} + \omega^{\,r+c+1} + \omega^{\,r+c+2} + \omega^{\,r+c+3} = \omega^{\,r+c}\left(1 + \omega + \omega^2 + \omega^3\right) = 0$$

کاشی عمودی هم همین حساب را دارد: وزن فقط به $r + c$ بسته است و فرقی نمی‌کند چهار قدمِ پیاپی را در کدام جهت برداریم.

پس اگر کاشی‌کاریِ کاملی وجود داشت، جمعِ وزنِ کلِ صفحه — که جمعِ ۲۵ کاشیِ صفرجمع است — باید صفر می‌شد. حالا جمعِ کل را مستقل حساب می‌کنیم. نکتهٔ کلیدی این است که وزنِ ما ضربی است: $\omega^{\,r+c} = \omega^{\,r}\, \omega^{\,c}$؛ پس جمعِ صد خانه به حاصل‌ضربِ دو جمعِ ساده تجزیه می‌شود:

$$\sum_{r=1}^{10} \sum_{c=1}^{10} \omega^{\,r+c} = \left(\sum_{r=1}^{10} \omega^{\,r}\right)\left(\sum_{c=1}^{10} \omega^{\,c}\right)$$

(اگر پرانتزها را باز کنید، هر جمله دقیقاً یک خانه است.) و جمعِ توان‌های $\omega$ از ۱ تا ۱۰ ساده است: هر چهار توانِ پیاپی یک دورِ کاملِ چرخه است و صفر می‌شود؛ از ده جمله، هشت‌تا در دو دورِ کامل می‌سوزند و فقط دو جملهٔ آخر می‌مانند:

$$\sum_{r=1}^{10} \omega^{\,r} = \omega^{9} + \omega^{10} = \omega + \omega^2$$

پس جمعِ کل برابرِ $\left(\omega + \omega^2\right)^2$ است. صفر است یا نه؟ این‌جا یک بار به مقدارِ $\omega$ برمی‌گردیم: $\omega + \omega^2 = i - 1$، و

$$\sum_{r,\,c} \omega^{\,r+c} = (i - 1)^2 = -2i \neq 0$$

جمعِ کل صفر نیست؛ ولی اگر کاشی‌کاری ممکن بود، باید صفر می‌شد. همان حکمِ قبل، این بار از دلِ یک حساب بیرون آمد.

عددِ مختلط این وسط چه‌کاره بود؟ بسته‌بندی. اگر تعدادِ خانه‌های هر رنگ را $N_0, N_1, N_2, N_3$ بنامیم، جمعِ وزنِ صفحه چیزی نیست جز

$$N_0 + N_1\,\omega + N_2\,\omega^2 + N_3\,\omega^3 = (N_0 - N_2) + (N_1 - N_3)\,i = (25 - 25) + (24 - 26)\,i = -2i$$

چهار شمارش در یک عدد جمع شدند، و ناصفر بودنِ آن عدد یعنی دست‌کم یکی از توازن‌ها به هم خورده است. و جالب این‌که در حسابِ بالا اصلاً این چهار عدد را نشمردیم: تجزیه به دو جمعِ ساده، خودش کارِ شمارش را کرد.

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

---

حالت کلی: قضیهٔ دِ بروین

همین وزن‌دهی، بی‌هیچ خرجِ تازه‌ای، حکم کلی را هم می‌دهد — نتیجه‌ای از دِ بروین (de Bruijn):

مستطیل $m \times n$ را می‌توان با کاشی $1 \times k$ فرش کرد اگر و تنها اگر $k \mid m$ یا $k \mid n$.

سوی آسان. اگر $k \mid m$، هر ستون — که $m$ خانه دارد — با کاشی‌های عمودی پر می‌شود؛ ستون‌به‌ستون، تمام. (اگر $k \mid n$، همین کار با سطرها.)

سوی سخت. فرض کنید $k$ نه $m$ را می‌شمارد و نه $n$ را. همان کارِ قبل را با $k$ به‌جای ۴ می‌کنیم: این بار $\omega$ نخستین ریشهٔ $k$-اُم واحد پس از ۱ است (برای $k = 4$ همان $\omega$ی قبلی) — اندازهٔ ۱ و زاویهٔ $\tfrac{2\pi}{k}$ — و خانهٔ $(r, c)$ را با $\omega^{\,r+c}$ وزن بدهید. مثل قبل، هر کاشی جمعِ $\omega^{\,j}\left(1 + \omega + \cdots + \omega^{k-1}\right) = 0$ دارد و جمعِ کل تجزیه می‌شود:

$$\sum_{r=1}^{m}\sum_{c=1}^{n} \omega^{\,r+c} = \left(\sum_{r=1}^{m} \omega^{\,r}\right)\left(\sum_{c=1}^{n} \omega^{\,c}\right)$$

حالا مهرهٔ اصلی. جمعِ توان‌های $\omega$ یک تصاعد هندسی با نسبتِ $\omega \neq 1$ است:

$$\sum_{r=1}^{m} \omega^{\,r} = \omega\cdot\frac{\omega^{\,m} - 1}{\omega - 1} \qquad\Longrightarrow\qquad \sum_{r=1}^{m} \omega^{\,r} = 0 \iff \omega^{\,m} = 1 \iff k \mid m$$

(تساویِ $\omega^{\,m} = 1$ دقیقاً وقتی برقرار است که $m$ مضربِ $k$ باشد — همان بحثِ زاویه‌ها در برگهٔ ریشه‌های واحد.) پس اگر $k \nmid m$ و $k \nmid n$، هر دو عامل ناصفرند، جمعِ کل ناصفر است و کاشی‌کاری ناممکن. مسئلهٔ $10 \times 10$ ما حالتِ $k = 4$ بود: $4 \nmid 10$.

برای خوانندهٔ کنجکاو بگوییم که راهِ بی‌اعدادِ مختلط هم هست: با همان رنگ‌آمیزیِ قطریِ $k$-رنگی می‌توان نوارهای $k$ سطری و $k$ ستونی را — که خودشان به‌سادگی فرش می‌شوند — از دو طرف کند و مسئله را به مستطیلِ کوچکِ $a \times b$ با $1 \le a, b \le k-1$ رساند؛ آن‌جا شمردنِ دو کلاسِ رنگیِ مناسب نشان می‌دهد که توازن برقرار نمی‌شود. استدلالِ درستی است، اما رنگِ درست را باید حدس زد و چند حالت را جداجدا وارسی کرد.

---

وزن‌دهی فقط «نه» نمی‌گوید؛ حساب هم می‌کند

تا این‌جا ریشه‌های واحد در نقشِ مانع ظاهر شدند. مسئلهٔ بعدی نشان می‌دهد که از همین وزن‌دهی، جوابِ کامل هم بیرون می‌آید.

مسئله. از صفحهٔ $8 \times 8$ یک خانه — خانهٔ $(a, b)$ — را برمی‌داریم. به ازای کدام خانه‌ها می‌توان ۶۳ خانهٔ باقی‌مانده را با ۲۱ کاشیِ $1 \times 3$ فرش کرد؟

این بار کاشی سه‌خانه‌ای است، پس $k = 3$: $\omega$ را نخستین ریشهٔ سومِ واحد پس از ۱ می‌گیریم — زاویهٔ $\tfrac{2\pi}{3}$ یا ۱۲۰ درجه — و مثل قبل وزن می‌دهیم: $w(r, c) = \omega^{\,r+c}$. هر کاشی جمعِ صفر دارد (چون $1 + \omega + \omega^2 = 0$) و جمعِ صفحهٔ کامل:

$$\sum_{r,\,c} \omega^{\,r+c} = \left(\sum_{r=1}^{8} \omega^{\,r}\right)^{2} = \left(\omega^7 + \omega^8\right)^2 = \left(\omega + \omega^2\right)^2 = (-1)^2 = 1$$

(شش توانِ نخست در دو دورِ کامل صفر شدند؛ $\omega^7 = \omega$ و $\omega^8 = \omega^2$؛ و $\omega + \omega^2 = -1$، چون جمعِ هر سه ریشه صفر است.)

حالا اگر صفحهٔ بدونِ خانهٔ $(a, b)$ فرش شود، جمعِ وزن‌هایش باید صفر باشد؛ یعنی:

$$1 - \omega^{\,a+b} = 0 \qquad\Longleftrightarrow\qquad 3 \mid a + b$$

این شرط از ۶۴ خانه، ۲۲ خانهٔ نامزد باقی می‌گذارد. خوب است، ولی هنوز جوابِ نهایی نیست.

پیش از ادامه، حدس بزنید. یک وزن‌دهی، یک معادله داد: $3 \mid a + b$. آیا همهٔ ۲۲ نامزد واقعاً شدنی‌اند؟ اگر نه، معادلهٔ دوم را از کجا می‌شود آورد؟ راهنمایی: وزن‌دهیِ ما به چیزی از صفحه بی‌اعتنا ماند؛ به شکلِ وزن‌ها دوباره نگاه کنید.

قطرِ دیگر: وزنِ $\omega^{\,r-c}$

رنگ‌آمیزیِ ما روی قطرهای یک جهت ثابت بود؛ صفحه اما قطرهایی در جهتِ دیگر هم دارد و دلیلی ندارد آن‌ها را مفت از دست بدهیم. وزنِ تازه: $w(r, c) = \omega^{\,r-c}$.

هر کاشی باز هم صفر جمع می‌زند. عمودی‌اش روشن است:

$$\omega^{\,r-c}\left(1 + \omega + \omega^2\right) = 0$$

و افقی‌اش هم، چون این بار توان‌ها پایین می‌روند:

$$\omega^{\,r-c} + \omega^{\,r-c-1} + \omega^{\,r-c-2} = \omega^{\,r-c-2}\left(\omega^2 + \omega + 1\right) = 0$$

جمعِ صفحهٔ کامل با این وزن هم ۱ است: جمع به $\left(\sum \omega^{\,r}\right)\left(\sum \omega^{\,-c}\right)$ تجزیه می‌شود و عاملِ دوم مزدوجِ عاملِ قبلی است؛ یعنی $(-1) \times (-1) = 1$. پس همان استدلال، معادلهٔ دوم را می‌دهد:

$$3 \mid a - b$$

ترکیبِ دو معادله. از $3 \mid a + b$ و $3 \mid a - b$ نتیجه می‌شود $3 \mid 2a$ و $3 \mid 2b$؛ و چون ۲ و ۳ نسبت به هم اول‌اند، $3 \mid a$ و $3 \mid b$. روی صفحهٔ $8 \times 8$ یعنی $a, b \in \lbrace 3, 6 \rbrace$؛ فقط چهار خانه:

$$(3, 3), \qquad (3, 6), \qquad (6, 3), \qquad (6, 6)$$

---

و حالا ساختن

دو معادله گفتند «جز این چهار خانه، هیچ»؛ اما هنوز باید نشان دهیم این چهارتا واقعاً شدنی‌اند. تقارن، کار را یک‌چهارم می‌کند: بازتاب‌های افقی و عمودیِ صفحه این چهار خانه را به هم می‌برند؛ پس کافی است سوراخِ $(3, 3)$ را فرش کنیم. و این هم فرش:

۲۱ کاشیِ $1 \times 3$ و خانهٔ خالیِ $(3, 3)$ با علامتِ ×؛ کاشی‌های افقی خاکستری‌اند و عمودی‌ها سفید.

پس جوابِ نهایی:

صفحهٔ $8 \times 8$ منهای خانهٔ $(a, b)$ دقیقاً وقتی با کاشی $1 \times 3$ فرش می‌شود که هر دو مختصات مضربِ ۳ باشند.

به عقب برگردید و ببینید چه شد: دو جای‌گذاری، دو معادله؛ و دو معادله، محاصرهٔ کاملِ جواب. رنگ‌آمیزی‌ها معمولاً فقط امتناع نشان می‌دهند؛ این‌جا وزن‌دهی، مجموعهٔ جواب را محاسبه کرد.

---

پشتِ پرده: زبانِ چندجمله‌ای‌ها

تا این‌جا وزن‌ها را برداشتیم و کار کردند. اما چرا این وزن‌ها؟ و چرا ریشهٔ واحد؟ همان ترجمه‌ای که در مسئلهٔ تاس‌ها دیدیم جواب را می‌دهد: چندجمله‌ای‌ها.

۱. هر خانه، یک تک‌جمله‌ای. به خانهٔ $(r, c)$ تک‌جمله‌ایِ $x^{r} y^{c}$ را نسبت می‌دهیم — سطر در توانِ $x$، ستون در توانِ $y$. آن‌گاه هر مجموعه‌ای از خانه‌ها یک چندجمله‌ای می‌شود: کافی است تک‌جمله‌ای‌های خانه‌هایش را جمع بزنیم. مثلاً کلِ صفحهٔ $m \times n$:

$$B(x, y) = \sum_{r=1}^{m} \sum_{c=1}^{n} x^{r} y^{c}$$

۲. هر کاشی، مضربی از یک چندجمله‌ایِ ثابت. کاشیِ افقیِ $1 \times 3$ که از خانهٔ $(r, c)$ شروع می‌شود، سه خانهٔ $(r, c), (r, c+1), (r, c+2)$ را می‌پوشاند، پس چندجمله‌ای‌اش

$$x^{r} y^{c} + x^{r} y^{c+1} + x^{r} y^{c+2} = x^{r} y^{c}\left(1 + y + y^2\right)$$

است، و کاشیِ عمودی به همین ترتیب $x^{r} y^{c}\left(1 + x + x^2\right)$. نکته این است که کاشی هر جا بنشیند، فقط تک‌جمله‌ایِ جلوی پرانتز عوض می‌شود؛ پرانتز همیشه همان است. این دو پرانتز را چندجمله‌ایِ کاشی می‌نامیم.

۳. کاشی‌کاری، یک تساوی. اگر صفحه با این کاشی‌ها فرش شود، چندجمله‌ایِ صفحه دقیقاً جمعِ چندجمله‌ایِ کاشی‌هاست:

$$B(x, y) = \sum_{t} x^{r_t} y^{c_t}\left(1 + y + y^2\right) \;+\; \sum_{s} x^{r_s} y^{c_s}\left(1 + x + x^2\right)$$

جمعِ اول روی کاشی‌های افقی است و جمعِ دوم روی عمودی‌ها؛ $(r_t, c_t)$ هم خانهٔ شروعِ آن کاشی.

۴. حالا جای‌گذاری. فرض کنید دو عددِ $u$ و $v$ را طوری پیدا کنیم که هر دو پرانتز صفر شوند، یعنی $1 + u + u^2 = 0$ و $1 + v + v^2 = 0$. با گذاشتنِ $x = u$ و $y = v$، سمتِ راستِ تساویِ بالا تمامش صفر می‌شود — هر چند تا کاشی که باشد، هر جا که باشند. پس

$$B(u, v) = 0$$

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

۵. آن عددها همان ریشه‌های واحدند. ریشه‌های $1 + t + t^2$ کدام‌اند؟ چون $(t - 1)(1 + t + t^2) = t^3 - 1$، هر ریشهٔ سومِ واحد به‌جز خودِ ۱ در آن صدق می‌کند: $\omega$ و $\omega^2$. برای کاشیِ $1 \times k$ هم همین‌طور: ریشه‌های $1 + t + \cdots + t^{k-1}$ دقیقاً ریشه‌های $k$-اُم واحدند به‌جز ۱. پس ریشه‌های واحد از آسمان نیفتادند؛ آن‌ها ریشه‌های چندجمله‌ایِ کاشی‌اند.

۶. و وزن‌دهی، همان جای‌گذاری است. وزنی که به خانهٔ $(r, c)$ دادیم چیزی نبود جز مقدارِ تک‌جمله‌ای‌اش در نقطهٔ جای‌گذاری: $u^{r} v^{c}$. پس «جمعِ وزن‌های صفحه» همان $B(u, v)$ است، و «جمعِ وزن‌های هر کاشی صفر است» همان صفر شدنِ چندجمله‌ایِ کاشی. دو وزن‌دهیِ ما هم دو انتخابِ $(u, v)$ بودند:

• با $u = v = \omega$: وزنِ خانه $\omega^{\,r} \omega^{\,c} = \omega^{\,r+c}$ — وزن‌دهیِ قطرِ اول.
• با $u = \omega$ و $v = \omega^2$: وزنِ خانه $\omega^{\,r} \omega^{\,2c} = \omega^{\,r-c}$، چون $\omega^{3} = 1$ — وزن‌دهیِ قطرِ دوم.

۷. یک وارسی. صفحهٔ $8 \times 8$ منهای خانهٔ $(a, b)$ چندجمله‌ای‌اش $\left(\sum_{r} x^{r}\right)\left(\sum_{c} y^{c}\right) - x^{a} y^{b}$ است. جای‌گذاریِ $x = y = \omega$ همان $1 - \omega^{\,a+b} = 0$ را می‌دهد — دقیقاً معادلهٔ اولی که پیدا کردیم.

و یک پاداش: در مسئلهٔ $1 \times 4$، عددِ $-1$ هم ریشهٔ $1 + t + t^2 + t^3$ است. جای‌گذاریِ $x = y = -1$ یعنی وزنِ $(-1)^{\,r+c}$ — که چیزی نیست جز همان رنگ‌آمیزیِ شطرنجی! پس آن تلاشِ اولِ ما هم یکی از همین جای‌گذاری‌ها بود؛ فقط معادله‌ای که داد $0 = 0$ از آب درآمد. سه ریشهٔ دیگر، سه معادلهٔ دیگر — و یکی از آن‌ها همان بود که کار را تمام کرد.

هر جای‌گذاری در ریشهٔ چندجمله‌ایِ کاشی، یک معادله از صفحه بیرون می‌کشد؛ رنگ‌آمیزی و وزن‌دهی دو روایت از یک ایده‌اند — یکی را می‌بینیم، دیگری را حساب می‌کنیم.

---

تمرین‌ها

تمرین. آیا صفحهٔ $6 \times 6$ با کاشی $1 \times 4$ فرش می‌شود؟ اول همان بررسی‌های اولیه — مساحت و رنگِ شطرنجی — را امتحان کنید؛ بعد سراغِ وزن‌دهی بروید.

پاسخ

مساحت: $36 = 4 \times 9$، بی‌اعتراض؛ رنگِ شطرنجی: ۱۸ سیاه و ۱۸ سفید، باز هم بی‌اعتراض. اما با وزنِ $\omega^{\,r+c}$ (همان ریشهٔ چهارمِ واحد): از شش توان، چهارتای نخست یک دورِ کامل‌اند و می‌ماند $\omega^5 + \omega^6 = \omega + \omega^2 = i - 1$؛ پس جمعِ کل $(i-1)^2 = -2i \neq 0$ است و فرش‌کردن ناممکن. (با قضیهٔ دِ بروین هم یک‌خطی است: $4 \nmid 6$.)

یک قدم فراتر. از صفحهٔ $10 \times 10$ خانهٔ $(a, b)$ را برمی‌داریم. به ازای کدام خانه‌ها باقی‌مانده با کاشی $1 \times 3$ فرش می‌شود؟ جواب را حدس نزنید: این بار مضرب‌های ۳ نیستند!

پاسخ

این بار $\sum_{r=1}^{10} \omega^{\,r} = \omega^{10} = \omega$ است (نُه توانِ نخست، سه دورِ کامل‌اند). پس جمعِ صفحهٔ کامل با وزنِ $\omega^{\,r+c}$ برابر $\omega^2$ است و شرطِ فرش‌شدن، $\omega^{\,a+b} = \omega^2$ یعنی $a + b \equiv 2 \pmod{3}$؛ و با وزنِ $\omega^{\,r-c}$، جمعِ کل $\omega \cdot \omega^2 = 1$ است و شرطِ دوم $a \equiv b \pmod{3}$. از این دو، $2a \equiv 2$ و در نتیجه:

$$a \equiv b \equiv 1 \pmod{3}$$

یعنی دقیقاً ۱۶ خانه با $a, b \in \lbrace 1, 4, 7, 10 \rbrace$. ساختن هم این بار آسان‌تر از $8 \times 8$ است: بالا و پایینِ سطرِ سوراخ به‌ترتیب $a - 1$ و $10 - a$ سطرِ کامل‌اند — هر دو مضربِ ۳ — که ستون‌به‌ستون با کاشی‌های عمودی پر می‌شوند؛ و در خودِ آن سطر، سمتِ چپِ سوراخ $b - 1$ خانه و سمتِ راستش $10 - b$ خانه است — باز هم مضربِ ۳ — که با کاشی‌های افقی پر می‌شوند.