اصل اکسترمال




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


اصل اکسترمال

ریاضی دان ورزیده مجهز به یک سری اصول و فنون با دامنه کاربرد وسیع وساده می باشد که می تواند از آنها در حالت های مختلف استفاده نمایید. این اصول و فنون وابسته به موضوعی ویژه نبوده و در کلیه شاخه های ریاضی قابلیت استفاده را دارند. ریاضی دان به این اصول فکر نمی کند بلکه به طور ناخودآگاه از آن مطلع می باشد یکی از این اصول ، ناوردایی بود که در فصل اول از آن بحث شد و اما اصل اکسترمال زمانی که بحث درباره تبدیلات است مورد استفاده واقع می شود. « وقتی شما تبدیل دارید به دنبال ناوردایی باشید.» در این فصل به بحث درباره اصل اکسترمال خواهیم پرداخت که دارای کاربردهای پردامنه ای می باشد که باید با تمرین زیاد آن را به خاطر سپرد. به این اصل روش «متغیر» هم گفته می شود. با این روش می توان به اثبات های بسیار آسان دست یافت.
ابتدا سعی می کنیم وجود یک حالت را به اثبات برسانیم. اصل اکسترمال به ما می گوید که با انتخاب این حالت سعی کنید برخی حالت های ماکزیمم و مینیمم آن را بررسی کنید. حالت حاصل نشان دهنده تقریبی وضعیت خواسته شده است هر چند کاملاً با آن منطبق نمی نماید ولی با کمی تغییر روی توابع به حالت اصلی می توان رسید. اگر راه های مختلفی برای بهینه سازی وجود داشته باشد انتخاب یکی از آنها بسته به نظر ما می باشد. اصل اکسترمال بسیار خلاق است و می تواند الگوریتم روش ساختن آن حالت را به ما نشان دهد.
در این بحث به حل چیدین مثال به کمک اصل اکسترمال در زمینه های هندسه، نظریه گراف، ترکیبیات، نظریه اعداد خواهیم پرداخت، اما در ابتدا به سه اصل معروف می پردازیم.
الف.هر مجموعه محدود نامشخصی مثل از اعداد صحیح یا حقیقی دارای یک عنصر مینیمم و یک عنصر ماکسیمم است .
ب.هر زیرمجموعه غیر تهی از اعداد صحیح مثبت دارای کوچک ترین عضو است. این را « اصل خوش ترتیبی» می نامند .
ج.مجموعه نامحدود از اعداد حقیقی ضرورتاً دارای عضو ماکسیمال یا مینیمال نیست. اگر از بالا کران دار باشد، آنگاه دارای کوچک ترین کران بالاست که آن را سوپریمم می نامیم. اگر از پایین کران دار باشد دارای بزرگترین کران پایین است و آن را اینفیمم می نامیم.
اگر باشد آنگاه و اگر آنگاه .



مثال

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


درواقع در این استدلال هیچ اشکالی نیست چون رابطه بازگشتی پایه و اساس این شیوه تفکر است یک مسأله حل کن تجربه گرا ممکن است مسأله را در ذهن خود حل نماید. در حالت (الف) ما به شماره کردن مسأله می پردازیم. یکی از اصول شمارشی اساسی تناظر یک به یک برقرار کردن است.
img/daneshnameh_up/c/c1/com0039a.jpg

اولین سوال این است آیا می توان بخش از صفحه را به صورت یک به یک به مجموعه ای مربوط ساخت که به آسانی بتوان آن را شمرد؟ ترکیب نقطه برخورد خط را به آسانی می توان یافت. اما پایین برخورد دقیقاً در یک بخش وجود دارد (اصل اکسترمال) بنابراین بخش را با یک نقطه اشتراک داریم، بخش ها بدون نقاط اشتراک در کران پایین واقع نمی شوند، و یک خط افقی را به قسمت تقسیم می کند مانند شکل بالا.
این بخش ها را می توان به طور منحصر به فرد به این نقطه خط ها نسبت داد. بنابراین یا قسمت بدون یک نقطه اشتراک وجود دارد. بنابراین در مجموع داریم

