====== سوالات ۲۷ و ۲۸ ======

اخیرا در پی آزمایش‌های هسته‌ای در مجمع‌الجزایر پنیر، جنگی بین دو کشور پنیر ‌شمالی و پنیر ‌جنوبی در گرفته است. در این مجمع الجزایر ۱۰ جزیره وجود دارد که  این دو کشور در پی تصرف آن‌ها هستند. در این جنگ هر یک از دو کشور به هر جزیره تعدادی نیرو اعزام می‌کند و در هر جزیره کشوری که نیروی بیش‌تری اعزام کرده باشد، پیروز نبرد خواهد شد و اگر تعداد نیرو‌ها مساوی باشد جزیره به هیچ یک از دو کشور تعلق نخواهد گرفت. اما همه می‌دانند که کشور پنیر ‌جنوبی با همکاری کشور‌های دیگر به تکنولوژی‌ای دست یافته که می‌تواند تعداد نیرو‌هایی که طرف مقابل به هر جزیره ارسال می‌کند را پیش‌بینی کند و بر اساس آن نیروهای خود را به جزیره‌ها بفرستد. می‌دانیم هر یک از دو کشور بهترین شیوه را برای تصاحب بیش‌ترین تعداد جزیره‌ به کار می‌بندند.

با توجه به توضیحات بالا به ۲ سؤال زیر پاسخ دهید.


====== سوال ۲۷ ======

اگر کشور پنیر شمالی ۱۰۰ نیرو و کشور پنیر ‌جنوبی ۴۵ نیرو در اختیار داشته‌ باشد. کشور پنیر شمالی حداکثر چند جزیره را می‌تواند تصاحب کند؟



  - ۷
  - ۳
  - ۴
  - ۵
  - ۶
/*
<راهنمایی>
فرض کنید به ترتیب کم به زیاد پنیر شمالی $a_1$ تا $a_{10}$ نیرو فرستاده باشد.
اگر پنیر جنوبی بتواند $t$ کشور را تصاحب کند، حداقل تعداد نیرو‌های فرستاده شده توسط پنیر جنوبی به کشور‌های تصاحب شده چقدر است؟ 
این مقادیر را برای حالت‌های مختلف t بررسی کنید.
</راهنمایی>

<راهنمایی>
با توجه به مقادیر فوق، در هر حالت از t، حداقل مجموع نیروهای لازم برای هر دو کشور را نیز بررسی کنید.
</راهنمایی>

<راهنمایی>
برای اثبات کران بالای خود، باید یک مثال ارائه دهید. برای ساخت مثال مورد نظر، سعی کنید از همان مراحلی که برای محاسبه کران بالا استفاده کردید کمک بگیرید و مقدار $a_1$ تا $a_{10}$ را یک به یک از کم به زیاد تعیین کنید.
</راهنمایی>
*

<پاسخ>

 گزینه‌ی ۵ درست است.

چون کشور پنیر ‌جنوبی از نحوه‌ی چینش کشور پنیر ‌شمالی اطلاع می‌یابد 
یک استراتژی بهینه برای آن این است که همیشه سعی کند جزیره‌هایی که کمترین نیرو را دارند اشغال کند.
اما می‌دانیم مجموع تعداد نیروهایی که پنیر ‌شمالی به چهار جزیره‌ای که کم‌ترین نیروها را دارند اعزام کرده است 
حداکثر ۴۰ است (چرا؟). 
در نتیجه کشور پنیر ‌جنوبی می‌تواند حداقل ۴ جزیره را تصاحب کند. 
اما اگر کشور پنیر ‌شمالی به هر جزیره دقیقا ۱۰ نیرو اعزام کند پنیر ‌جنوبی نمی‌تواند 
بیش‌تر از ۴ جزیره‌ را تصاحب کند و در نتیجه پنیر ‌شمالی می‌تواند ۶ جزیره را تصاحب کند.
</پاسخ>
====== سوال ۲۸ ======

اگر کشور پنیر ‌جنوبی ۴۵ نیرو در اختیار داشته باشد، کشور پنیر ‌شمالی حداقل چند نیرو باید داشته باشد تا مطمئن باشد که نیمی از جزیره‌ها را تصاحب می‌کند؟



  - ۶۸
  - ۶۹
  - ۷۰
  - ۷۳
  - ۷۵ 
/*
<راهنمایی>
فرض کنید به ترتیب کم به زیاد پنیر شمالی $a_1$ تا $a_{10}$ نیرو فرستاده باشد.
اگر پنیر جنوبی نتواند ۶ کشور را تصاحب کند، حداقل تعداد نیرو‌های فرستاده شده به کشور‌های تصاحب شده چقدر است؟ مجموع نیرو‌های لازم برای ۶ کشور با کمترین تعداد نیرو از پنیر شمالی چقدر باید باشد؟
</راهنمایی>

<راهنمایی>
با توجه به مقادیر فوق، حداقل مجموع نیروهای لازم برای هر دو کشور را نیز بررسی کنید.
</راهنمایی>

<راهنمایی>
برای اثبات کران پایین خود، باید یک مثال ارائه دهید. برای ساخت مثال مورد نظر، سعی کنید از همان مراحلی که برای محاسبه کران پایین استفاده کردید کمک بگیرید و مقدار $a_1$ تا $a_{10}$ را یک به یک از کم به زیاد تعیین کنید.
</راهنمایی>
*
<پاسخ>

 گزینه‌ی ۲ درست است.


اگر پنیر ‌شمالی در هر جزیره ۷ نیرو قرار دهد، پنیر ‌جنوبی حداکثر می‌تواند ۵ جزیره را اشغال کند. 
اما پنیر ‌شمالی می‌تواند در یک جزیره ۶ نیرو قرار دهد به طوری که باز هم پنیر ‌جنوبی نتواند بیش‌تر از ۵ جزیره را اشغال کند. 
با استفاده از اصل لانه‌کبوتری می‌توان نشان داد که پنیر ‌شمالی با کمتر از ۶۸ نیرو نمی‌تواند این کار را انجام دهد،
چون در این صورت پنیر ‌جنوبی با ۴۵ نیرو می‌تواند حداقل ۶ جزیره‌ را تصاحب کند (چرا؟). 
البته با ۶۸ نیرو اگر چه پنیر ‌جنوبی نمی‌تواند بیش‌تر از ۵ جزیره را تصاحب کند 
اما پنیر ‌شمالی هم نمی‌تواند مطمئن باشد که ۵ جزیره را تصاحب می‌کند،
زیرا ممکن است در یکی از جزایر تساوی رخ دهد.
</پاسخ>
  * [[سوالات ۲۹ و ۳۰|سوال بعد]]
  * [[سوالات ۲۵ و ۲۶|سوال قبل]]