: رنگ آمیزی و همخوانیI

کاربر Online

1194 کاربر online

تفاوت با نگارش: 2

Lines: 1-136

Lines: 1-133

||V{maketoc}||

||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ��ی��ی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||

||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ک��مپیو�� رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||

^@#16:

!رنگ آمیزی

در سال 1961 فیزیکدان نظری ،ام . ا . فیشر اهل انگلیس، مسأله‌ای معروف و بسیار فکربرانگیز را حل کرد. صورت آن مسأله این بود که به چند طریق می‌توان صفحةی شطرنج {TEX()} {8\times 8} {TEX}را به وسیلة دومینوها (قطعات مستطیل شکل {TEX()} {2\times 1} {TEX}) پوشاند؟
او نشان داداین کار را به{TEX()} {2^4\times 901^2} {TEX} یا 12988816 راه مختلف می‌توان انجام داد. حال فرض کنید دو خانة گوشه‌ای و متقابل (قطری) صفحه شطرنج را حذف کرده‌ایم، به نظر شما صفحة باقیمانده را که از 62 مربع واحد تشکیل شده به چند طریق می‌توان توسط 31 دومینو پوشاند؟

در سال 1961 فیزیکدان نظری ،ام . ا . فیشر اهل انگلیس، مسأله‌ای معروف و بسیار فکربرانگیز را حل کرد. صورت آن مسأله این بود که به چند طریق می‌توان صفحهی شطرنج {TEX()} {8\times 8} {TEX}را به وسیله دومینوها (قطعات مستطیل شکل {TEX()} {2\times 1} {TEX}) پوشاند؟
او نشان داداین کار را به{TEX()} {2^4\times 901^2} {TEX} یا 12988816 راه مختلف می‌توان انجام داد. حال فرض کنید دو خانه گوشه‌ای و متقابل (قطری) صفحه شطرنج را حذف کرده‌ایم، به نظر شما صفحه باقیمانده را که از 62 مربع واحد تشکیل شده به چند طریق می‌توان توسط 31 دومینو پوشاند؟

این نکته را یادآور می‌شویم که پوشاندن به این معناست که هیچ خانه‌ای خالی نباشد و در ضمن دومینوها روی هم نیفتاده باشند.

به نظر می‌رسد که این مسأله از مسأله‌ای که ((فیشر)) حل کرده سخت‌تر باشد، اما این طور نیست. جواب مسأله خیلی بدیهی است البته با کمک رنگ‌های خود صفحة شطرنج !
جواب مسأله عدد صفر است، به بیان روشن‌تر پوشاندن صفحة مذکور به وسیلة 31 دومینو غیرممکن است زیرا فرض کنید این صفحه را به وسیلة 31 دومینو بتوان پوشاند، بدیهی است که هر دومینوی قرار داده شده در صفحه یک خانة سفید و یک خانة سیاه را پوشانده است، به این ترتیب در صفحة مذکور 31 خانة سفید و 31 خانة سیاه داریم ولی این مطلب درست نیست، زیرا صفحة مذکور از حذف دو خانه گوشه‌ای و متقابل صفحة شطرنج حاصل شده و همان‌طور که می‌دانید این دو خانه حتماً همرنگ هستند و در نتیجه تعداد خانه‌های سفید و سیاه صفحة مذکور دو واحد با هم اختلاف دارند. پس با توجه به تناقض موجود اصلاً نمی‌توان صفحة ذکر شده را به وسیلة دومینوها پوشاند. اکثر مسائلی که در این قسمت مطرح می‌شوند مسائلی هستند که جواب منفی دارند و نحوة اثبات آنها به وسیلة ایده‌های هوشمندانة رنگ‌آمیزی و زوجیت است. در مسأله‌ای که لحظاتی پیش به آن جواب دادیم از دو رنگ استفاده کردیم ولی اکثراً به بیش از دو رنگ نیاز داریم.
برای آنکه بیشتر به نحوة اثبات با این ایده پی ببرید نخست باید با اصل همخوانی آشنا شوید:

