منو
 کاربر Online
746 کاربر online

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

چاپ
علوم ریاضی > علو م رایانه



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


رنگ آمیزی

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

اصل همخوانی



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

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

فرض کنید یک صفحه داریم که از مربع متساوی تشکیل شده است. مربع‌ها در سطر و ستون قرار دارند. گاهی اوقات برای حل مسئله‌ای خاص لازم می‌شود که خانه‌های این شبکه را یک در میان، سفید و سیاه در نظر بگیریم.
منظور از یک دومینو یک مستطیل است که در شکل زیر ملاحظه می‌کنید. مثلاً اگر بتوان یک صفحه شطرنجی را با تعدادی دومینو، بدون اینکه دومینوها روی هم قرار گیرند، به طور کامل پوشاند گوییم آن صفحه شطرنجی دارای یک پوشش کامل بوسیله دومینوها است.
img/daneshnameh_up/b/bd/com0041a.jpg


مثال

نشان دهید اگر فرد باشند یک صفحه شطرنجی دارای یک پوشش کامل بوسیله دومینوها نیست.
حل
تعداد مربع‌های صفحه شطرنجی که فرد هستند عددی فرد است. چون هر تعداد از دومینوها را که در نظر بگیریم تعداد زوج خواهد بود، پس نمی‌توان این صفحهرا با دومینوها پوشاند. در اینجا از ویژگی زوجیت استفاده کردیم.
از این مسأله نتیجه می‌گیریم که برای پوشش کامل یک صفحه شطرنجی بوسیله دومینوها لازم است ضرب در زوج باشد.
این مثال را می‌توان با روش دیگری هم بررسی کرد:


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

مثال

یک صفحه مشبک موجود است، به قسمی که خانه‌های گوشه‌ای متقابل آن، مطابق شکل 1، حذف شده‌اند. (در شکل فوق نشان‌دهنده خانه مشکی ونشان‌دهنده خانه سفید می‌باشد.)
img/daneshnameh_up/4/4e/com0041b.jpg

تعدادی دومینو در دست می‌باشد. آیا می‌توان صفحه فوق را به طور کامل با دومینوها پوشاند. (یعنی یک پوشش کامل را بوسیله دومینوها داشته باشیم. به تعریف پوشش کامل توسط دومینوها توجه کنید.)
حل
این کار نشدنی است، زیرا هر دومینو یک خانه سیاه و یک خانه سفید را می‌پوشاند. بنابراین عدد دومینو عدد خانه سیاه و عدد خانه سفید را خواهند پوشاند، یعنی از هر کدام به عدد مساوی. اما صفحه مسأله ما تعداد بیشتری خانه سیاه نسبت به سفید دارد. پس نمی‌توان آن را با دومینوها پوشاند. تعمیم دومینو یا 2مربعی، چند مربعی است و قضایای ما را درباره چند مربعی‌های ساده شکل زیر می‌باشد.
img/daneshnameh_up/3/34/com0041c.jpg

به طور دقیق یک مربعی یک مجموعه مرتبط (همبند) از مربع واحد صفحه مشبک است، به گونه‌ای که اگر یک رخ در هر خانه از آن قرار بگیرد قادر باشد با تعداد متناهی حرکت بر روی صفحه به هر مربع آن برود. برای مثال شکل زیر نمی‌تواند یک سه مربعی باشد.
img/daneshnameh_up/c/c3/com0041d.jpg



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

مثال

آیا پوشاندن صفحه شطرنج با 21 عدد 3- مربعی راست و یک عدد 1- مربعی در گوشه سمت چپ بالای آن قرار داده شده ممکن است؟ اگر جواب منفی است یک پوشش برای آن بیان کنید.
سه مربعی راست:
img/daneshnameh_up/8/86/com0041e.jpg

حل
برای اثبات این مطلب صفحه را با سه رنگ مانند شکل زیر رنگ می‌کنیم.
img/daneshnameh_up/9/95/com0041f.jpg

