مبانی کمینه و بیشینه
در یک صفحه شطرنجی 4 در 4 حداکثر چند وزیر میشه قرار داد به طوری که همدیگه رو تهدید نکنند؟
یه سری سوال باحال هستند که حداکثر یا حداقل یه چیزی رو میخوان. مثلا توی سوال بالای صفحه، لازم بود حداکثر تعداد وزیر هارو حساب کنیم. توی این مدل مسئله ها باید دوتا چیز رو بدست بیاریم یکی "کران" و اون یکی "مثال". اگه خود مسئله بالای صفحه رو در نظر بگیریم باید اول اثبات کنیم بیشتر از x تا وزیر نمیشه گذاشت و بعدش یه مثال برای x تا وزیر بزنیم.
خب اگه همینجوری وزیر توی جدول بذاریم، میفهمیم که مثال برای گذاشتن سه تا وزیر میتونیم پیدا کنیم و از طرفی چون توی هر سطر حداکثر یه وزیر باید باشه و 4 تا سطر داریم پس حداکثر هم 4 تا وزیر میشه گذاشت. حالا سوال اینجاست که جواب 3 میشه یا 4.
اگه یکم دیگه سعی کنیم و وزیر ها رو جابه جا کنیم میتونیم به مثال 4 برسیم و مسئله حل میشه. 😂
| ⚪ | |||
| ⚪ | |||
| ⚪ | |||
| ⚪ |
به سوالات کمینه و بیشینه، اکسترمال ویا بهینگی هم میگن.
با 48 تا چوب کبریت شکل زیر را ساخته ایم. حداقل چند تا چوب کبریت لازمه حذف کنیم تا هیچ مربعی به طول واحد در شکل دیده نشه؟
بیشترین تعداد مربع به طول واحدی را پیدا کن که چوب کبریت مشترکی نداشته باشند. اینجوری باید از هر کدوم از اون مربع ها حداقل یک چوب کبریت برداری.
و بعدش یه مثال هم با اون تعداد ارائه بده.
پاسخ - 12
اون 12 تا مربع که حداقل یه چوب کبریتشون به سمت بیرون شکله را در نظر بگیر؛ هیچ دوتایی از این ها چوب کبریت مشترکی ندارند. پس باید حداقل 12 تا چوب کبریت از شکل حذف کنیم. حالا این هم مثالش:
می‌خواهیم رئوس گراف زیر را با قرمز و آبی رنگ کنیم. باید طوری این کار انجام شود که هر رأس (چه قرمز و چه آبی) دست‌کم یک رأس قرمز مجاور داشته باشد. توجه کنید در یک گراف دو رأس را مجاور گوییم، اگر با یک یال به هم وصل باشند. کمینه‌ی تعداد رأس‌های قرمز چیست؟
اول سعی کن یه مثال بزنی که توش کمترین تعداد راس ها قرمز شده باشند و بعدش اثبات کنی کمتر از اون نمیشه.
پاسخ - 2
همون طور که توی شکل میبینید یه مثال زدیم که توش 2 تا راس قرمز شده. حالا ثابت میکنیم با کمتر از 2 راس نمیشه.
اگه قرار باشه فقط یک راس قرمز باشه، خود اون راس، مجاور قرمز نخواهد داشت؛ پس حداقل 2 راس باید قرمز باشند.
توی شکل زیر 16 تا قطرک قرار بدید به طوری که هیچ دوتا قطرکی با هم متقاطع نباشند (حتی اگه در یکی از سر هاشون هم به هم برسند، متقاطع حساب میشوند)
قطرک: قطر اصلی یا فرعی هر مربع به طول واحد. (پس تعداد کل قطرک های این شکل برابر 50 تاست)
یک جدول 4×4 داریم که ابتدا تمام خانه‌های آن سفید است. دو خانه را مجاور می‌گوییم، اگر در یک ضلع مشترک باشند. قلمرو هر خانه عبارت است از خود آن خانه و تمامی خانه‌های مجاورش. بنابراین قلمرو هر خانه شامل حداکثر 5 خانه است. در هر مرحله می‌توان تعدادی از خانه‌های قلمرو یک خانه را انتخاب کرد و رنگ آن‌ها را تغییر داد (از سفید به سیاه و برعکس). در حداقل چند مرحله می‌توان تمام خانه‌های جدول را سیاه کرد؟
بیشترین تعداد خانه رو پیدا کنید که هیچ دوتای آن ها در یک قلمرو نباشند.
پاسخ - 4
این مثال برای 4 تاش.
حالا اگه 4 تا خونه ی گوشه رو در نظر بگیری میفهمی که هیچ دوتاییشون توی یک قلمرو نیستند؛ پس حداقل 4 مرحله نیازه.
سوال قبل را در نظر بگیرید، با این تفاوت که این بار در هر مرحله می‌توان یک خانه انتخاب کرد و رنگ دقیقا سه خانه از قلمرو آن را تغییر داد. در این صورت کمترین تعداد مراحل لازم برای سیاه کردن تمام خانه‌های جدول چقدر است؟
حواست به این باشه که هر خونه میتونه توسط چند تا قلمرو، چندین بار تغییر رنگ بده.
پاسخ - 6
چون توی هر مرحله رنگ حداکثر 3 تا خونه تغییر میکنه و جدول شامل 16 تا خونه ست پس حداقل 6 مرحله لازمه. (چون با 5 مرحله، رنگ حداکثر 15 تا خونه سیاه میشه)
این هم مثال برای 6 مرحله.
2 |
1 3 2 |
1 |
1 |
2 |
3 |
6 |
6 |
4 |
3 |
6 |
5 |
4 |
4 |
5 |
5 |
شکل زیر، یک جدول 5×5 با حذف چهار گوشه‌ی آن است. می‌خواهیم این شکل را به طور کامل با کاشی‌های 1×1, 2×2, 3×3 بپوشانیم، طوری که کاشی‌ها روی هم قرار نگرفته و از جدول بیرون نزنند. نیازی نیست از هر سه نوع کاشی استفاده کنیم. حداقل تعداد کاشی‌ها برای انجام این کار چیست؟
از کاشی 3×3 استفاده نکن.
پاسخ - 9
ابتدا مثالی ارائه میدهیم.
حالا ثابت میکنیم با کمتر از 9 تا نمیشه.
- یا اینکه از کاشی
3در3استفاده میکنیم:
که در این صورت اگه کاشی3در3در وسط جدول باشه، بقیه خونه ها باید با کاشی های1در1پر بشن. اینطوری به13تا کاشی نیاز داریم. اگه هم که کاشی3در3در وسط جدول نباشه، حداکثر میشه یه کاشی2در2قرار داد و بقیه باید با کاشی1در1پر بشن. اینجوری هم حداقل به10تا کاشی نیاز داریم. - یا اینکه از کاشی
3در3استفاده نمیکنیم:
اینطوری خانه های مشخص شده در شکل زیر توسط حداکثر یک کاشی پوشانده میشه، پس حداقل به9تا کاشی نیاز داریم.
