پاسخ : مسابقات دانش آموزی دانشگاه شریف
سوال كامپيوتر سال 90
به سوال هاي رنگ اميزي معروف هست كه چندتا نمونه رو توي تاپيك المپياد كامپيوتر حل كرديم.
اما يه بار ديگه روش هاي حلش رو اينجا مرور مي كنيم
اصولا روش حل خاصي براي اين سوال ها نيست و بايد فقط براي حل ذهن خلاق داشته باشيد.
ولي هميشه ايجاد تقارن در رنگ اميزي مي تونه تاثير داشته باشه.
رنگ اميزي از شكل هاي كوچيك و تعميم اون به شكل هاي بزرگتر.
و مهم ترين نكته رنگ اميزي به كمك گراف هست كه چون ميدونم كسي اينجا گراف نخونده پس اين روش رو نمي تونيد استفاده كنيد و از همون دو روش اول و ذهن خلاق بايد كمك بگيريد.
الان من اين تعداد رو پيدا كردم كه توي هر قسمت اگر 8 تا خونه رو رنگ كنيم مي توينم مسئله رو حل كنيم!
اين روش رو از راه تقارن حل كردم يعني واسه يه قسمت از شكل 8 تا رو پيدا كردم و براي اون قسمت ديگه هم همين 8 تا رو پياده كردم.
ولي اين روش كمترين تعداد نيست!!!!!!!!!!!
چرا؟ چون تقارن هميشه موثر نيست مخصوصا در شكل هايي كه داراي گره هستند! اگر اين بار مبناي كار رو روي گره بذاريم يعني اگر گره و اول رنگ كنيم و بقيه رو بر اساس گره پيش بريم شكل فرق مي كنه كه باعث ميشه تعداد رنگ اميزي ها كمتر بشه.
در نتيجه رنگ اميزي نهايي به اين صورت ميشه
پس در كل اگه ما 15 قسمت رو رنگ كنيم بقيه شكل به صورت يكتا حل مي شوند.
