====== سوال ۲۱ ======


یک جدول
$4 \times 5$
داریم در هر یک از خانه‌های آن عدد ۰ نوشته شده است.  ایلیچ الگوریتم زیر را انجام ‌می‌دهد:

۱. به ازای هر سطر از بالا به پایین انجام بده:

۱-۱. به ازای هر ستون از چپ به راست انجام بده:

۱-۱-۱. خانه‌ی واقع در سطر و ستون گفته شده را در نظر بگیر. سطر یا ستون آن را انتخاب کن و تمام خانه‌های سطر یا ستون انتخاب شده را برعکس کن (از ۰ به ۱ و از ۱ به ۰).

از میان تمام 
$2^{20}$
حالت برای انتخاب سطرها و ستون‌ها توسط ایلیچ،
در چند حالت پس از اجرای الگوریتم به جدولی می‌رسیم که تمام خانه‌های آن عدد ۱ دارند؟

  - ۴۰۹۶
  - ۲۵۶
  - ۵۱۲
  - ۸۱۹۲
  - ۰

<راهنمایی>
یک خانه که ستونش را تغییر داده سفید و در غیر این صورت آن را سیاه می‌کنیم. شروطی بر روی زوجیت تعداد خانه‌های سیاه و سفید سطر‌ها و ستون‌ها بیابید.
</راهنمایی>

<راهنمایی>
اگر ستونی داشته باشیم که تعداد زوجی خانه‌ی سفید داشته باشد(به تعریف راهنمایی پیشین)، در مورد تعداد خانه‌های سیاه سطر‌ها چه می‌توان گفت؟
</راهنمایی>

<راهنمایی>
در راستای راهنمایی پیشین، اگر ستونی داشته باشیم که تعداد زوجی خانه‌ی سفید داشته باشد، باید تمام سطرها شامل  تعداد فردی خانه‌ی سیاه باشند.
</راهنمایی>

<راهنمایی>
پس می‌توانید کل حالات را در دو دسته بررسی کنید. تمام ستون‌ها شامل فرد خانه‌ی سفید و تمام سطرها شامل زوج خانه‌ی سیاه باشند یا تمام ستون‌ها شامل زوج خانه‌ی سفید و تمام سطرها شامل فرد خانه‌ی سیاه باشند. 
</راهنمایی>
<راهنمایی>
نشان دهید حالت اول راهنمایی پیشین، نمی‌تواند رخ دهد.
</راهنمایی>

<راهنمایی>
برای حالت دوم راهنمایی‌های پیشین، عملیات انجام شده روی ۱۲ خانه‌ی ابتدایی را در نظر گیرید. 
</راهنمایی>

<راهنمایی>
روی زوجیت تعداد خانه‌های سیاه و سفید ۱۲ خانه‌ی ابتدایی‌ای که عملیات بر آن‌ها انجام شده حالت بندی کنید.
</راهنمایی>

<پاسخ>
 گزینه‌ی ۱ درست است.



یک خانه که ستون‌ش را تغییر داده سفید و در غیر این صورت آن را سیاه می‌کنیم. اگر ستونی داشته باشیم که تعداد زوجی خانه‌ی سفید داشته باشد، باید تمام سطرها شامل  تعداد فردی خانه‌ی سیاه باشند (تا خانه‌های آن ستون برابر ۱ شود). به همین ترتیب برای ستون با تعداد فردی خانه‌ی سفید می‌توان حکم مشابهی گفت. با در نظر گرفتن حکمی مشابه (با در نظر گرفتن یک سطر) نیز، نتیجه می‌گیریم تنها یکی از دو حالت زیر رخ می‌دهد:
  * تمام ستون‌ها شامل فرد خانه‌ی سفید و تمام سطرها شامل زوج خانه‌ی سیاه هستند. امکان رخ دادن این حالت  وجود ندارد، زیرا تعداد کلّ خانه‌های جدول برابر با مجموع تعداد خانه‌های سیاه سطرها و تعداد خانه‌های سفید ستون‌ها است. پس در این حالت تعداد کلّ خانه‌های جدول فرد خواهد شد.
  * تمام ستون‌ها شامل زوج خانه‌ی سفید و تمام سطرها شامل فرد خانه‌ی سیاه هستند. برای شمردن حالات مطلوب این قسمت، ابتدا تمام خانه‌های جدول جز ستون و سطر آخر را به $2^{12}$ حالت رنگ می‌کنیم. حال رنگ سه خانه‌ی نخست ستون آخر و چهار خانه‌ی نخست سطر آخر به طور یکتا مشخص می‌شود. اکنون تمام خانه‌ها به جز خانه‌ی واقع در سطر و ستون آخر رنگ شده‌اند. دو حالت داریم:
     * در ۱۲ خانه‌ی ابتدایی رنگ شده تعداد فردی خانه‌ی سیاه و تعداد  فردی خانه‌ی سفید داشته باشیم.  در این صورت باید سه خانه‌ی نخست ستون آخر شامل تعداد زوجی خانه‌ی سیاه (و در نتیجه تعداد فردی خانه‌ی سفید) باشند. به همین ترتیب، چهار خانه‌ی نخست سطر آخر شامل تعداد فردی خانه‌ی سفید (و در نتیجه تعداد فردی خانه‌ی سیاه) هستند. پس تنها خانه‌ی رنگ نشده به طور یکتا باید سفید شود.
     * در ۱۲ خانه‌ی ابتدایی رنگ شده تعداد زوجی خانه‌ی سیاه و تعداد  زوجی خانه‌ی سفید داشته باشیم.  در این صورت باید سه خانه‌ی نخست ستون آخر شامل تعداد فردی خانه‌ی سیاه (و در نتیجه تعداد زوجی خانه‌ی سفید) باشند. به همین ترتیب، چهار خانه‌ی نخست سطر آخر شامل تعداد زوجی خانه‌ی سفید (و در نتیجه تعداد زوجی خانه‌ی سیاه) هستند. پس تنها خانه‌ی رنگ نشده به طور یکتا باید سیاه شود.
   
$\qquad$ پس در هر صورت تنها خانه‌ی رنگ نشده از جدول به طور یکتا رنگ می‌شود.

پس پاسخ برابر
$2^{12} = 4096$
است.
</پاسخ>

  * [[سوال ۲۰|سوال قبل]]
  * [[سوال ۲۲|سوال بعد]]