به نظر می‌رسد که این مسأله از مسأله‌ای که ((فیشر)) حل کرده سخت‌تر باشد، اما این طور نیست. جواب مسأله خیلی بدیهی است البته با کمک رنگ‌های خود صفحه شطرنج !
جواب مسأله عدد صفر است، به بیان روشن‌تر پوشاندن صفحه مذکور به وسیله 31 دومینو غیرممکن است زیرا فرض کنید این صفحه را به وسیله 31 دومینو بتوان پوشاند، بدیهی است که هر دومینوی قرار داده شده در صفحه یک خانه سفید و یک خانه سیاه را پوشانده است، به این ترتیب در صفحه مذکور 31 خانه سفید و 31 خانه سیاه داریم ولی این مطلب درست نیست، زیرا صفحه مذکور از حذف دو خانه گوشه‌ای و متقابل صفحه شطرنج حاصل شده و همان‌طور که می‌دانید این دو خانه حتماً همرنگ هستند و در نتیجه تعداد خانه‌های سفید و سیاه صفحه مذکور دو واحد با هم اختلاف دارند. پس با توجه به تناقض موجود اصلاً نمی‌توان صفحه ذکر شده را به وسیله دومینوها پوشاند. اکثر مسائلی که در این قسمت مطرح می‌شوند مسائلی هستند که جواب منفی دارند و نحوه اثبات آنها به وسیله ایده‌های هوشمندانه رنگ‌آمیزی و زوجیت است. در مسأله‌ای که لحظاتی پیش به آن جواب دادیم از دو رنگ استفاده کردیم ولی اکثراً به بیش از دو رنگ نیاز داریم.
برای آنکه بیشتر به نحوه اثبات با این ایده پی ببرید نخست باید با اصل همخوانی آشنا شوید:

---

!اصل همخوانی{TEX()} { (Parity)} {TEX}

@#16:

به کمک آزمون همخوانی می‌توان عدم وجود شیء یا اشیاء واجد ویژگی‌های خاص یا عدم امکان انجام اعمال خاصی را ثابت کرد. معمولا در این روش از زوج یا فرد بودن ،از مساوی بودن تعداد اشیاء موجود، از دو رنگ متفاوت یا ترکیبی از این‌ها استفاده می‌شود.

---

!!پوشش کامل یک صفحه شطرنجی به وسیله دومینوها

فرض کنید یک صفحة {TEX()} {m\times n} {TEX}داریم که از {TEX()} {m\cdot n} {TEX}مربع متساوی تشکیل شده است. مربع‌ها در {TEX()} {m} {TEX}سطر و {TEX()} {n} {TEX}ستون قرار دارند. گاهی اوقات برای حل مسئله‌ای خاص لازم می‌شود که خانه‌های این شبکه را یک در میان، سفید {TEX()} {(W)} {TEX}و سیاه {TEX()} {(B)} {TEX} در نظر بگیریم.

فرض کنید یک صفحه {TEX()} {m\times n} {TEX}داریم که از {TEX()} {m\cdot n} {TEX}مربع متساوی تشکیل شده است. مربع‌ها در {TEX()} {m} {TEX}سطر و {TEX()} {n} {TEX}ستون قرار دارند. گاهی اوقات برای حل مسئله‌ای خاص لازم می‌شود که خانه‌های این شبکه را یک در میان، سفید {TEX()} {(W)} {TEX}و سیاه {TEX()} {(B)} {TEX} در نظر بگیریم.

منظور از یک دومینو یک مستطیل {TEX()} {1\times 2} {TEX}است که در شکل زیر ملاحظه می‌کنید. مثلاً اگر بتوان یک صفحه شطرنجی را با تعدادی دومینو، بدون اینکه دومینوها روی هم قرار گیرند، به طور کامل پوشاند گوییم آن صفحه شطرنجی دارای یک پوشش کامل بوسیله دومینوها است.

::{picture=img/daneshnameh_up/b/bd/com0041a.jpg}::

---

!!مثال

نشان دهید اگر {TEX()} {n,m} {TEX}فرد باشند یک صفحه شطرنجی {TEX()} {m\times n} {TEX}دارای یک پوشش کامل بوسیله دومینوها نیست.

__حل __

