المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۱:سوال ۱۷

سوال ۱۷

یک جدول ‎$9 \times 9$‎ از اعداد ‎۰‎ و ‎۱‎ داده شده است. می‌دانیم در هر چهار خانه‌ای که تشکیل یک مربع ‎$2 \times 2$‎ بدهند حداقل ‎۲‎ و حداکثر ‎۳‎ بار عدد ‎۱‎ ظاهر شده‌است. حداقل و حداکثر تعداد یک‌های جدول چه‌قدر می‌تواند باشد؟

  1. ۴۱‎ و ‎۶۵
  2. ۴۰‎ و ‎۶۱
  3. ۳۶‎ و ‎۶۵
  4. ۴۰‎ و ‎۶۵
  5. ۳۶‎ و ‎۶۱

پاسخ

گزینه (۳) درست است.

حالت مینیمم موقعی است که سطرهای دوم٬ چهارم٬ ششم و هشتم همگی ۱ و مابقی خانه‌ها ۰ باشند٬ که در این صورت تعداد ۱ها٬ ۳۶ خواهد بود.

حالت ماکزیمم نیز موقعی است که سطرهای فرد همگی ۱ وسطرهای زوج نیز یک در میان ۱ باشند (با شروع از ۱) که دراین صورت نیز تعداد ۱ ها $5\times9+4\times5$؛ یعنی ۶۵ خواهد بود.


ابزار صفحه