المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:روش رنگ‌آمیزی

روش رنگ‌آمیزی

در این صفحه با روش رنگ‌آمیزی برای حل مسائل آشنا می‌شوید. رنگ‌آمیزی یک روش پرکاربرد برای حل مسائل است. در این روش با رنگ‌آمیزی عناصر مسئله به پاسخ می‌رسیم.


تعریف

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

مثال: دایره‌ی زیر را در نظر بگیرید. در هر مرحله می‌توانید دو قطاع مجاور انتخاب کرده و به اعداد هر کدام، یک واحد اضافه کنید. آیا پس از تعدادی مرحله تمام اعداد را برابر کرد؟

پاسخ

خیر؛ با زوجیت مسئله را حل می‌کنیم. مجموع اعداد در ابتدا فرد است. در هر مرحله به مجموع اعداد ۲ واحد اضافه می‌شود؛ پس هم‌واره فرد می‌ماند. اگر بخواهیم تمام اعداد برابر شوند، مجموع اعداد باید به صورت $6k$ شود که زوج است و امکان ندارد.

مثال: همان مسئله‌ی قبل را برای دایره‌ی زیر حل کنید:

پاسخ

این بار راه حل قبل (زوجیت) ما را به پاسخ نمی‌رساند. از روش رنگ‌آمیزی استفاده می‌کنیم. قطاع‌ها را به شکل زیر به صورت یک در میان با قرمز و سفید رنگ کنید: $S_1$ و $S_2$ را به ترتیب مجموع اعداد قطاع‌های قرمز و مجموع اعداد قطاع‌های سفید تعریف می‌کنیم. در ابتدا $S1-S2$ برابر ۲ است. در هر مرحله به مقدار هر یک از $S_1, S_2$ یک واحد اضافه می‌شود؛ پس مقدار $S_1 - S_2$ ثابت می‌ماند. اگر بخواهیم تمام اعداد را برابر کنیم، $S_1-S_2=0$ خواهد شد که امکان ندارد.


رنگ‌آمیزی‌های پیچیده‌تر

در مثال بالا با رنگ‌آمیزی توسط دو رنگ و آن هم به صورت یک در میان (شترنجی) به پاسخ رسیدیم. گاهی نیاز است از رنگ‌های بیش‌تری استفاده کنیم و گاهی نیز روش رنگ‌آمیزی کمی پیچیده‌تر است و لزومن به صورت یک در میان نیست.

مثال: یک جدول $3 \times 3$ داریم که در ابتدا یک گوشه‌ی آن سیاه است و بقیه‌ی خانه‌های آن سفید هستند. در هر مرحله می‌توان یک سطر یا یک ستون در نظر گرفت و رنگ تمام خانه‌های آن را عوض کرد (از سیاه به سفید و بالعکس). آیا می‌توان کاری کرد که تمام خانه‌های جدول سیاه شوند؟

پاسخ

همین مسئله را برای یک جدول $8 \times 8$ در زوجیت حل کردیم؛ اما آن روش این‌جا به کار ما نمی‌آید. خانه‌های گوشه‌ی جدول را در نظر بگیرید و آن‌ها را قرمز کنید (توجه کنید ما کاری با رنگ‌های مسئله نداریم و به طور جداگانه این رنگ‌آمیزی را انجام می‌دهیم): حال تعریف می‌کنیم: $$S = \text{تعداد خانه‌های سیاه در گوشه‌ها}$$ زوجیت $S$ با هر حرکت ثابت می‌ماند. از آن‌جایی که $S$ در ابتدا فرد و در انتها زوج است، این کار ممکن نیست.

مثال: آیا می‌توان یک جدول $10 \times 10$ را با کاشی‌های $1 \times 4$ پوشاند؟

پاسخ

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


چند مثال

مثال: یک جدول $8 \times 8$ داریم که در هر خانه‌ی آن یک عدد صحیح نوشته شده است. در هر مرحله می‌توان یک زیرجدول $3 \times 3$ یا $4 \times 4$ انتخاب کرد و به اعداد هر یک از خانه‌های آن یک واحد اضافه کرد. آیا هم‌واره می‌توان تمام اعداد را زوج کرد؟

پاسخ

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

مثال: $2n$ کارت در یک ردیف داریم که روی هر کدام یک عدد صحیح نوشته شده است و مجموع اعداد کارت‌ها فرد است. دو نفر با هم بازی می‌کنند. هر فرد در نوبت‌ش یکی از دو کارت کناری ردیف را برای خود برمی‌دارد. در انتها کسی برنده است که مجموع اعداد کارت‌های‌ش بیش‌تر باشد. چه کسی استراتژی برد دارد؟

پاسخ

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


مسائل نمونه از المپیادهای کامپیوتر ایران

منابع و مراجع

  1. D.Fomin, I.Itenberg, S.Genkin (1996), Mathematical circles (Russian Experience), Mathematical World
  2. Arthur Engel (1998), Problem Solving Strategies, New York, Springer

خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:

نظرات

نظر خود را وارد کنید. دستورات ویکی مجاز است:
‎ 91 +10 =​ ? ‎
 

ابزار صفحه