تعداد مربع‌های صفحة شطرنجی {TEX()} {m\times n} {TEX}که {TEX()} {n,m} {TEX}فرد هستند عددی فرد است. چون هر تعداد از دومینوها را که در نظر بگیریم تعداد زوج خواهد بود، پس نمی‌توان این صفحة{TEX()} {m\times n} {TEX}را با دومینوها پوشاند. در اینجا از ویژگی زوجیت استفاده کردیم.

تعداد مربع‌های صفحه شطرنجی {TEX()} {m\times n} {TEX}که {TEX()} {n,m} {TEX}فرد هستند عددی فرد است. چون هر تعداد از دومینوها را که در نظر بگیریم تعداد زوج خواهد بود، پس نمی‌توان این صفحه{TEX()} {m\times n} {TEX}را با دومینوها پوشاند. در اینجا از ویژگی زوجیت استفاده کردیم.

از این مسأله نتیجه می‌گیریم که برای پوشش کامل یک صفحه شطرنجی {TEX()} {m\times n} {TEX}بوسیله دومینوها لازم است {TEX()} {m} {TEX}ضرب در {TEX()} {n} {TEX}زوج باشد.

این مثال را می‌توان با روش دیگری هم بررسی کرد:

@#16:

اگر خانه‌های این صفحه را یک در میان سیاه و سفید فرض کنیم برای {TEX()} {m\cdot n} {TEX}فرد تعداد خانه‌های سیاه و سفید برابر نمی‌باشد ولی هر دومینو به هر نحوی که قرار گیرد یک خانه سیاه و یک خانه سفید را خواهد پوشاند. و چون تعداد خانه‌های سفید و سیاه این صفحه با هم برابر نمی‌باشند، نمی‌توان این صفحه را به طور کامل پوشاند. در این حل از روش شطرنجی کردن استفاده کردیم.

!!مثال

یک صفحه مشبک {TEX()} {8\times 8} {TEX}موجود است، به قسمی که خانه‌های گوشه‌ای متقابل آن، مطابق شکل 1، حذف شده‌اند. (در شکل فوق {TEX()} {B} {TEX}نشان‌دهندة خانه مشکی و{TEX()} {W} {TEX}نشان‌دهندة خانة سفید می‌باشد.)

یک صفحه مشبک {TEX()} {8\times 8} {TEX}موجود است، به قسمی که خانه‌های گوشه‌ای متقابل آن، مطابق شکل 1، حذف شده‌اند. (در شکل فوق {TEX()} {B} {TEX}نشان‌دهنده خانه مشکی و{TEX()} {W} {TEX}نشان‌دهنده خانه سفید می‌باشد.)

::{picture=img/daneshnameh_up/4/4e/com0041b.jpg}::

تعدادی دومینو در دست می‌باشد. آیا می‌توان صفحه فوق را به طور کامل با دومینوها پوشاند. (یعنی یک پوشش کامل را بوسیله دومینوها داشته باشیم. به تعریف پوشش کامل توسط دومینوها توجه کنید.)

__حل __

این کار نشدنی است، زیرا هر دومینو یک خانه سیاه و یک خانه سفید را می‌پوشاند. بنابراین {TEX()} {n} {TEX}عدد دومینو {TEX()} {n} {TEX}عدد خانه سیاه و {TEX()} {n} {TEX}عدد خانه سفید را خواهند پوشاند، یعنی از هر کدام به عدد مساوی. اما صفحة مسأله ما تعداد بیشتری خانه سیاه نسبت به سفید دارد. پس نمی‌توان آن را با دومینوها پوشاند. تعمیم دومینو یا 2مربعی، چند مربعی است و قضایای ما را درباره چند مربعی‌های سادة شکل زیر می‌باشد.

این کار نشدنی است، زیرا هر دومینو یک خانه سیاه و یک خانه سفید را می‌پوشاند. بنابراین {TEX()} {n} {TEX}عدد دومینو {TEX()} {n} {TEX}عدد خانه سیاه و {TEX()} {n} {TEX}عدد خانه سفید را خواهند پوشاند، یعنی از هر کدام به عدد مساوی. اما صفحه مسأله ما تعداد بیشتری خانه سیاه نسبت به سفید دارد. پس نمی‌توان آن را با دومینوها پوشاند. تعمیم دومینو یا 2مربعی، چند مربعی است و قضایای ما را درباره چند مربعی‌های ساده شکل زیر می‌باشد.

