فهرست مندرجات
سوالات ۱۰ و ۱۱
یک جدول $n \times n$ که رنگ هر خانه‌ی آن سفید یا سیاه است را قوی می‌نامیم، اگر و تنها اگر هیچ یک از اشکال زیر در خانه‌های سفید جدول دیده نشود:
سوال ۱۰
کمینه‌ی تعداد خانه‌های سیاه را میان تمامی جدول‌های $5 \times 5$ قوی بیابید.
- 3
- 1
- 2
- 4
- 5
پاسخ
گزینه (۱) درست است.
شکل مطرح شده در صورت سؤال را شکل H می‌نامیم.
لم: برای اینکه یک جدول $3 \times 4$ قوی باشد، حداقل ۲ خانه باید سیاه باشند. یک جدول بدون خانه‌ی سیاه قوی نیست. فرض کنید یک جدول با یک خانه‌ی سیاه قوی شده است. پس در ستون اول و آخر این جدول خانه‌ی سیاه قرار ندارد، زیرا در این صورت در ۳ ستون دیگر H دیده می‌شود. پس با توجه به تقارن، فرض کنید خانه‌ی سیاه در ستون دوم است.
با توجه به شکل بالا، باید ردیف وسط این ستون سیاه باشد. در این صورت با توجه به شکل زیر، یک \lr{H} وجود دارد و به تناقض می‌رسیم.
با توجه به لم مطرح شده، برای قوی بودن یک جدول $5 \times 5$ حداقل ۲ خانه باید سیاه باشند. حال فرض کنید یک جدول قوی $5 \times 5$ با ۲ خانه‌ی سیاه وجود دارد. طبق لم می‌دانیم در قسمت زرد هر یک جدول‌های زیر حداقل ۲ خانه‌ی سیاه وجود دارد.
پس ۲ خانه‌ی سیاه در جدول باید در تمامی قسمت‌های زرد باشند. اما این ۴ قسمت زرد فقط در خانه‌ی مرکزی جدول اشتراک دارند. پس به تناقض می‌رسیم.
یک جدول قوی حداقل ۳ خانه‌ی سیاه لازم دارد. مثالی از یک جدول قوی در شکل زیر نشان داده شده است:
سوال ۱۱
کمینه‌ی تعداد خانه‌های سیاه را میان تمامی جدول‌های $7 \times 7$ قوی بیابید.
- 8
- 5
- 6
- 7
- 9
پاسخ
گزینه (۱) درست است.
شکل مطرح شده در صورت سؤال را شکل H می‌نامیم.
به شکل زیر توجه کنید:
با توجه به لم مطرح شده در سؤال قبل برای اینکه در این زیر مستطیل‌ها H دیده نشود، در هر یک از رنگ‌ها باید ۲ خانه سیاه باشد. پس در مجموع به حداقل ۸ خانه‌ی سیاه احتیاج داریم. مثالی از یک جدول قوی با ۸ خانه‌ی سیاه را در شکل زیر مشاهده می‌کنید:
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
