المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۹

یک جدول $۲۰۰۵× ۲۰۰۵$ در اختیار داریم که تمام خانه‌های آن سفید هستند. شخصی ۱۳۸۳ بار، یک سطر و یک ستون را انتخاب و رنگ همه‌ی خانه‌های آن سطر و آن ستون را برعکس می‌کند. توجه کنید که رنگ خانه‌ی مشترک در سطر و ستون تغییر نمی‌کند. تعداد خانه‌های سیاه باقی‌مانده در جدول در انتها، کدام‌یک از گزینه‌های زیر می‌تواند باشد؟

  1. ۰
  2. ۹۱۵، ۷۷۲، ۲
  3. ۰۷۸، ۱۹۶
  4. ۸۵۴، ۰۴۴، ۳
  5. ۱۲۴، ۲

پاسخ

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

معلوم است که برایند کار مانند آن است که در نهایت $i$ سطر متمایز و $j$ ستون متمایز انتخاب شده باشند(ستون و یا سطرهایی که زوج‌بار٬ انتخاب شده باشند٬ مانند آن است که اصلا انتخاب نشده‌اند و ستون و یا سطر‌های که فردبار انتخاب شده باشند مانند آن است که دقیقا یک‌بار انتخاب شده‌اند). از طرف دیگر چون ۱۳۸۳ فرد است بنابراین هردو عدد $i$ و $j$ فرد هستند. تعداد خانه‌های سیاه در سطر‌های $i$گانه برابر $2005-j$ و در سایز سطرها برابر $j$ می‌باشد٬ بنابراین تعداد خانه‌های سیاه برابر است با:

$$x=i\times(2005-j)+(2005-i)\times j=2005(i+j)-2ij$$

حداقل مقدار $x$ به ازای $i=j=1$ برابر با ۴۰۰۸ و حداکثر مقدار $x$ به ازای $i=j=1383$ برابر ۱٬۷۲۰٬۴۵۲ به دست می‌آید که در بین گزینه‌ها فقط عدد موجود در گزینه ۳ در این محدوده است.


ابزار صفحه