ب. سه صفحه یک راس در فضا می سازند. پس راس وجود دارد که با یک نقطه اشتراک یک بخش از فضا را می سازند. پس بخش با یک نقطه اشتراک پایین داریم هر بخش با یک راس مشترک یک صفحه افقی را به قطعه صفحه تقسیم می نماید. بنابراین در بخش های فضا عبارتند از

مثال



ادامه بخش ب: فرض کنیم نشان دهید در بین بخش از فضا حداقل چهاروجهی وجود دارد ().
حل
بررسی نتیجه مسأله را ساده تر می کند. یک مسأله حل کن با تجربه اغلب با توجه به نتیجه به جستجوی راه حل مسأله می پردازد. فرض کنیم تعداد چهاروجهی هایی باشد که در بخش از فضا وجود دارند. پس باید ثابت کنیم که حدس عددی به ما می گوید که روی صفحه حداقل دو چهاروجهی وجود دارد. بنابراین این تعداد باید بر 4 بخش پذیر باشد. با توجه به استدلال فوق به راحتی می توان راه حل مسأله را یافت. فرض کنیم یکی از صفحه باشد. این صفحه فضا را به دو نیم فضای و تقسیم می نماید. حداقل یکی از نیم فضاها مثلاً شامل راس های می باشد. در ما راس را کمترین فاصله نسبت به در نظر می گیریم (اصل اکسترمال) فصل مشترک صفحات ، و می باشد و بنابراین ، ، و یک چهاروجهی مانند تعریف می کند به شکل مقابل.
img/daneshnameh_up/d/d6/com0039b.jpg

هیچ یک از صفحه باقی مانده با تقاطع ندارد. بنابراین یکی از بخش ها بوده که به وسیله صفحه به وجود آمده است. اگر صفحه ای مانند چهاروجهی را قطع نماید، بنابراینe' باید یکی از یال های ، و را در نقطه ای مانند قطع نماید که فاصله کمتری از تا دارد و این تناقض است.
مطلب فوق برای هر صفحه صادق است. حال اگر رئوس در هر دو طرف یک صفحه باشند، پس حداقل دو چهاروجهی به وجود می آیند. حال کافی است نشان دهیم در این صفحه سه چهاروجهی وجود دارد که تمام رئوس آن در یک طرف صفحه واقع می باشند.
این مطلب را با مثال نقیض ثابت می کنیم. فرض کنیم چهار صفحه ، ، و وجود داشته باشد. آنها چهاروجهی را ناحیه بندی می کنند. شکل زیر
img/daneshnameh_up/5/54/com0039c.jpg

این صفحه نمی تواند هر شش یال چهاروجهی را قطع نماید. فرض کنیم امتداد را در نقطه قطع نماید. پس و در دو طرف مختلف صفحه واقع می شود که یک تناقض است.



مثال

نقطه در یک صفحه واقع می باشند. هر سه نقطه ای یک مثلث با مساحتی نابیشتر از یک دارند. ثابت نمایید تمام این نقاط در مثلثی به مساحت نابیشتر از 4 وافع می باشند.
img/daneshnameh_up/b/b3/com0039d.jpg

حل
در بین تمام نقاط سه نقطه ، و را در نظر می گیریم که مساحت آن ماکزیمم باشد. واضح است که . از رئوس مثلث سه خط به موازات اضلاع مقابل مثلث رسم می کنیم. مثلث به دست می آید که مساحت آن است . ثابت خواهیم کرد مثلث در بردارنده تمام نقطه می باشند. فرض کنیم یک نقطه مثل در خارج مثلث واقع باشد پس مثلث و نقطه در یک طرف یکی از سه ضلع مثلث مثلاً واقع می باشند. پس مثلث مساحتی پیش از مثلث خواهد داشت. این یک تناقض دربازه ماکسیمال بودن مساحت مثلث می باشد.

مثال

