اگر $A$ یک جدول باشد، خانه‌ی واقع در سطر $r$ و ستون $c$ از آن را با $A(r, c)$ نشان می‌دهیم. گوییم خانه‌ی $A(r_1, c_1)$ بر $A(r_2, c_2)$ رجحان دارد، هر گاه $r1 \le r2, c1 \le c2$ باشد. توجه کنید هر خانه بر خودش رجحان دارد!

فرض کنید $T$ یک جدول $m \times n$ باشد که خانه‌های آن با سیاه و سفید رنگ شده‌اند. گوییم جدول $S$ فرزند $T$ است، هرگاه پس از عمل زیر، تمام خانه‌های $T$ سفید شوند:

به ازای هر خانه‌ی سیاه $S$ مانند $S(r, c)$، رنگ تمام خانه‌هایی در جدول $T$ را که بر خانه‌ی $T(r, c)$ رجحان دارند، عوض می‌کنیم.

به راحتی می‌توانید بررسی کنید که هر جدول دقیقن یک فرزند دارد. حال فرض کنید فرزند $T$ را به دست آورده، سپس از جدول حاصل دوباره فرزند آن را بسازیم و همین طور ادامه دهیم. ثابت کنید پس از تعدادی مرحله جدول $T$ دوباره ساخته خواهد شد و تعداد مراحل طی شده تا ساختن دوباره‌ی $T$ به صورت توانی از 2 است.

• سوال قبل