المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۶:سوال شش

جدول اصلاح‌پذیر

جدولی به اندازه‌ی $m \times n$ که در هر خانه‌اش ۰ یا ۱ نوشته شده موجود است. در هر مرحله مقدار خانه‌ها را به این صورت عوض می‌کنیم:

مقدار جدید یک خانه در مرحله‌ی $i+۱$ام ۱ است اگر و فقط اگر در مرحله‌ی $i$ام در خانه‌های هم‌سطر و هم‌ستونش (به جز خود آن خانه) تعداد فردی ۱ وجود داشته باشد.

توجه کنید که برای هر خانه $m+n-۲$ خانه‌ی دیگر هم‌سطر یا هم‌ستونش وجود دارد.

یک جدول را «اصلاح‌پذیر» می‌گوییم اگر با شروع از این جدول و چند مرحله انجام عمل فوق بر روی کلیه‌ی خانه‌های جدول دوباره به جدول اصلی برسیم. اگر $m$ و $n$ هر دو زوج باشند٬ تعداد جداول اصلاح‌پذیر با اندازه‌ی $m \times n$ را به دست آورید و ادعای خود را ثابت کنید.


ابزار صفحه