نقطه در یک صفحه مفروضند که هیچ سه تایی از آنها بر یک خط راست واقع نمی باشند. تا از این نقطه ها مزرعه های را می سازند. نقطه باقیمانده چاه های را می سازند. از ما خواسته شده جاده ای مستقیم بسازیم که هر چاه را به یک مزرعه وصل نماید. ثابت کنید این جاده ها می توانند طوری ساخته شوند که هیچ یک دیگری را قطع نکند.
حل
یک نگاشت یک به یک تعریف می کنیم. اگر ما از هر مزرعه یک جاده مستقیم را بسازیم، سیستم جاده ها را طراحی کرده ایم. فرض کنیم در بین همه جاده یکی را که کوتاه ترین راه را دارد انتخاب کرده باشیم. فرض کنیم این سیستم جاده ها قطعه خط های متقاطعی مانند و داشته باشند به شکل مقابل این جاده ها را با جاده های و جایگزین می کنیم، مجموع طول جاده ها به خاطر نامساوی مثلثی کوتاه تر می شود، بنابراین این جاده خواسته شده نیست.
img/daneshnameh_up/4/48/com0039e.jpg




مثال

مجموعه نقاطی از صفحه است. هر نقطه وسط دو نقطه دیگر است. ثابت کنید مجموعه ای نامحدود است.
اثبات اول
فرض کنیم یک مجموعه محدود باشد. آنگاه شامل دو نقطه مانند و است که فاصله آنها ماکسیمال باشد. حال اگر نقطه وسط دو نقطه و از باشد مطابق شکل مقابل یا .
img/daneshnameh_up/f/f2/com0039f.jpg

اثبات دوم
فرض کنیم تمام نقاط در طرف چپ و نقطه دورترین نقطه آن باشد. نقطه نمی تواند نقطه میانی و متعلق به باشد چون یک عضو باز در طرف چپ نقطه واقع می شود که ناممکن است.

مثال

در یک پنج ضلعی محدب می توان سه قطر انتخاب کرد که اضلاع یک مثلث باشند.
img/daneshnameh_up/3/34/com0039g.jpg

حل
فرض کنیم بزرگترین قطر پنج ضلعی باشد نامساوی مثلثی ایجاب می کند که

بنابراین با ، و می توان یک مثلث ساخت.

مثال

در چهاروجهی با سه یال همرس می توان یک مثلث ساخت.
حل
فرض کنیم بزرگترین یال باشد. آنگاه

پس یا یا .



مثال

نقاط شبکه ای صفحه با اعداد صحیح مثبت نام گذاری شده اند. هر نقطه ای واسطه حسابی از چهار نقطه کناری خود است (بالا، پایین، راست، چپ).
ثابت کنید تمام اعداد شماره گذاری شده با هم برابرند.
حل
کوچکترین شماره گذاری را می گیریم که مربوط به نقطه است. در همسایگی وجود دارند، آنگاه
(1)

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

که با رابطه (1) متناقض می باشد بنابراین

بنابراین تمام شماره گذاری برابر خواهد بود.
این مسأله ساده بود، اما با جایگزین کردن اعداد حقیقی مثبت به جای اعداد صحیح مثبت مسأله بسیار پیچیده می شود. چون اعداد حقیقی ایجاب نمی نماید که کوچک ترین عضو را داشته باشند. در حالی که برای اعداد صحیح مثبت به خاطر اصل خوش ترتیبی این موضوع الزام آور است. ولی می دانیم مسأله در این حالت درست است ولی راه حل ساده ای برای آن وجود ندارد.

مثال

ثابت کنید برای اعداد صحیح مثبت معادله زیر جواب ندارد.

حل
فرض کنیم معادله جواب داشته باشد. می توان فرض کرد که با کوچک ترین مسأله حل شده باشد. حال اگر جواب های معادله باشند داریم:


بنابراین یک عده جواب دیگر به صورت به دست آورده ایم که
که یک تناقض است.
در راه حل از این موضوع سود بردیم که

این حکم را خودتان ثابت کنید.



مثال. مسأله سیلوستر

