====== سوال ۱۱======
یک جدول $۱۰\times۱۰$ داریم. می خواهیم تعدادی از خانه های آن را رنگ کنیم به طوری که شرط زیر برقرار باشد:
  * به ازای هر پوشش این جدول با مستطیل های $۱\times۲$، تعداد مستطیل های $۱\times۲$ که هر دو خانه ی آن ها رنگ شده است حداکثر ۲۵ باشد. 

توجه کنید که در هر پوشش باید هر خانه ی جدول توسط دقیقا یک مستطیل $۱\times۲$ پوشانده شود. همچنین مستطیل های $۱\times۲$ می توانند به صورت افقی یا عمودی قرار بگیرند و هرکدام باید دقیقا دو خانه را پوشش دهند. با این شرایط حداکثر چند خانه را می توانیم رنگ کنیم؟

  - ۵۱
  - ۵۰
  - ۸۰
  - ۶۰
  - ۷۵

<راهنمایی>
فرض کنید حالتی وجود داشته باشد که دقیقا ۲۵ دومینو گذاشته شده‌اند تا هر دو خانه‌ی آن‌ها رنگ شده باشد. در این صورت حداکثر چند خانه‌ی رنگی می‌توانیم داشته باشیم؟
</راهنمایی>
<راهنمایی>
در راستای راهنمایی پیشین، یعنی ۲۵ دومینو با دو خانه‌ی رنگی و ۲۵ دومینو با یک خانه‌ی رنگی وجود دارند. پس حداکثر چند خانه‌ی رنگی وجود دارد؟
</راهنمایی>
<راهنمایی>
برای مثال عدد ۷۵، یک جدول که به شکل صفحه‌ی شطرنج رنگ‌آمیزی شده است را در نظر گیرید. سعی کنید تغییراتی در آن اعمال کنید تا به حکم دست یابید.
</راهنمایی>

<راهنمایی>
نیمه‌ی چپ جدول را کامل رنگ کنید.
</راهنمایی>



<پاسخ>

گزینه‌ی ۵ درست است.


در صورتی که در یک پوشش ۲۵ مستطیل کامل رنگ شده باشد و از بقیه‌ی مستطیل‌ها نیز حداکثر یک خانه‌ی رنگ شده داشته باشیم، به حداکثر ۷۵ خانه‌ی رنگی خواهیم داشت.


مثال زیر با این تعداد رنگ‌آمیزی، شرایط مسئله را برآورده کرده است.






{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۳:1123.png |}}


</پاسخ>

  * [[سوال ۱۲|سوال بعد]]
  * [[سوال ۱۰|سوال قبل]]