یک جدول $۲۰۰۵× ۲۰۰۵$ در اختیار داریم که تمام خانههای آن سفید هستند. شخصی ۱۳۸۳ بار، یک سطر و یک ستون را انتخاب و رنگ همهی خانههای آن سطر و آن ستون را برعکس میکند. توجه کنید که رنگ خانهی مشترک در سطر و ستون تغییر نمیکند. تعداد خانههای سیاه باقیمانده در جدول در انتها، کدامیک از گزینههای زیر میتواند باشد؟
پاسخ
گزینه (۳) درست است.
معلوم است که برایند کار مانند آن است که در نهایت $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$ برابر ۱٬۷۲۰٬۴۵۲ به دست میآید که در بین گزینهها فقط عدد موجود در گزینه ۳ در این محدوده است.