::{picture=img/daneshnameh_up/3/34/com0041c.jpg}::

به طور دقیق یک {TEX()} {n} {TEX}مربعی یک مجموعة مرتبط (همبند) از {TEX()} {n} {TEX}مربع واحد صفحه مشبک است، به گونه‌ای که اگر یک رخ در هر خانه از آن قرار بگیرد قادر باشد با تعداد متناهی حرکت بر روی صفحه به هر مربع آن برود. برای مثال شکل زیر نمی‌تواند یک سه مربعی باشد.

به طور دقیق یک {TEX()} {n} {TEX}مربعی یک مجموعه مرتبط (همبند) از {TEX()} {n} {TEX}مربع واحد صفحه مشبک است، به گونه‌ای که اگر یک رخ در هر خانه از آن قرار بگیرد قادر باشد با تعداد متناهی حرکت بر روی صفحه به هر مربع آن برود. برای مثال شکل زیر نمی‌تواند یک سه مربعی باشد.

::{picture=img/daneshnameh_up/c/c3/com0041d.jpg}::

@#16:

ابتدا 3 – مربعی ها را در نظر می‌گیریم. آشکار است که نمی‌توان صفحه {TEX()} {8\times 8} {TEX}را با 3- مربعی پوشاند، زیرا 64 بر 3 بخش‌پذیر نیست. در عوض سعی می‌کنیم صفحه شطرنج را با 21 عدد 3- مربعی و یک عدد یک مربعی بپوشانیم.

---

!!مثال

آیا پوشاندن صفحة شطرنج با 21 عدد 3- مربعی راست و یک عدد 1- مربعی در گوشة سمت چپ بالای آن قرار داده شده ممکن است؟ اگر جواب منفی است یک پوشش برای آن بیان کنید.

آیا پوشاندن صفحه شطرنج با 21 عدد 3- مربعی راست و یک عدد 1- مربعی در گوشه سمت چپ بالای آن قرار داده شده ممکن است؟ اگر جواب منفی است یک پوشش برای آن بیان کنید.

سه مربعی راست:

::{picture=img/daneshnameh_up/8/86/com0041e.jpg}::

__حل __

برای اثبات این مطلب صفحه را با سه رنگ {TEX()} { c , b, a } {TEX} مانند شکل زیر رنگ می‌کنیم.

::{picture=img/daneshnameh_up/9/95/com0041f.jpg}::

می‌بینید که 21 مربعی با رنگ {TEX()} {a} {TEX}، 22 مربع با رنگ {TEX()} {b} {TEX}و 21 مربع با رنگ {TEX()} {c} {TEX}به چشم می‌خورد. هر 3- مربعی که در این صفحه قرار می‌گیرد، یک {TEX()} {-a} {TEX} مربع و یک{TEX()} {-b} {TEX}مربع و یک {TEX()} {-c} {TEX} مربع را می‌پوشاند. پس این 3 - مربعی‌ها همیشه تعداد مساوی خانه از هر کدام از این سه رنگ را می‌پوشانند. اما گوشة سمت چپ بالا یک {TEX()} {-a} {TEX}مربع است و با پوشاندن آن با یک 1- مربعی ،20 عدد {TEX()} {-a} {TEX} مربع باقی می‌ماند، اما 20 عدد {TEX()} {-b} {TEX}مربع و 21 عدد{TEX()} {-c} {TEX}مربع خواهیم داشت. این اعداد نامساوی‌اند، پس چنین پوششی غیرممکن است.