این مسأله به وسیله سیلوستر در سال 1893 طرح شد و در سال 1933 توسط گالی به روش پیچیده ای حل گردید و سپس در سال 1948 در چند خط با اصل اکسترمال توسط کلی حل گردیده است.
مجموعه محدود شامل نقاطی از صفحه است که هر خط گذرنده از دو نقطه از نقطه سومی نمی گذرد. ثابت کنید تمام نقاط روی یک خط واقع می باشند.
حل
فرض کنیم این نقاط هم خط نیستند. زوج عبارت است از خطی مانند و نقطه ای مانند غیرواقع بر . حال نقطه ای را درنظر می گیریم کمه فاصله اش از خط مینیمم باشد. فرض کنیم پای عمودی است که از نقطه بر خط وارد شده است. بنابراین بنا بر فرض حداقل سه نقطه بر خط قرار دارد. فرض کنیم دو نقطه مثلاً و در یک طرف واقع باشند به شکل مقابل
img/daneshnameh_up/6/6b/com0039h.jpg

و فرض کنیم به تا نزدیک تر باشد آنگاه فاصله تا کمتر از می باشد و این تناقض است.

مثال

در کشور اسکانیا هر شهری به شهر دیگر فقط به وسیله یک جاده یک طرفه وصل شده است. ثابت کنید شهری وجود دارد که از هر شهری به آن مستقیم و یا حداکثر به واسطه یک شهر دیگر می توان رسید.
img/daneshnameh_up/8/86/com0039i.jpg
شکل 9

حل
فرض کنیم حداکثر جاده های منتهی به یک شهر باشد. و فرض کنیم شهری باشد که حداکثر جاده ها به آن وصل شده باشد. فرض کنیم مجموعه شهری باشد که به متصل هستند. و فرض کنیم مجموعه تمام شهرهای نامتصل به و موجود در باشد. اگر باشد پس شهری مانند وجود دارد که از طریق آن می توان به رسید یعنی

اگر چنین وجود نداشته باشد، پس به شهر می توان از طریق شهرهای و از رسید بنابراین جاده به منتهی می شود که یک تناقض نسبت به فرض در مورد است. بنابراین به هر شهر به طور حداکثر به حالت حکم مسأله می توان رسید.



مثال

رخ هایی روی صفحه شطرنج قرار دارند. واضح است که رخ کمترین تعداد رخی می باشد که تمام خانه های شطرنج را تهدید می نماید. اما درباره چه می توان گفت که بتوانند خانه های شطرنج را تهدید کند.
حل
ابتدا سعی می کنیم کوچکترین را حدس بزنیم. اما در ابتدا باید بدانیم که قرار گرفتن رخ ها در فضا چگونه صورت می گیرد. ردیف روی مربع های قرار می دهیم و آنها را با اعداد شماره گذاری می کنیم. هر رخ شماره ای را دارد که در آن ردیف واقع است. شکل زیر حالت هایی را که به حدس زدن کمک می نماید نشان می دهد
img/daneshnameh_up/e/e2/com0039j.jpg

img/daneshnameh_up/8/8a/com0039k.jpg

حال باید حدس خود را اثبات کرد. فرض کنیم رخ در مکعب های قرار گرفته اند و تمام مکعب های درونی را تهدید کرده اند. ما ردیف را انتخاب می کنیم در این ردیف تعداد رخ ها حداقل است. فرض کنیم این ردف با صفحه موازی باشد. اگر ردیف دارای رخ باشد می توان فرض کرد که رخ ردیف را در جهت تهدید می کند و تهدید می نماید و همچنین فرض می کنیم که . واضح است که و . در ردیف این رخ ها نمی توانند خانه را تهدید نمایند چون آنها در جهت می باشند. حال تمام ردیف موازی صفحه را درنظر می گیریم. در هیچ رخی از ردیف وجود ندارد، چون باید حداقل رخ داشته باشیم. پس در ردیف های حداقل رخ وجود دارد پس

سمت راست تساوی وقتی مینیمم است که برای های زوج داشته باشیم و برای های فرد داشته باشیم ، به سادگی دیده می شود این تعداد بنابر شکل زیر کفایت دارد.
img/daneshnameh_up/2/2f/com0039l.jpg


مثال

