Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۹

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

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

پاسخ

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

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

x=i×(2005j)+(2005i)×j=2005(i+j)2ij

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


ابزار صفحه