می‌بینید که 21 مربعی با رنگ {TEX()} {a} {TEX}، 22 مربع با رنگ {TEX()} {b} {TEX}و 21 مربع با رنگ {TEX()} {c} {TEX}به چشم می‌خورد. هر 3- مربعی که در این صفحه قرار می‌گیرد، یک {TEX()} {-a} {TEX} مربع و یک{TEX()} {-b} {TEX}مربع و یک {TEX()} {-c} {TEX} مربع را می‌پوشاند. پس این 3 - مربعی‌ها همیشه تعداد مساوی خانه از هر کدام از این سه رنگ را می‌پوشانند. اما گوشه سمت چپ بالا یک {TEX()} {-a} {TEX}مربع است و با پوشاندن آن با یک 1- مربعی ،20 عدد {TEX()} {-a} {TEX} مربع باقی می‌ماند، اما 20 عدد {TEX()} {-b} {TEX}مربع و 21 عدد{TEX()} {-c} {TEX}مربع خواهیم داشت. این اعداد نامساوی‌اند، پس چنین پوششی غیرممکن است.

پس ما نتیجه می‌گیریم 1- مربعی باید روی یک{TEX()} {-b} {TEX}مربع باشد.

حال فرض می‌کنیم 1- مربعی روی یک{TEX()} {-b} {TEX}مربع قرار گرفته باشد، برای مثال گوشه سمت چپ پایین. با در نظر گرفتن تقارن نسبت به محور {TEX()} {x} {TEX}در می‌یابیم که این حالت، شبیه همان حالتی است که 1- مربعی روی گوشة سمت چپ بالایی بود و چنین پوششی غیرممکن می‌باشد. در حقیقت مکان‌های ممکن برای جای‌گذاری 1- مربعی، فقط {TEX()} {-b} {TEX}مربع‌های هستند که نسبت به {TEX()} {-b} {TEX} مربع‌های دیگر متقارن‌اند. این مربع‌ها چهار مربع سیاه شکل زیر هستند. شکل زیر نشان می‌دهد که اگر 1- مربعی روی یکی از این 4 مربع باشد بقیه صفحه را می‌توان با 3- مربعی‌های راست پوشاند.

حال فرض می‌کنیم 1- مربعی روی یک{TEX()} {-b} {TEX}مربع قرار گرفته باشد، برای مثال گوشه سمت چپ پایین. با در نظر گرفتن تقارن نسبت به محور {TEX()} {x} {TEX}در می‌یابیم که این حالت، شبیه همان حالتی است که 1- مربعی روی گوشه سمت چپ بالایی بود و چنین پوششی غیرممکن می‌باشد. در حقیقت مکان‌های ممکن برای جای‌گذاری 1- مربعی، فقط {TEX()} {-b} {TEX}مربع‌های هستند که نسبت به {TEX()} {-b} {TEX} مربع‌های دیگر متقارن‌اند. این مربع‌ها چهار مربع سیاه شکل زیر هستند. شکل زیر نشان می‌دهد که اگر 1- مربعی روی یکی از این 4 مربع باشد بقیه صفحه را می‌توان با 3- مربعی‌های راست پوشاند.

::{picture=img/daneshnameh_up/9/9c/com0041g.jpg}::

---

!نتیجه

@#16:

شرط لازم و کافی برای این که صفحه شطرنج به وسیله 21 عدد 3- مربعی راست و یک عدد 1-مربعی پوشانده شود، این است که 1- مربعی در یکی از چهارخانه سیاه شکل بالا باشد.

شکل زیر یک نمونه از پوشش صفحه این مثال را نشان می‌دهد. (مستطیل‌ها مربع فرض شود)

::{picture=img/daneshnameh_up/c/c5/com0041h.jpg}::

---

!!مثال

بدون توجه به این که یک، 1- مربعی در کجای صفحه شطرنج قرار گرفته، بقیه خانه‌ها را همیشه می‌توان بوسیله 21 عدد 3- مربعی قائمه پوشاند.

سه مربعی قائمه :

::{picture=img/daneshnameh_up/9/9e/com0041i.jpg}::

البته حکم فوق در مورد صفحه {TEX()} {2^n\times 2^n} {TEX}درست است و اثبات به وسیله استقرا روی {TEX()} {n} {TEX}است. این مسئله برای یک صفحه {TEX()} {2\times 2} {TEX}بدیهی است.

::{picture=img/daneshnameh_up/7/71/com0041j.jpg}::

