معمای المپیادی: هفت ناحیه رنگی

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

.
.
.
.
.

پاسخ معما:

84
فرض کنیم ناحیه های مشخص شده با اعداد 1،2،3 در شکل فوق به ترتیب دارای رنگ های x،y،z باشند. توجه کنید که تمامی رنگ های x، y، z نمی توانند متمایز باشند زیرا در غیر این صورت ناحیه مرکزی را با هیچ رنگی نمیتوان رنگ کرد. اکنون دو حالت را بررسی می کنیم:
حالت اول:
x،y،z همرنگ باشند. در این حالت رنگ مشترک را می توان به 3 حالت انتخاب کرد. همچنین هر یک از دیگر نواحی را می توان به دو صورت رنگ آمیزی کرد. پس در این حالت، تعداد رنگ آمیزی ها برابر 48 خواهد بود:
3x2x2x2x2=48
حالت دوم:
در میان x،y،z از یک رنگ دوبار و از یک رنگ یک بار استفاده شده باشد. برای انتخاب ناحیه ی با رنگ متمایز 3، برای انتخاب رنگ این ناحیه، 3 و برای انتخاب رنگ دیگر، 2 انتخاب داریم. پس برای مشخص نمودن رنگ ناحیه ی 1،2،3 در این حالت 3x3x2=18 روش متمایز داریم. حال توجه کنید که رنگ مرکزی به صورت یکتا، مشخص می شود چرا که از دو رنگ متمایز، همسایه دارد. همچنین دو تا از نواحی گوشه ای نیز با هر دو رنگ مجاور هستند و رنگ این نواحی نیز بصورت یکتا مشخص می گردد. تنها ناحیه نامشخص ناحیه گوشه ای است که با دو ناحیه همرنگ مجاور است و در نتیجه می توان آن را به دو شیوه رنگ آمیزی کرد. پس در این حالت، طبق اصل ضرب، تعداد شیوه های رنگ آمیزی برابر 18x2=36 است.
پس طبق اصل جمع، تعداد راه های رنگ آمیزی شکل برابر 84=36+48 است.

منبع:ihoosh