شبكه‌اي از خانه‌ها را در نظر بگيريد كه اكثر خانه‌هاي آن سفيد رنگ و بعضي از خانه‌هايش به‌رنگ آبي باشد. اصطلاح «دو خانه‌ي مجاور» را براي دو خانهاي درنظر مي‌گيريم كه در يك يال با يكديگر اشتراك داشته باشند.
ابتدا خانه‌هايي را به‌رنگ آبي درمي‌آوريم كه قبلاً داراي حداقل دو خانه‌ي مجاور باشند.
به‌عنوان مثال:
به‌شكل ذيل توجه كنيد:
|
يا |
|
شكل 1. |
خانهاي كه داخل آن حرف «الف» نوشته شده است را با رنگ آبي پُر مي‌كنيم زيرا در هر حالت داراي دو خانه‌ي مجاور است.
خانه‌هايي كه رنگ مي‌شوند باعث مي‌شوند خانه‌هاي سفيد ديگري نيز مشمول همان قاعده شده و آن‌ها را نيز رنگ كنيم.
بعد از گذشت مدت زماني:
| - يا تمام جدول به‌رنگ آبي درمي‌آيد |
| - يا رنگ كردن به خانهاي ختم مي‌شود كه تنها در مجاورت يك خانه‌ي آبي ديگر قرار گرفته است. |
براي ما رنگي شدن كامل تمام خانه‌هاي شبكه مورد نظر است.
به‌عنوان مثال:
فرض كنيد شبكه‌اي از خانه‌ها به‌صورت 8 در 8 داريم به‌گونه‌اي كه خانه‌هاي آبي رنگ مطابق شكل 2 بر روي قطر آن قرار گرفته است.
|
شكل بالا با رعايت قاعده
به‌شكل ذيل تبديل مي‌شود: |
|
و نهايتاً
به‌شكل ذيل منتهي مي‌شود |
|
شكل 2. |
البته چنان‌چه بخواهيم عمليات رنگ كردن خانه‌ها مطابق قاعده‌ي مذكور منتهي به رنگي شدن تمام خانه‌هاي جدول شود حالت‌هاي مختلفي از حالت اوليه‌ي خانه‌هاي آبي‌رنگ وجود دارد (شكل 3).
|
يا |
|
شكل 3 – نمونه‌اي از حالت‌هاي ابتدايي
كه منجر به رنگي شدن كامل خانه‌هاي جدول مي‌شود. |
به‌نظر شما:
| - آيا حالت ابتدايي متشكل از 7 خانه‌ي آبي‌رنگ ممكن است وجود داشته باشد كه منتهي به رنگي شدن كامل تمام خانه‌هاي جدول شود |
| - يا اين‌كه هميشه نيازمند حداقل 8 خانه‌ي آبي‌رنگ در حالت اوليه هستيم؟ |