المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

۱۰۰ زیرجدول $100 \times 100$ متمایز در یک جدول $200 \times 200$ داریم. حداکثر چند خانه از جدول در تمام این زیرجدول‌ها هستند؟

  1. ۶۴۰۰
  2. ۹۰۰
  3. ۸۱۰۰
  4. ۱۰۰
  5. ۸۲۸۱

پاسخ

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

خانه‌ی بالا-چپ تمام زیرجدول‌ها را در نظر بگیرید. این ۱۰۰ خانه را خانه‌های مهم می‌نامیم. خانه‌هایی را که در تمام زیرجدول‌ها هستند، همگانی نام می‌نهیم.

کوچک‌ترین زیرجدولی را در نظر بگیرید که تمام خانه‌های مهم را بپوشاند. اگر این زیرجدول $r$ سطر داشته باشد، با در نظر گرفتن بالاترین و پایین‌ترین خانه‌ی مهم، خانه‌های همگانی در یک زیرجدول $\big(100 - (r-1)\big) \times 100$ محصور می‌شوند. به همین ترتیب اگر این زیرجدول $c$ ستون داشته باشد، خانه‌های همگانی در یک زیرجدول $100 \times \big(100 - (c-1)\big)$ محصور می‌شوند. پس تعداد خانه‌های همگانی از $(101-r) \times (101-c)$ بیش‌تر نیست. از آن‌جایی که $rc \ge 100$ حداکثر این مقدار برابر $91 \times 91 = 8281$ است.

حال اگر خانه‌های مهم زیرجدول‌ها در زیرجدول $10 \times 10$ بالا-چپ جدول باشند، یک مثال برای ۸۲۸۱ ساخته می‌شود.

پس پاسخ برابر ۸۲۸۱ است.


ابزار صفحه