هفت کوتوله دور یک میز دایره ای نشسته اند. در مقابل هر یک، یک فنجان قرار دارد. در بعضی از فنجان ها شیر وجود دارد که مجموع آنها 3 لیتر است. یکی از کوتوله ها شیر فنجان خود را به طور مساوی در سایر فنجان ها ریخت. در جهت عکس عقربه های ساعت سایر کوتوله ها هم همین کار را انجام دادند. بعد از اینکه هفتمین کوتوله این عمل را انجام داد در هر فنجان به اندازه اولیه شیر وجود داشت تعیین کنید در هر فنجان در ابتدا چقدر شیر بوده است.


حل
جواب صحیح و صفر است. حدس زدن این جواب ها اصل ناوردایی آسان است.
فرض کنیم کوتوله ماکزیمم مقدار شیر به اندازه را قبل از عمل تقسیم داشته است پس کوتوله های دست راست او دارای مقدار هستند. پس این کوتوله از کوتوله ام به اندازه شیر دریافت می کند پس
(1)

که
.

اگر یک نامساوی وجود داشته باشد در رابطه (1) علامت تساوی نمی توانند وجود داشته باشد بنابراین

پس کوتوله مقدار مساوی شیر دریافت کرده است. بنابراین به سادگی بسته می شود که توزیع شیر به صورت

پس از 3 لیتر به دست می آید که .

مثال

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

مثال

آیا می توانن 1983 عدد صحیح مثبت کوچک تر از 100000 چنان انتخاب کرد که هیچ سه تایی از آن یک تصاعد حسابی تشکیل ندهند. (1983 و ).


حل
مجموعه ای مانند می سازیم که حتی شامل بیش از 1983 عد صحیح باشد. همه کمتر از باشند، به طوری که هیچ سه تا از آنها تشکیل تصاعد عددی ندهند یعنی در معادله صدق نکنند.
مجموع متشکل از کلیه اعداد صحیح مثبت است که نمایش آنها در مبنای 2 حداکثر 11 رقم دارد که هر یک از آنها صفر با یک است (یعنی رقم 2 ندارد) پس تا از آنها موجود است و بزرگ ترین آنها عبارت است از

حال فرض کنید به ازای ، باشد عدد به ازای تنها متشکل از ارقام 0 و 2 است بنابراین و باید رقم به رقم با هم منطبق نماید پس نتیجه می شود که بنابراین شامل هیچ تصاعد حسابی سه جمله ای نیست و انتخاب موردنظر امکان پذیر است.

مثال

در هر ضلعی محدب سه راس مجاور ، و چنان وجود دارد که دایره محیطی مثلث تمام ضلعی محدب را می پوشاند.
حل
در بین این تعداد محدود از دایره ها یکی از آنها ماکسیمال است. حال مسأله را به دو قسمت می نماییم.
الف. دایره ماکسیمال ضلعی را می پوشاند.
ب. دایره ماکسیمال از سه راس مجاور می گذرد.
اثبات الف.قسمت الف را این طور اثبات می کنیم که فرض کنیم راس بیرون از دایره ماکسیمال واقع شود که ، ، و رئوس یک چهارضلعی محدب هستند. پس دایره محیطی مثلث از دایره محیطی مثلث بزرگ تر خواهد شد و این یک تناقض است.


اثبات ب. فرض کنیم ، و رئوس روی دایره ماکسیمال باشند و فرض کنیم بین و واقع باشد و روی این دایره نیز نباشد. به دلیل حکم قسمت الف این نقطه داخل دایره واقع می شود، اما باز هم دایره محیطی مثلث بزرگ تر از دایره ماکسیمال می شود که این یک تناقض است.

مثال

ثابت کنید برای هر عدد صحیح مثلث نمی تواند یک عدد صحیح باشد.
حل
فرض کنیم مجموعه اعداد صحیح باشد که را یک عدد صحیح نماید اگر تهی نباشد دارای یک عضو حداقل مانند است.
حال عدد را درنظر می گیریم

و چون ، هم و هم اعداد صحیح مثبت هستند بنابراین اما پس با اینکه کوچکترین عضو بود در تناقض است. پس تهی می باشد که به معنی آن است که گویا نیست.

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0141.pdf

همچنین ببینید





تعداد بازدید ها: 32245