آیکون منو
007

مبانی کمینه و بیشینه

مسئله

در یک صفحه شطرنجی 4 در 4 حداکثر چند وزیر میشه قرار داد به طوری که همدیگه رو تهدید نکنند؟

 


یه سری سوال باحال هستند که حداکثر یا حداقل یه چیزی رو میخوان. مثلا توی سوال بالای صفحه، لازم بود حداکثر تعداد وزیر هارو حساب کنیم. توی این مدل مسئله ها باید دوتا چیز رو بدست بیاریم یکی "کران" و اون یکی "مثال". اگه خود مسئله بالای صفحه رو در نظر بگیریم باید اول اثبات کنیم بیشتر از x تا وزیر نمیشه گذاشت و بعدش یه مثال برای x تا وزیر بزنیم.

خب اگه همینجوری وزیر توی جدول بذاریم، میفهمیم که مثال برای گذاشتن سه تا وزیر میتونیم پیدا کنیم و از طرفی چون توی هر سطر حداکثر یه وزیر باید باشه و 4 تا سطر داریم پس حداکثر هم 4 تا وزیر میشه گذاشت. حالا سوال اینجاست که جواب 3 میشه یا 4.

اگه یکم دیگه سعی کنیم و وزیر ها رو جابه جا کنیم میتونیم به مثال 4 برسیم و مسئله حل میشه. 😂

 

     
     
     
     

 

به سوالات کمینه و بیشینه، اکسترمال ویا بهینگی هم میگن.

مسئله

با 48 تا چوب کبریت شکل زیر را ساخته ایم. حداقل چند تا چوب کبریت لازمه حذف کنیم تا هیچ مربعی به طول واحد در شکل دیده نشه؟

 

48 تا چوب کبریت - کمینه و بیشینه - بهینگی - مرحله اول المپیاد کامپیوتر - ببعییی

 


مسئله

می‌خواهیم رئوس گراف زیر را با قرمز و آبی رنگ کنیم. باید طوری این کار انجام شود که هر رأس (چه قرمز و چه آبی) دست‌کم یک رأس قرمز مجاور داشته باشد. توجه کنید در یک گراف دو رأس را مجاور گوییم، اگر با یک یال به هم وصل باشند. کمینه‌ی تعداد رأس‌های قرمز چیست؟

 

مبانی کمینه و بیشینه (اکسترمال)

 


مسئله

توی شکل زیر 16 تا قطرک قرار بدید به طوری که هیچ دوتا قطرکی با هم متقاطع نباشند (حتی اگه در یکی از سر هاشون هم به هم برسند، متقاطع حساب میشوند)

قطرک: قطر اصلی یا فرعی هر مربع به طول واحد. (پس تعداد کل قطرک های این شکل برابر 50 تاست)

 

         
         
         
         
         

 


مسئله

یک جدول 4×4 داریم که ابتدا تمام خانه‌های آن سفید است. دو خانه را مجاور می‌گوییم، اگر در یک ضلع مشترک باشند. قلمرو هر خانه عبارت است از خود آن خانه و تمامی خانه‌های مجاورش. بنابراین قلمرو هر خانه شامل حداکثر 5 خانه است. در هر مرحله می‌توان تعدادی از خانه‌های قلمرو یک خانه را انتخاب کرد و رنگ آن‌ها را تغییر داد (از سفید به سیاه و برعکس). در حداقل چند مرحله می‌توان تمام خانه‌های جدول را سیاه کرد؟

 


مسئله

سوال قبل را در نظر بگیرید، با این تفاوت که این بار در هر مرحله می‌توان یک خانه انتخاب کرد و رنگ دقیقا سه خانه از قلمرو آن را تغییر داد. در این صورت کم‌ترین تعداد مراحل لازم برای سیاه کردن تمام خانه‌های جدول چقدر است؟

 


مسئله

شکل زیر، یک جدول 5×5 با حذف چهار گوشه‌ی آن است. می‌خواهیم این شکل را به طور کامل با کاشی‌های 1×1, 2×2, 3×3 بپوشانیم، طوری که کاشی‌ها روی هم قرار نگرفته و از جدول بیرون نزنند. نیازی نیست از هر سه نوع کاشی استفاده کنیم. حداقل تعداد کاشی‌ها برای انجام این کار چیست؟

 

کمینه و بیشینه - سوال - مرحله اول المپیاد کامپیوتر - ببعییی

 


منابعی برای مطالعه بیشتر

آزمون دوم - گراف و کمینه و بیشینه