Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

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


ابزار صفحه