می‌بینید که 21 مربعی با رنگ ، 22 مربع با رنگ و 21 مربع با رنگ به چشم می‌خورد. هر 3- مربعی که در این صفحه قرار می‌گیرد، یک مربع و یکمربع و یک مربع را می‌پوشاند. پس این 3 - مربعی‌ها همیشه تعداد مساوی خانه از هر کدام از این سه رنگ را می‌پوشانند. اما گوشه سمت چپ بالا یک مربع است و با پوشاندن آن با یک 1- مربعی ،20 عدد مربع باقی می‌ماند، اما 20 عدد مربع و 21 عددمربع خواهیم داشت. این اعداد نامساوی‌اند، پس چنین پوششی غیرممکن است.
پس ما نتیجه می‌گیریم 1- مربعی باید روی یکمربع باشد.
حال فرض می‌کنیم 1- مربعی روی یکمربع قرار گرفته باشد، برای مثال گوشه سمت چپ پایین. با در نظر گرفتن تقارن نسبت به محور در می‌یابیم که این حالت، شبیه همان حالتی است که 1- مربعی روی گوشه سمت چپ بالایی بود و چنین پوششی غیرممکن می‌باشد. در حقیقت مکان‌های ممکن برای جای‌گذاری 1- مربعی، فقط مربع‌های هستند که نسبت به مربع‌های دیگر متقارن‌اند. این مربع‌ها چهار مربع سیاه شکل زیر هستند. شکل زیر نشان می‌دهد که اگر 1- مربعی روی یکی از این 4 مربع باشد بقیه صفحه را می‌توان با 3- مربعی‌های راست پوشاند.
img/daneshnameh_up/9/9c/com0041g.jpg


نتیجه



شرط لازم و کافی برای این که صفحه شطرنج به وسیله 21 عدد 3- مربعی راست و یک عدد 1-مربعی پوشانده شود، این است که 1- مربعی در یکی از چهارخانه سیاه شکل بالا باشد.
شکل زیر یک نمونه از پوشش صفحه این مثال را نشان می‌دهد. (مستطیل‌ها مربع فرض شود)
img/daneshnameh_up/c/c5/com0041h.jpg


مثال

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

البته حکم فوق در مورد صفحه درست است و اثبات به وسیله استقرا روی است. این مسئله برای یک صفحه بدیهی است.
img/daneshnameh_up/7/71/com0041j.jpg

یک صفحهرا در نظر می‌گیریم. آن را به چهار مربع مطابق شکل زیر تقسیم می‌کنیم. فرض کنید 1-مربعی در یکی از چهار ربع باشد مثلاً‌ در ربع سوم . هر یک از ربع‌ها یک صفحه است و ما می‌توانیم 1- مربعی را در هر ربع قرار دهیم و بقیه را با 3-مربعی قائمه بپوشانیم. در ربع سوم قبلاً‌ 1-مربعی قرار گرفته است، در سه ربع دیگر -1 مربعی‌ها را در مرکز قرار می‌دهیم. آنگاه می‌توان این 3 عدد 1- مربعی مرکزی را با یک 3- مربعی قائمه عوض کنیم. بنابراین صفحه را با یک 1- مربعی در یک مکان دلخواه و 5 تا 3-مربعی قائمه پوشانده‌ایم.
img/daneshnameh_up/b/b3/com0041k.jpg

حالت و همچنین حالت کلی به همین صورت استقرایی بحث می‌شود. در شکل زیر فرض کنیم 1- مربعی مثلاً در ربع دوم قرار بگیرد آنگاه ربع دوم خود یک مربعاست که مطابق قبل می‌توان آن را پوشش داد و 1- مربعی ربع اول و سوم و چهارم هر کدام در گوشه قرار بگیرد و با هم تشکیل سه مربعی بدهند.
img/daneshnameh_up/e/e9/com0041l.jpg




مثال