یک صفحه{TEX()} {4\times 4} {TEX}را در نظر می‌گیریم. آن را به چهار مربع مطابق شکل زیر تقسیم می‌کنیم. فرض کنید 1-مربعی در یکی از چهار ربع باشد مثلاً‌ در ربع سوم . هر یک از ربع‌ها یک صفحه {TEX()} {2\times 2} {TEX}است و ما می‌توانیم 1- مربعی را در هر ربع قرار دهیم و بقیه را با 3-مربعی قائمه بپوشانیم. در ربع سوم قبلاً‌ 1-مربعی قرار گرفته است، در سه ربع دیگر -1 مربعی‌ها را در مرکز قرار می‌دهیم. آنگاه می‌توان این 3 عدد 1- مربعی مرکزی را با یک 3- مربعی قائمه عوض کنیم. بنابراین صفحة {TEX()} {4\times 4} {TEX}را با یک 1- مربعی در یک مکان دلخواه و 5 تا 3-مربعی قائمه پوشانده‌ایم.

یک صفحه{TEX()} {4\times 4} {TEX}را در نظر می‌گیریم. آن را به چهار مربع مطابق شکل زیر تقسیم می‌کنیم. فرض کنید 1-مربعی در یکی از چهار ربع باشد مثلاً‌ در ربع سوم . هر یک از ربع‌ها یک صفحه {TEX()} {2\times 2} {TEX}است و ما می‌توانیم 1- مربعی را در هر ربع قرار دهیم و بقیه را با 3-مربعی قائمه بپوشانیم. در ربع سوم قبلاً‌ 1-مربعی قرار گرفته است، در سه ربع دیگر -1 مربعی‌ها را در مرکز قرار می‌دهیم. آنگاه می‌توان این 3 عدد 1- مربعی مرکزی را با یک 3- مربعی قائمه عوض کنیم. بنابراین صفحه {TEX()} {4\times 4} {TEX}را با یک 1- مربعی در یک مکان دلخواه و 5 تا 3-مربعی قائمه پوشانده‌ایم.

::{picture=img/daneshnameh_up/b/b3/com0041k.jpg}::

حالت {TEX()} {8\times 8} {TEX}و همچنین حالت کلی به همین صورت استقرایی بحث می‌شود. در شکل زیر فرض کنیم 1- مربعی مثلاً در ربع دوم قرار بگیرد آنگاه ربع دوم خود یک مربع{TEX()} {4\times 4} {TEX}است که مطابق قبل می‌توان آن را پوشش داد و 1- مربعی ربع اول و سوم و چهارم هر کدام در گوشه قرار بگیرد و با هم تشکیل سه مربعی بدهند.

::{picture=img/daneshnameh_up/e/e9/com0041l.jpg}::

---

@#16:

!!مثال

یک صفحه شطرنجی {TEX()} {m} {TEX}در {TEX()} {n} {TEX}را در نظر بگیرید که در آن {TEX()} {m\cdot n} {TEX}فرد است، و فرض کن ید که مربع واقع در گوشة چپ و بالای آن سفید باشد. نشان دهید که اگر یک مربع سفید از این صفحه شطرنجی برداشته شود صفحه شطرنجی هرس شده دارای پوشش کامل به وسیله دومینوها است.

یک صفحه شطرنجی {TEX()} {m} {TEX}در {TEX()} {n} {TEX}را در نظر بگیرید که در آن {TEX()} {m\cdot n} {TEX}فرد است، و فرض کن ید که مربع واقع در گوشه چپ و بالای آن سفید باشد. نشان دهید که اگر یک مربع سفید از این صفحه شطرنجی برداشته شود صفحه شطرنجی هرس شده دارای پوشش کامل به وسیله دومینوها است.

__حل __

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

::{picture=img/daneshnameh_up/6/67/com0041m.jpg}::

ضمناً ردیف‌های بالا و پایین این ردیف دارای حاصل ضرب سطر و ستون زوج است و بنابر مثال 1 می‌توان آنها را با دومینوها پوشاند.

اما اگر مربع اول از سمت چپ مشکی باشد حداقل یک ردیف مربع در بالا و یک ردیف مربع در پایین آن وجود دارد. این سه ردیف را به صورت ذیل در نظر می‌گیریم که مثلاً خانه سفید هاشورزده شده برداشته شده است.

::{picture=img/daneshnameh_up/0/06/com0041n.jpg}::

