المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:تئوری:سوال ۱۵

دومینو

یک صفحه‌ی $n\times n$ ( $n$ زوج)، را می‌توان با مهره‌های دومینو به طور کامل پوشاند به طوری که هیچ دومینویی روی دومینوی دیگری قرار نگرفته باشد.

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

ثابت کنید برای $n$ های زوج و $n\geq 8$ حداقل یک پوشش خوب برای صفحه‌ی $n\times n$ وجود دارد.


ابزار صفحه