یک صفحه شطرنجی در را در نظر بگیرید که در آن فرد است، و فرض کن ید که مربع واقع در گوشه چپ و بالای آن سفید باشد. نشان دهید که اگر یک مربع سفید از این صفحه شطرنجی برداشته شود صفحه شطرنجی هرس شده دارای پوشش کامل به وسیله دومینوها است.
حل
ردیف افقی که یک مربع سفید از آن برداشته شده در نظر می‌‌گیریم. اگر رنگ اولین مربع از سمت چپ در این ردیف سفید باشد پس، از تعدادی فرد مربع سفید تشکیل شده که تعداد سفیدها یکی از تعداد سیاه‌ها بیشتر است. یک مربع سفید برداشته شده است. شکل زیر نشان می‌دهد که این مربع سفید از هر جا که برداشته شده باشد می‌توان بقیه ردیف را با دومینوها پوشاند.
img/daneshnameh_up/6/67/com0041m.jpg

ضمناً ردیف‌های بالا و پایین این ردیف دارای حاصل ضرب سطر و ستون زوج است و بنابر مثال 1 می‌توان آنها را با دومینوها پوشاند.
اما اگر مربع اول از سمت چپ مشکی باشد حداقل یک ردیف مربع در بالا و یک ردیف مربع در پایین آن وجود دارد. این سه ردیف را به صورت ذیل در نظر می‌گیریم که مثلاً خانه سفید هاشورزده شده برداشته شده است.
img/daneshnameh_up/0/06/com0041n.jpg

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

مثال

نشان دهید که در هر مربع وفقی عددی که در مربع وسط قرار دارد 5 است و تعداد مربع‌های وفقی مختلف را بدست آورید.



تعریف

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


مجموع اعداد در هر سطر و در هر ستون و روی هر قطر
اعداد واقع در مربع‌ها را با حروف نمایش می‌دهیم:
img/daneshnameh_up/5/5b/com0041o.jpg




همچنین آزمون همخوانی نشان می‌دهد که هیچکدام از اعداد نمی‌توانند فرد باشند. (علت بررسی شود، مثلاً را فرد بگذارید آنگاه نیز باید فرد باشد و … )
حال اگر باشد دو جدول وفقی زیر حاصل می‌شود:
img/daneshnameh_up/b/bc/com0041p.jpg

به همین ترتیب به ازای هر یک از مقادیر 6، 4 و 8 که به بدهیم دو جدول وفقی حاصل می‌شود. پس جمعاً 8 مربع وفقیوجود دارد.

مثال

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

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



اما در همین وضعیت مربع شماره 6 نیز می‌تواند سبز باشد (دو طریق) حال اگر مربع شماره 2 زرد باشد مربع‌های زرد و قرمز جابجا می‌شوند که در این حالت هم مربع شماره 6 می‌تواند هم زرد و هم سبز باشد (دو طریق). پس وقتی ناحیه 1 سبز باشد به چهار طریق می‌توان مربع‌ها را رنگ‌آمیزی کرد. چون سه رنگ وجود دارد، پس بنابر اصل ضرب ، جمعاً طریق برای رنگ‌آمیزی این نقشه وجود دارد.

مثال

فرض کنید یک مستطیل داریم، می‌خواهیم این مستطیل را با دومینوها بپوشانیم. به چند طریق مستطیل با دومینوها کاملاً پوشانده می‌شود؟
حل
فرض کنیدتعداد طرق پوشاندن یک مستطیل با دومینوها باشد.
img/daneshnameh_up/c/cf/com0041s.jpg

حال طریق پوشش مستطیل را به دو دسته تقسیم می‌کنیم.
1.پوشش‌هایی که در آنها آخرین دومینو به طور عمودی قرار گرفته است که تعداد حالت‌های پوشش مربوط به بقیه مستطیل کهمی‌باشد برابر است.
2.پوشش‌هایی که در آنها دومینوها به طور افقی در سمت راست قرار گرفته‌اند و بقیه مستطیل‌ها را کهمی‌باشد با حالت‌های مختلف می‌پوشانیم که تعدادش برابر می‌باشد. بنابراین خواهیم داشت:
img/daneshnameh_up/2/2e/com0041t.jpg


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

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

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



تعداد بازدید ها: 23012


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



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