چون خانة هاشورزده شده در ردیف وسط قرار دارد همواره می‌توان یک مربع {TEX()} {3\times 3} {TEX}، شامل 9 مربع، که مربع وسط هاشورزده باشد در نظر گرفت (مطابق شکل بالا) واضح است که این ((مربع‌)) {TEX()} {3\times 3} {TEX} هرس شده را می‌توان با دومینوها پوشاند. ردیف‌های دو طرف این مربع {TEX()} {3\times 3} {TEX}دارای ابعادی است که حاصل‌ضرب آنها زوج است و بنابر مثال 1 قابل پوشش کامل به وسیلة دومینوها هستند. ضمناً ردیف‌های بالا و پایین این سه ردیف به شرط وجود دارای ابعادی با حاصل‌ضرب زوج هستند و قابل پوشش کامل به وسیلة دومینوها هستند.

چون خانه هاشورزده شده در ردیف وسط قرار دارد همواره می‌توان یک مربع {TEX()} {3\times 3} {TEX}، شامل 9 مربع، که مربع وسط هاشورزده باشد در نظر گرفت (مطابق شکل بالا) واضح است که این ((مربع‌)) {TEX()} {3\times 3} {TEX} هرس شده را می‌توان با دومینوها پوشاند. ردیف‌های دو طرف این مربع {TEX()} {3\times 3} {TEX}دارای ابعادی است که حاصل‌ضرب آنها زوج است و بنابر مثال 1 قابل پوشش کامل به وسیله دومینوها هستند. ضمناً ردیف‌های بالا و پایین این سه ردیف به شرط وجود دارای ابعادی با حاصل‌ضرب زوج هستند و قابل پوشش کامل به وسیله دومینوها هستند.

---

!!مثال

نشان دهید که در هر مربع وفقی {TEX()} {3\times 3} {TEX}عددی که در مربع وسط قرار دارد 5 است و تعداد مربع‌های وفقی {TEX()} {3\times 3} {TEX}مختلف را بدست آورید.

---

@#16:

!تعریف

یک مربع {TEX()} {n\times n} {TEX}که در آن اعداد 1 تا {TEX()} {n^2} {TEX} چنان قرار گرفته‌اند که مجموع اعداد واقع در هر سطر مساوی مجموع اعداد واقع در هر ستون و مساوی مجموع اعداد هر قطر است، یک مربع وفقی (جادویی) نامیده می‌شود.

__حل __

@@{TEX()} {45 = 9 + 8 + … + 3 + 2 + 1} {TEX}@@

مجموع اعداد در هر سطر و در هر ستون و روی هر ((قطر)){TEX()} {\frac{45}{3}=15=} {TEX}

اعداد واقع در مربع‌ها را با حروف نمایش می‌دهیم:

@@{picture=img/daneshnameh_up/5/5b/com0041o.jpg}@@

@@ {TEX()} {(x + y + z) + 3u + (m + n + w)=45 } {TEX}@@

@@ {TEX()} { 3u = 15} {TEX}@@

@@{TEX()} { u = 5} {TEX}@@

همچنین آزمون همخوانی نشان می‌دهد که هیچکدام از اعداد{TEX()} {x,z,w,n} {TEX} نمی‌توانند فرد باشند. (علت بررسی شود، مثلاً {TEX()} {x} {TEX}را فرد بگذارید آنگاه {TEX()} {n} {TEX}نیز باید فرد باشد و … )

حال اگر{TEX()} { x = 2} {TEX} باشد دو جدول وفقی زیر حاصل می‌شود:

::{picture=img/daneshnameh_up/b/bc/com0041p.jpg}::

به همین ترتیب به ازای هر یک از مقادیر 6، 4 و 8 که به {TEX()} {x} {TEX}بدهیم دو جدول وفقی حاصل می‌شود. پس جمعاً 8 مربع وفقی{TEX()} {3\times 3} {TEX}وجود دارد.

---

!!مثال

نشان دهید که نقشة روبرو را که از 10 ناحیه تشکیل شده می‌توان با سه رنگ (نه کمتر) چنان رنگ کرد که نواحی مجاور با رنگ‌های متفاوت رنگ‌آمیزی شده باشند. اگر سه رنگ موجود، سبز، قرمز و زرد باشند، به چند طریق می‌توان این نقشه را رنگ کرد؟

