المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۴:سوالات ۷ تا ۸

فهرست مندرجات

سوالات ۷ تا ۸

سوال ۷

راهنمایی

مانند سوال قبل باید یک کران بالا و یک کران پایین برای حداقل تعداد خانه‌های سیاه پیدا کنیم.
به سادگی می‌توان دید جواب مسئله کمتراز $2$ نیست.(چرا؟)
سعی کنید با رنگ کردن کمترین تعداد خانه، یک جدول سلطانی بسازید. دقت کنید، مثلاً اگر ادعا می‌کنید جواب مسئله $3$ است، باید نشان دهید با سیاه کردن $2$ خانه نمی‌توان یک جدول سلطانی ساخت.

سوال ۸

راهنمایی

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


ابزار صفحه