یک جدول $4 \times 5$ داریم در هر یک از خانههای آن عدد ۰ نوشته شده است. ایلیچ الگوریتم زیر را انجام میدهد:
۱. به ازای هر سطر از بالا به پایین انجام بده:
۱-۱. به ازای هر ستون از چپ به راست انجام بده:
۱-۱-۱. خانهی واقع در سطر و ستون گفته شده را در نظر بگیر. سطر یا ستون آن را انتخاب کن و تمام خانههای سطر یا ستون انتخاب شده را برعکس کن (از ۰ به ۱ و از ۱ به ۰).
از میان تمام $2^{20}$ حالت برای انتخاب سطرها و ستونها توسط ایلیچ، در چند حالت پس از اجرای الگوریتم به جدولی میرسیم که تمام خانههای آن عدد ۱ دارند؟
راهنمایی
یک خانه که ستونش را تغییر داده سفید و در غیر این صورت آن را سیاه میکنیم. شروطی بر روی زوجیت تعداد خانههای سیاه و سفید سطرها و ستونها بیابید.
راهنمایی
اگر ستونی داشته باشیم که تعداد زوجی خانهی سفید داشته باشد(به تعریف راهنمایی پیشین)، در مورد تعداد خانههای سیاه سطرها چه میتوان گفت؟
راهنمایی
در راستای راهنمایی پیشین، اگر ستونی داشته باشیم که تعداد زوجی خانهی سفید داشته باشد، باید تمام سطرها شامل تعداد فردی خانهی سیاه باشند.
راهنمایی
پس میتوانید کل حالات را در دو دسته بررسی کنید. تمام ستونها شامل فرد خانهی سفید و تمام سطرها شامل زوج خانهی سیاه باشند یا تمام ستونها شامل زوج خانهی سفید و تمام سطرها شامل فرد خانهی سیاه باشند.
راهنمایی
نشان دهید حالت اول راهنمایی پیشین، نمیتواند رخ دهد.
راهنمایی
برای حالت دوم راهنماییهای پیشین، عملیات انجام شده روی ۱۲ خانهی ابتدایی را در نظر گیرید.
راهنمایی
روی زوجیت تعداد خانههای سیاه و سفید ۱۲ خانهی ابتداییای که عملیات بر آنها انجام شده حالت بندی کنید.
پاسخ
گزینهی ۱ درست است.
یک خانه که ستونش را تغییر داده سفید و در غیر این صورت آن را سیاه میکنیم. اگر ستونی داشته باشیم که تعداد زوجی خانهی سفید داشته باشد، باید تمام سطرها شامل تعداد فردی خانهی سیاه باشند (تا خانههای آن ستون برابر ۱ شود). به همین ترتیب برای ستون با تعداد فردی خانهی سفید میتوان حکم مشابهی گفت. با در نظر گرفتن حکمی مشابه (با در نظر گرفتن یک سطر) نیز، نتیجه میگیریم تنها یکی از دو حالت زیر رخ میدهد:
$\qquad$ پس در هر صورت تنها خانهی رنگ نشده از جدول به طور یکتا رنگ میشود.
پس پاسخ برابر $2^{12} = 4096$ است.