نشان دهید که نقشه روبرو را که از 10 ناحیه تشکیل شده می‌توان با سه رنگ (نه کمتر) چنان رنگ کرد که نواحی مجاور با رنگ‌های متفاوت رنگ‌آمیزی شده باشند. اگر سه رنگ موجود، سبز، قرمز و زرد باشند، به چند طریق می‌توان این نقشه را رنگ کرد؟

::{picture=img/daneshnameh_up/6/6f/com0041q.jpg}::

__حل __

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

::{picture=img/daneshnameh_up/3/39/com0041r.jpg}::

@#16:

اما در همین وضعیت مربع شمارة 6 نیز می‌تواند سبز باشد (دو طریق) حال اگر مربع شماره 2 زرد باشد مربع‌های زرد و قرمز جابجا می‌شوند که در این حالت هم مربع شمارة 6 می‌تواند هم زرد و هم سبز باشد (دو طریق). پس وقتی ناحیه 1 سبز باشد به چهار طریق می‌توان مربع‌ها را رنگ‌آمیزی کرد. چون سه رنگ وجود دارد، پس بنابر اصل ضرب ، جمعاً {TEX()} {3\times 4=12} {TEX}طریق برای رنگ‌آمیزی این نقشه وجود دارد.

اما در همین وضعیت مربع شماره 6 نیز می‌تواند سبز باشد (دو طریق) حال اگر مربع شماره 2 زرد باشد مربع‌های زرد و قرمز جابجا می‌شوند که در این حالت هم مربع شماره 6 می‌تواند هم زرد و هم سبز باشد (دو طریق). پس وقتی ناحیه 1 سبز باشد به چهار طریق می‌توان مربع‌ها را رنگ‌آمیزی کرد. چون سه رنگ وجود دارد، پس بنابر اصل ضرب ، جمعاً {TEX()} {3\times 4=12} {TEX}طریق برای رنگ‌آمیزی این نقشه وجود دارد.

---

!!مثال

فرض کنید یک مستطیل {TEX()} {2\times n} {TEX}داریم، می‌خواهیم این مستطیل را با دومینوها بپوشانیم. به چند طریق مستطیل {TEX()} {2\times n} {TEX}با دومینوها کاملاً پوشانده می‌شود؟

__حل __

فرض کنید{TEX()} {d_n} {TEX}تعداد طرق پوشاندن یک مستطیل {TEX()} {2\times n} {TEX}با دومینوها باشد.

::{picture=img/daneshnameh_up/c/cf/com0041s.jpg}::

حال طریق پوشش مستطیل {TEX()} {2\times n} {TEX}را به دو دسته تقسیم می‌کنیم.

1.پوشش‌هایی که در آنها آخرین دومینو به طور عمودی قرار گرفته است که تعداد حالت‌های پوشش مربوط به بقیة مستطیل که{TEX()} {2\times (n-1)} {TEX}می‌باشد برابر {TEX()} {d_{n-1}} {TEX}است.

1.پوشش‌هایی که در آنها آخرین دومینو به طور عمودی قرار گرفته است که تعداد حالت‌های پوشش مربوط به بقیه مستطیل که{TEX()} {2\times (n-1)} {TEX}می‌باشد برابر {TEX()} {d_{n-1}} {TEX}است.

2.پوشش‌هایی که در آنها دومینوها به طور افقی در سمت راست قرار گرفته‌اند و بقیه ((مستطیل))‌ها را که{TEX()} {2\times (n-2)} {TEX}می‌باشد با حالت‌های مختلف می‌پوشانیم که تعدادش برابر {TEX()} {d_{n-2}} {TEX}می‌باشد. بنابراین خواهیم داشت:

@@{picture=img/daneshnameh_up/2/2e/com0041t.jpg}@@

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0143.pdf]

---

!همچنین ببینید

*((رنگ آمیزی و همخوانیII ))

*((اصل اکسترمال ))

#@^

تاریخچه

توجه:

از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..

تفاوت با نگارش: 2

سرویس‌های رشد:

فهرست: