====== سوالات ۱۰ و ۱۱ ======




یک جدول
$n \times n$
که رنگ هر خانه‌ی آن سفید یا سیاه است را
**قوی**
می‌نامیم، اگر و تنها اگر هیچ یک از اشکال زیر در خانه‌های سفید جدول دیده نشود:


{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:capture2.png |}}

====== سوال ۱۰ ======



کمینه‌ی تعداد خانه‌های سیاه را میان تمامی جدول‌های $5 \times 5$ ‌‌قوی بیابید. 



  - 3
  - 1
  - 2
  - 4
  - 5







<پاسخ>
گزینه (۱) درست است.




شکل مطرح شده در صورت سؤال را شکل //H// می‌نامیم.

لم: برای اینکه یک جدول $3 \times 4$ قوی باشد، حداقل ۲ خانه باید سیاه باشند. یک جدول بدون خانه‌ی سیاه قوی نیست. فرض کنید یک جدول با یک خانه‌ی سیاه قوی شده است. پس در ستون اول و آخر این جدول خانه‌ی سیاه قرار ندارد، زیرا در این صورت در ۳ ستون دیگر //H// دیده می‌شود. پس با توجه به تقارن، فرض کنید خانه‌ی سیاه در ستون دوم است.


{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled5.png |}}



با توجه به شکل بالا، باید ردیف وسط این ستون سیاه باشد. در این صورت با توجه به شکل زیر، یک \lr{H} وجود دارد و به تناقض می‌رسیم.


{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled6.png |}}


با توجه به لم مطرح شده، برای قوی بودن یک جدول $5 \times 5$ حداقل ۲ خانه باید سیاه باشند. حال فرض کنید یک جدول قوی $5 \times 5$ با ۲ خانه‌ی سیاه وجود دارد. طبق لم می‌دانیم در قسمت زرد هر یک جدول‌های زیر حداقل ۲ خانه‌ی سیاه وجود دارد.




{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled7.png |}}



پس ۲ خانه‌ی سیاه در جدول باید در تمامی قسمت‌های زرد باشند. اما این ۴ قسمت زرد فقط در خانه‌ی مرکزی جدول اشتراک دارند. پس به تناقض می‌رسیم.

یک جدول قوی حداقل ۳ خانه‌ی سیاه لازم دارد. مثالی از یک جدول قوی در شکل زیر نشان داده شده است:



{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled8.png |}}

</پاسخ>



====== سوال ۱۱ ======



کمینه‌ی تعداد خانه‌های سیاه را میان تمامی جدول‌های $7 \times 7$ ‌‌قوی بیابید. 



  - 8
  - 5
  - 6
  - 7
  - 9




<پاسخ>
گزینه (۱) درست است.






شکل مطرح شده در صورت سؤال را شکل //H// می‌نامیم.

به شکل زیر توجه کنید:



{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled9.png |}}


با توجه به لم مطرح شده در سؤال قبل برای اینکه در این زیر مستطیل‌ها //H// دیده نشود، در هر یک از رنگ‌ها باید ۲ خانه سیاه باشد. پس در مجموع به حداقل ۸ خانه‌ی سیاه احتیاج داریم. مثالی از یک جدول قوی با ۸ خانه‌ی سیاه را در شکل زیر مشاهده می‌کنید:


{{ :سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۳۰:untitled10.png |}}




</پاسخ>




  * [[سوال ۹|سوال قبل]]
  * [[سوالات ۱۲ و ۱۳ و ۱۴|سوال بعد]]