منو
 کاربر Online
756 کاربر online
تاریخچه ی: اصل ناوردایی (المپیاد)

تفاوت با نگارش: 1

Lines: 1-203Lines: 1-207
 ||V{maketoc}|| ||V{maketoc}||
-||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| +||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
 ^@#16: ^@#16:
 !اصل ناوردایی !اصل ناوردایی
 در اینجا یکی از استراتژی های سطح بالا در حل مسایل را توضیح خواهیم داد. مسایل این قسمت در نگاه اول مشکل به نظر می رسند اما با حل چند مثال، روش کلی حل مسایل را به دست خواهیم آورد و خواهید دید که گاهی اوقات مسایلی که صورت آنها بسیار پیچیده است، چه باطن ساده ای دارند. در حقیقت روش حل مساله را تنها با حل مساله می توان آموخت. بنابراین توصیه می کنیم پس از مشاهده هر سوال ابتدا سعی کنید خودتان مسایل آن را حل کنید و سپس حل کتاب را مشاهده کنید.  در اینجا یکی از استراتژی های سطح بالا در حل مسایل را توضیح خواهیم داد. مسایل این قسمت در نگاه اول مشکل به نظر می رسند اما با حل چند مثال، روش کلی حل مسایل را به دست خواهیم آورد و خواهید دید که گاهی اوقات مسایلی که صورت آنها بسیار پیچیده است، چه باطن ساده ای دارند. در حقیقت روش حل مساله را تنها با حل مساله می توان آموخت. بنابراین توصیه می کنیم پس از مشاهده هر سوال ابتدا سعی کنید خودتان مسایل آن را حل کنید و سپس حل کتاب را مشاهده کنید.
 استراتژی اول حل مساله جستجوی قواعد ثابت است. در حل مساله های این فصل این قاعده را رعایت کنید:  استراتژی اول حل مساله جستجوی قواعد ثابت است. در حل مساله های این فصل این قاعده را رعایت کنید:
 --- ---
 !!اگر یک تکرار مشاهده کردید به دنبال یک قاعده ثابت بگردید.  !!اگر یک تکرار مشاهده کردید به دنبال یک قاعده ثابت بگردید.
 در مسایل این فصل در هر مساله یک حالت اولیه (فضای ابتدایی) وجود دارد و عملی نیز تعریف شده که در هر گام انجام می شود و معمولاً یک حالت به عنوان هدف نهایی معرفی شده و سوال این است که: آیا می توان به این هدف نهایی رسید یا خیر؟ بنابراین مسایل این فصل 2 حالت دارند:  در مسایل این فصل در هر مساله یک حالت اولیه (فضای ابتدایی) وجود دارد و عملی نیز تعریف شده که در هر گام انجام می شود و معمولاً یک حالت به عنوان هدف نهایی معرفی شده و سوال این است که: آیا می توان به این هدف نهایی رسید یا خیر؟ بنابراین مسایل این فصل 2 حالت دارند:
 1.مسایلی که رسیدن به حالت هدف آنها ممکن است: این دسته از مسایل (به نظر من) جالب تر هستند در این مسایل معمولاً به دنبال یک تابع اکیداً صعودی یا اکیداً نزولی برای هر گام می گردیم. پس از یافتن این تابع تقریباً 80% مساله حل شده است. پس از یافتن این تابع معمولاً مسایل به 2 روش حل می شوند.  1.مسایلی که رسیدن به حالت هدف آنها ممکن است: این دسته از مسایل (به نظر من) جالب تر هستند در این مسایل معمولاً به دنبال یک تابع اکیداً صعودی یا اکیداً نزولی برای هر گام می گردیم. پس از یافتن این تابع تقریباً 80% مساله حل شده است. پس از یافتن این تابع معمولاً مسایل به 2 روش حل می شوند.
 الف.از آنجا که تابع یکنواست، در گام های مساله به حالت تکراری برنمی خوریم چون بایستی در این صورت رشد تابع در مواقعی به صورت عکس ادامه یافته باشد. اگر تعداد حالت های (فضای) مساله محدود باشد چون در هر گام به یک حالت جدید می رسیم پس این عمل نمی تواند بینهایت بار انجام شود و بالاخره این عمل متوقف می شود و معمولاً توقف عمل معادل حل مساله است.  الف.از آنجا که تابع یکنواست، در گام های مساله به حالت تکراری برنمی خوریم چون بایستی در این صورت رشد تابع در مواقعی به صورت عکس ادامه یافته باشد. اگر تعداد حالت های (فضای) مساله محدود باشد چون در هر گام به یک حالت جدید می رسیم پس این عمل نمی تواند بینهایت بار انجام شود و بالاخره این عمل متوقف می شود و معمولاً توقف عمل معادل حل مساله است.
 ‌ب.تابع یکنواست و قدر مطلق رشد آن از مقدار {TEX()} {e} {TEX}بیشتر است حالا اگر تابع مورد نظر از مقدار مشخصی بیشتر (یا کمتر) نشود در این صورت این عمل متوقف خواهد شد. در اینجا ذکر یک نکته لازم است. مقدار {TEX()} {e} {TEX}چرا لازم است: فرض کنید هدف ما عدد 2 است و حالت ابتدا عدد 1 است و در گام اول {TEX()} {\frac{1}{2}} {TEX} در گام دوم {TEX()} {\frac{1}{4}} {TEX} در گام سوم {TEX()} {\frac{1}{8}} {TEX} و ... به عدد 1 اضافه شود مشاهده می کنیم که همیشه می توان به عدد موجود عددی اضافه کرد و هیچ وقت هم این عدد به 2 نمی رسد. اینجا لزوم وجود {TEX()} {e} {TEX}اثبات می شود.  ‌ب.تابع یکنواست و قدر مطلق رشد آن از مقدار {TEX()} {e} {TEX}بیشتر است حالا اگر تابع مورد نظر از مقدار مشخصی بیشتر (یا کمتر) نشود در این صورت این عمل متوقف خواهد شد. در اینجا ذکر یک نکته لازم است. مقدار {TEX()} {e} {TEX}چرا لازم است: فرض کنید هدف ما عدد 2 است و حالت ابتدا عدد 1 است و در گام اول {TEX()} {\frac{1}{2}} {TEX} در گام دوم {TEX()} {\frac{1}{4}} {TEX} در گام سوم {TEX()} {\frac{1}{8}} {TEX} و ... به عدد 1 اضافه شود مشاهده می کنیم که همیشه می توان به عدد موجود عددی اضافه کرد و هیچ وقت هم این عدد به 2 نمی رسد. اینجا لزوم وجود {TEX()} {e} {TEX}اثبات می شود.
 #@ #@
 @#16: @#16:
 2.مسایلی که رسیدن به حالت هدف در آنها ممکن نیست: در این مسایل معمولاً رابطه ثابتی می یابیم که با هر عمل همچنان برقرار باقی می ماند اگر این رابطه برای حالت نهایی (حالت هدف) برقرار نباشد، چون تنها به حالت های ممکن است برسیم که این رابطه را ارضا می کنند، بنابراین به حالت نهایی نمی رسیم (به این روش استفاده از اصل هم خوانی هم می گویند).  2.مسایلی که رسیدن به حالت هدف در آنها ممکن نیست: در این مسایل معمولاً رابطه ثابتی می یابیم که با هر عمل همچنان برقرار باقی می ماند اگر این رابطه برای حالت نهایی (حالت هدف) برقرار نباشد، چون تنها به حالت های ممکن است برسیم که این رابطه را ارضا می کنند، بنابراین به حالت نهایی نمی رسیم (به این روش استفاده از اصل هم خوانی هم می گویند).
 --- ---
 !!مثال1  !!مثال1
  از نقطه {TEX()} {s=(a,b)} {TEX} با فرض {TEX()} {0<b<a} {TEX} در صفحه شروع می کنیم و دنباله نقاط {TEX()} {(x_n,y_n)} {TEX} را بر طبق قانون زیر می سازیم:   از نقطه {TEX()} {s=(a,b)} {TEX} با فرض {TEX()} {0<b<a} {TEX} در صفحه شروع می کنیم و دنباله نقاط {TEX()} {(x_n,y_n)} {TEX} را بر طبق قانون زیر می سازیم:
 @@{TEX()} {x_0=a \ , \ y_0=b } {TEX}@@ @@{TEX()} {x_0=a \ , \ y_0=b } {TEX}@@
 @@{TEX()} {x_{n+1}=\frac{x_n+y_n}{2} \quad , \quad y_{n+1}=\frac{2x_ny_n}{x_n+y_n}} {TEX}@@ @@{TEX()} {x_{n+1}=\frac{x_n+y_n}{2} \quad , \quad y_{n+1}=\frac{2x_ny_n}{x_n+y_n}} {TEX}@@
 ثابت کنید با بزرگ شدن {TEX()} {n} {TEX}، {TEX()} {x_n} {TEX} و {TEX()} {y_n} {TEX} به سمت یک حد مشخص میل می کنند.  ثابت کنید با بزرگ شدن {TEX()} {n} {TEX}، {TEX()} {x_n} {TEX} و {TEX()} {y_n} {TEX} به سمت یک حد مشخص میل می کنند.
 __حل __ __حل __
  در اینجا یافتن یک رابطه ثابت کار ساده ای است. از رابطه {TEX()} {x_{n+1}y_{n+1}=x_ny_n} {TEX} (که بسیار واضح است ) برای تمام مقادیر {TEX()} {n} {TEX}می توان نتیجه گرفت {TEX()} {x_ny_n=ab} {TEX}. در ابتدا داریم {TEX()} {y_0<x_0} {TEX}. این رابطه نیز به عنوان یک رابطه ثابت باقی می ماند. در حقیقت {TEX()} {x_{n+1}} {TEX} واسطه حسابی {TEX()} {y_n} {TEX}، {TEX()} {x_n} {TEX} و {TEX()} {y_{n+1}} {TEX} واسطه هندسی {TEX()} {y_n} {TEX} و {TEX()} {x_n} {TEX} است: واسطه حسابی 2 عدد تنها وقتی با واسطه هندسی آنها مساوی است که 2 عدد با هم مساوی باشند و در غیر این صورت واسطه حسابی بزرگ تر است. چون {TEX()} {y_0<x_0} {TEX} است، به ازای تمام مقادیر {TEX()} {n} {TEX}رابطه {TEX()} {y_n<x_n} {TEX} برقرار می ماند. پس برای تمام مقادیر {TEX()} {n} {TEX}رابطه   در اینجا یافتن یک رابطه ثابت کار ساده ای است. از رابطه {TEX()} {x_{n+1}y_{n+1}=x_ny_n} {TEX} (که بسیار واضح است ) برای تمام مقادیر {TEX()} {n} {TEX}می توان نتیجه گرفت {TEX()} {x_ny_n=ab} {TEX}. در ابتدا داریم {TEX()} {y_0<x_0} {TEX}. این رابطه نیز به عنوان یک رابطه ثابت باقی می ماند. در حقیقت {TEX()} {x_{n+1}} {TEX} واسطه حسابی {TEX()} {y_n} {TEX}، {TEX()} {x_n} {TEX} و {TEX()} {y_{n+1}} {TEX} واسطه هندسی {TEX()} {y_n} {TEX} و {TEX()} {x_n} {TEX} است: واسطه حسابی 2 عدد تنها وقتی با واسطه هندسی آنها مساوی است که 2 عدد با هم مساوی باشند و در غیر این صورت واسطه حسابی بزرگ تر است. چون {TEX()} {y_0<x_0} {TEX} است، به ازای تمام مقادیر {TEX()} {n} {TEX}رابطه {TEX()} {y_n<x_n} {TEX} برقرار می ماند. پس برای تمام مقادیر {TEX()} {n} {TEX}رابطه
 @@{TEX()} {0<x_{n+1}-y_{n+1}=\frac{x_n-y_n}{x_n+y_n} \cdots {x_n-y_n}{2} <\frac{x_n-y_n}{2}} {TEX}@@ @@{TEX()} {0<x_{n+1}-y_{n+1}=\frac{x_n-y_n}{x_n+y_n} \cdots {x_n-y_n}{2} <\frac{x_n-y_n}{2}} {TEX}@@
 برقرار است. بنابراین {TEX()} {x_n} {TEX} و {TEX()} {y_n} {TEX} به ازای مقادیر بزرگ {TEX()} {n} {TEX}هر دو به سمت یک عدد که ما آن را {TEX()} {x} {TEX}می نامیم میل می کنند. {TEX()} {x} {TEX} در رابطه {TEX()} {x^2=ab} {TEX} یا {TEX()} {x=\sqrt{ab}} {TEX} بایستی صدق کند.  برقرار است. بنابراین {TEX()} {x_n} {TEX} و {TEX()} {y_n} {TEX} به ازای مقادیر بزرگ {TEX()} {n} {TEX}هر دو به سمت یک عدد که ما آن را {TEX()} {x} {TEX}می نامیم میل می کنند. {TEX()} {x} {TEX} در رابطه {TEX()} {x^2=ab} {TEX} یا {TEX()} {x=\sqrt{ab}} {TEX} بایستی صدق کند.
 این مثالی از یافتن رابطه ثابت در مساله بود. توجه کنید که یافتن این روابط حل مساله نیست بلکه صرفاً ابزاری برای حل مساله است. اینکه چگونه از این روابط برای حل مساله استفاده نماییم نیز کاملاً ابتکاری است.  این مثالی از یافتن رابطه ثابت در مساله بود. توجه کنید که یافتن این روابط حل مساله نیست بلکه صرفاً ابزاری برای حل مساله است. اینکه چگونه از این روابط برای حل مساله استفاده نماییم نیز کاملاً ابتکاری است.
 #@ #@
 @#16: @#16:
 --- ---
 !!مثال2  !!مثال2
- فرض کنید {TEX()} {n} {TEX}یک عدد طبیعی فرد است. در ابتدا تمام اعداد {TEX()} {1,2,3,\cdots ,2n} {TEX} روی تخته سیاه نوشته شده اند. در هر مرحله 2 عدد دلخواه {TEX()} {a} {TEX}و {TEX()} {b} {TEX}را از بین اعداد روی تخته سیاه پاک می کنیم و به جای آنها عدد {TEX()} {|a-b|} {TEX} را می نویسیم. ثابت کنید عددی که در نهایت باقی خواهد ماند فرد است. + فرض کنید {TEX()} {n} {TEX}یک ((عدد طبیعی)) فرد است. در ابتدا تمام اعداد {TEX()} {1,2,3,\cdots ,2n} {TEX} روی تخته سیاه نوشته شده اند. در هر مرحله 2 عدد دلخواه {TEX()} {a} {TEX}و {TEX()} {b} {TEX}را از بین اعداد روی تخته سیاه پاک می کنیم و به جای آنها عدد {TEX()} {|a-b|} {TEX} را می نویسیم. ثابت کنید عددی که در نهایت باقی خواهد ماند فرد است.
 __حل__ __حل__
  فرض کنید {TEX()} {S} {TEX}برابر مجموع اعدادی باشد که در هر مرحله روی تخته سیاه نوشته شده اند در ابتدا {TEX()} {S=\frac{2n(2n+1)}{2}} {TEX} است که یک عدد فرد است. فرض کنید در یک مرحله 2 عدد {TEX()} {a} {TEX}و {TEX()} {b} {TEX}را انتخاب کنیم. بدون کاسته شدن از کلیت مساله می توانیم فرض کنیم {TEX()} {a \le b} {TEX} باشد در این صورت {TEX()} {a} {TEX}و {TEX()} {b} {TEX}خط می خورند و به جای آنها {TEX()} {b-a} {TEX} قرار می گیرد که درنتیجه مقدار {TEX()} {S} {TEX}به اندازهُ {TEX()} {2a} {TEX}کاهش می یابد بنابراین زوج یا فرد بودن {TEX()} {S} {TEX}ثابت می ماند. در ابتدا {TEX()} {S} {TEX}عددی فرد است بنابراین عددی که در نهایت باقی می ماند نیز فرد است.   فرض کنید {TEX()} {S} {TEX}برابر مجموع اعدادی باشد که در هر مرحله روی تخته سیاه نوشته شده اند در ابتدا {TEX()} {S=\frac{2n(2n+1)}{2}} {TEX} است که یک عدد فرد است. فرض کنید در یک مرحله 2 عدد {TEX()} {a} {TEX}و {TEX()} {b} {TEX}را انتخاب کنیم. بدون کاسته شدن از کلیت مساله می توانیم فرض کنیم {TEX()} {a \le b} {TEX} باشد در این صورت {TEX()} {a} {TEX}و {TEX()} {b} {TEX}خط می خورند و به جای آنها {TEX()} {b-a} {TEX} قرار می گیرد که درنتیجه مقدار {TEX()} {S} {TEX}به اندازهُ {TEX()} {2a} {TEX}کاهش می یابد بنابراین زوج یا فرد بودن {TEX()} {S} {TEX}ثابت می ماند. در ابتدا {TEX()} {S} {TEX}عددی فرد است بنابراین عددی که در نهایت باقی می ماند نیز فرد است.
 --- ---
 !!مثال 3  !!مثال 3
  یک دایره را به 6 بخش تقسیم کرده ایم و در جهت خلاف حرکت عقربه های ساعت عددهای 0، 0، 0، 1، 0 و 1 در این بخش ها نوشته ایم. شما می توانید در هر مرحله به دو عدد که در 2 بخش مجاور قرار دارند یک واحد اضافه نمایید. آیا ممکن است به حالتی برسید که تمام اعداد نوشته شده با هم برابر باشند؟   یک دایره را به 6 بخش تقسیم کرده ایم و در جهت خلاف حرکت عقربه های ساعت عددهای 0، 0، 0، 1، 0 و 1 در این بخش ها نوشته ایم. شما می توانید در هر مرحله به دو عدد که در 2 بخش مجاور قرار دارند یک واحد اضافه نمایید. آیا ممکن است به حالتی برسید که تمام اعداد نوشته شده با هم برابر باشند؟
 __حل__ __حل__
  برای حل مساله فرض می کنیم {TEX()} {A} {TEX}مجموع اعداد بخش های اول و سوم و پنجم و {TEX()} {B} {TEX}، مجموع اعداد بخش های دوم و چهارم و ششم باشد روشن است که رابطه {TEX()} {A-B=2} {TEX} همیشه برقرار است چون در هر گام به هر یک از {TEX()} {A} {TEX}و {TEX()} {B} {TEX}یک واحد اضافه می شود. بنابراین امکان ندارد به حالتی برسیم که شش عدد با هم مساوی باشند چون در آن حالت {TEX()} {A-B} {TEX} برابر 0 خواهد بود.   برای حل مساله فرض می کنیم {TEX()} {A} {TEX}مجموع اعداد بخش های اول و سوم و پنجم و {TEX()} {B} {TEX}، مجموع اعداد بخش های دوم و چهارم و ششم باشد روشن است که رابطه {TEX()} {A-B=2} {TEX} همیشه برقرار است چون در هر گام به هر یک از {TEX()} {A} {TEX}و {TEX()} {B} {TEX}یک واحد اضافه می شود. بنابراین امکان ندارد به حالتی برسیم که شش عدد با هم مساوی باشند چون در آن حالت {TEX()} {A-B} {TEX} برابر 0 خواهد بود.
 ::{picture=img/daneshnameh_up/a/a3/com0040a.jpg}:: ::{picture=img/daneshnameh_up/a/a3/com0040a.jpg}::
 --- ---
 #@ #@
 @#16: @#16:
 !!مثال 4  !!مثال 4
 در یک پالمان هر نماینده حداکثر 3 مخالف دارد. ثابت کنید، این نمایندگان را می توان در 2 خانه قرار داد طوری که هر نماینده در خانهُ خود حداکثر 1 مخالف داشته باشد.  در یک پالمان هر نماینده حداکثر 3 مخالف دارد. ثابت کنید، این نمایندگان را می توان در 2 خانه قرار داد طوری که هر نماینده در خانهُ خود حداکثر 1 مخالف داشته باشد.
 __حل__ __حل__
  در ابتدا نمایندگان را به صورت دلخواه در 2 خانه قرار می دهیم. فرض کنید {TEX()} {H} {TEX}مجموع تعداد مخالفان افراد در خانه های خود باشد. فرض کنید {TEX()} {A} {TEX}در خانه خود بیش از 1 مخالف داشته باشد بنابراین {TEX()} {A} {TEX}حداکثر یک مخالف در خانهُ دیگر دارد و می تواند به خانهُ دیگر برود. اگر خانهُ {TEX()} {A} {TEX}عوض شود مقدار {TEX()} {H} {TEX}کم خواهد شد. (مقدار {TEX()} {H} {TEX}حداقل 2 واحد کمتر می شود) از آنجا که {TEX()} {H} {TEX}عددی طبیعی و محدود است این عمل نمی تواند همیشه ادامه یابد و بالاخره متوقف خواهد شد. یعنی بعد از چند مرحله مقدار {TEX()} {H} {TEX}دیگر کاهش نمی یابد و درنتیجه در آنجا ما به نتیجه مطلوب رسیده ایم.   در ابتدا نمایندگان را به صورت دلخواه در 2 خانه قرار می دهیم. فرض کنید {TEX()} {H} {TEX}مجموع تعداد مخالفان افراد در خانه های خود باشد. فرض کنید {TEX()} {A} {TEX}در خانه خود بیش از 1 مخالف داشته باشد بنابراین {TEX()} {A} {TEX}حداکثر یک مخالف در خانهُ دیگر دارد و می تواند به خانهُ دیگر برود. اگر خانهُ {TEX()} {A} {TEX}عوض شود مقدار {TEX()} {H} {TEX}کم خواهد شد. (مقدار {TEX()} {H} {TEX}حداقل 2 واحد کمتر می شود) از آنجا که {TEX()} {H} {TEX}عددی طبیعی و محدود است این عمل نمی تواند همیشه ادامه یابد و بالاخره متوقف خواهد شد. یعنی بعد از چند مرحله مقدار {TEX()} {H} {TEX}دیگر کاهش نمی یابد و درنتیجه در آنجا ما به نتیجه مطلوب رسیده ایم.
 __ملاحظه __ __ملاحظه __
- در اینجا از یک ایدهُ جدید استفاده نمودیم. ما یک تابع اکیداً نزولی بافتیم که در هر مرحله مقدار آن کاهش می یابد و همیشه مقدار آن عددی صحیح و غیرمنفی است از آنجا که دنبالهُ نامتناهی اکیداً نزولی از اعداد صحیح و غیرمنفی وجود ندارد، این دنباله بایستی یک دنبالهُ متناهی باشد. + در اینجا از یک ایدهُ جدید استفاده نمودیم. ما یک ((تابع)) اکیداً نزولی بافتیم که در هر مرحله مقدار آن کاهش می یابد و همیشه مقدار آن عددی صحیح و غیرمنفی است از آنجا که دنبالهُ نامتناهی اکیداً نزولی از اعداد صحیح و غیرمنفی وجود ندارد، این دنباله بایستی یک دنبالهُ متناهی باشد.
 --- ---
 !!مثال 5  !!مثال 5
  فرض کنید هر 4 عدد{TEX()} {a,b,c,d} {TEX} با هم مساوی نباشند از دنباله چهارتایی {TEX()} {(a,b,c,d)} {TEX} شروع می کنیم از این دنباله چهارتایی جدید {TEX()} {(a-b,b-c,c-d,d-a)} {TEX} را می سازیم و همین عمل را با دنبالهُ جدید ادامه می دهیم. ثابت کنید کوچکترین عدد دنباله، می تواند از لحاظ قدرمطلق، به هر اندازه بزرگ شود.   فرض کنید هر 4 عدد{TEX()} {a,b,c,d} {TEX} با هم مساوی نباشند از دنباله چهارتایی {TEX()} {(a,b,c,d)} {TEX} شروع می کنیم از این دنباله چهارتایی جدید {TEX()} {(a-b,b-c,c-d,d-a)} {TEX} را می سازیم و همین عمل را با دنبالهُ جدید ادامه می دهیم. ثابت کنید کوچکترین عدد دنباله، می تواند از لحاظ قدرمطلق، به هر اندازه بزرگ شود.
 __حل__ __حل__
  فرض کنید به ازای هر {TEX()} {n} {TEX}، {TEX()} {{\rho}_n=(a_n,b_n,c_n,d_n)} {TEX} چهارتایی باشد که در مرحلهُ {TEX()} {n} {TEX}ام به آن رسیده ایم بنابراین برای {TEX()} {n>0} {TEX} داریم: {TEX()} {a_n+b_n+c_n+d_n=0} {TEX} این یک رابطهُ ثابت است که شاید زیاد به ما کمک نکند ولی اگر ثابت کنیم دنبالهُ {TEX()} {a_n^2+b_n^2+c_n^2+d_n^2} {TEX} کران بالا ندارد در این صورت مسأله حل خواهد شد. می بینیم که رابطهُ زیر برقرار است.   فرض کنید به ازای هر {TEX()} {n} {TEX}، {TEX()} {{\rho}_n=(a_n,b_n,c_n,d_n)} {TEX} چهارتایی باشد که در مرحلهُ {TEX()} {n} {TEX}ام به آن رسیده ایم بنابراین برای {TEX()} {n>0} {TEX} داریم: {TEX()} {a_n+b_n+c_n+d_n=0} {TEX} این یک رابطهُ ثابت است که شاید زیاد به ما کمک نکند ولی اگر ثابت کنیم دنبالهُ {TEX()} {a_n^2+b_n^2+c_n^2+d_n^2} {TEX} کران بالا ندارد در این صورت مسأله حل خواهد شد. می بینیم که رابطهُ زیر برقرار است.
 @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2=(a_n-b_n)^2+(b_n-c_n)^2+(c_n-d_n)^2+(d_n-a_n)^2} {TEX}@@ @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2=(a_n-b_n)^2+(b_n-c_n)^2+(c_n-d_n)^2+(d_n-a_n)^2} {TEX}@@
 (1) @@ {TEX()} {=2(a_n^2+b_n^2+c_n^2+d_n^2)-2a_nb_n-2b_nc_n-2c_nd_n-2d_na_n} {TEX}@@ (1) @@ {TEX()} {=2(a_n^2+b_n^2+c_n^2+d_n^2)-2a_nb_n-2b_nc_n-2c_nd_n-2d_na_n} {TEX}@@
 حالا از رابطهُ {TEX()} {0=a_n+b_n+c_n+d_n} {TEX} استفاده می کنیم:  حالا از رابطهُ {TEX()} {0=a_n+b_n+c_n+d_n} {TEX} استفاده می کنیم:
 @@{TEX()} {0=(a_n+b_n+c_n+d_n)^2=(a_n+c_n)^2+(b_n+d_n)^2+2a_nb_n+2b_nc_n+2c_nd_n+2d_na_n} {TEX}@@ @@{TEX()} {0=(a_n+b_n+c_n+d_n)^2=(a_n+c_n)^2+(b_n+d_n)^2+2a_nb_n+2b_nc_n+2c_nd_n+2d_na_n} {TEX}@@
 طرفین تساوی فوق و رابطهُ (1) را با هم جمع می کنیم تا رابطهُ زیر به دست آید:  طرفین تساوی فوق و رابطهُ (1) را با هم جمع می کنیم تا رابطهُ زیر به دست آید:
 @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2=2(a_n^2+b_n^2+c_n^2+d_n^2)+(a_n+c_n)^2+(b_n+d_n)^2} {TEX}@@ @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2=2(a_n^2+b_n^2+c_n^2+d_n^2)+(a_n+c_n)^2+(b_n+d_n)^2} {TEX}@@
 #@ #@
 @#16: @#16:
 درنتیجه داریم:  درنتیجه داریم:
 @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2 \ge 2(a_n^2+b_n^2+c_n^2+d_n^2)} {TEX}@@ @@{TEX()} {a_{n+1}^2+b_{n+1}^2+c_{n+1}^2+d_{n+1}^2 \ge 2(a_n^2+b_n^2+c_n^2+d_n^2)} {TEX}@@
 و درنتیجه به ازای هر {TEX()} {n} {TEX}داریم:  و درنتیجه به ازای هر {TEX()} {n} {TEX}داریم:
 @@{TEX()} {a_n^2+b_n^2+c_n^2+d_n^2 \ge 2^{n-1}(a_1^2+b_1^2+c_1^2+d_1^2)} {TEX}@@ @@{TEX()} {a_n^2+b_n^2+c_n^2+d_n^2 \ge 2^{n-1}(a_1^2+b_1^2+c_1^2+d_1^2)} {TEX}@@
  بنابراین مجموع توان دوم اعداد هر چهارتایی در هر مرحله در حال افزایش است و چون این مجموع همیشه عدد طبیعی است مقدار آن هر اندازه که بخواهیم بزرگ می شود. حالا نتیجه می گیریم بزرگترین عدد هر چهارتایی از لحاظ قدرمطلق، هر اندازه که بخواهیم می تواند زیاد شود. اما چون مجموع اعداد 4تایی ها بعد از مرحلهُ اول 0 است نتیجه می گیریم هم قدرمطلق کوچکترین عدد منفی و هم قدرمطلق بزرگترین عدد مثبت در حال افزایش است.   بنابراین مجموع توان دوم اعداد هر چهارتایی در هر مرحله در حال افزایش است و چون این مجموع همیشه عدد طبیعی است مقدار آن هر اندازه که بخواهیم بزرگ می شود. حالا نتیجه می گیریم بزرگترین عدد هر چهارتایی از لحاظ قدرمطلق، هر اندازه که بخواهیم می تواند زیاد شود. اما چون مجموع اعداد 4تایی ها بعد از مرحلهُ اول 0 است نتیجه می گیریم هم قدرمطلق کوچکترین عدد منفی و هم قدرمطلق بزرگترین عدد مثبت در حال افزایش است.
  __ملاحظه__  __ملاحظه__
  اگر در این مسأله {TEX()} {{\rho}_n =(a_n,b_n,c_n,d_n)} {TEX} را نقطه ای در صفحهُ 4 بعدی فرض کنیم. متوجه می شویم که در هر مرحله، فاصلهُ نقطهُ جدید از مبدأ در حال افزایش است بنابراین فاصله از مبدأ تابع مهمی است که زمان هایی که با دنباله ای از نقاط سروکار داریم ممکن است مفید باشد.   اگر در این مسأله {TEX()} {{\rho}_n =(a_n,b_n,c_n,d_n)} {TEX} را نقطه ای در صفحهُ 4 بعدی فرض کنیم. متوجه می شویم که در هر مرحله، فاصلهُ نقطهُ جدید از مبدأ در حال افزایش است بنابراین فاصله از مبدأ تابع مهمی است که زمان هایی که با دنباله ای از نقاط سروکار داریم ممکن است مفید باشد.
 --- ---
 !!مثال 6  !!مثال 6
  از نقطه {TEX()} {(x_0,y_0)} {TEX} با فرض {TEX()} {0< x_0 <y_0} {TEX} شروع می کنیم و در هر مرحله {TEX()} {y_{n+1},x_{n+1}} {TEX} را به صورت زیر از {TEX()} {y_n,x_n} {TEX} به دست می آوریم.   از نقطه {TEX()} {(x_0,y_0)} {TEX} با فرض {TEX()} {0< x_0 <y_0} {TEX} شروع می کنیم و در هر مرحله {TEX()} {y_{n+1},x_{n+1}} {TEX} را به صورت زیر از {TEX()} {y_n,x_n} {TEX} به دست می آوریم.
 @@{TEX()} {y_{n+1}=\sqrt{x_{n+1}y_n} {TEX} @@  @@{TEX()} {y_{n+1}=\sqrt{x_{n+1}y_n} {TEX} @@
  @@ {TEX()} {x_{n+1}=\frac{x_n+y_n}{2}} {TEX}@@  @@ {TEX()} {x_{n+1}=\frac{x_n+y_n}{2}} {TEX}@@
 با استفاده از شکل 1 و نامساوی واسطه های حسابی و هندسی برای هر {TEX()} {n} {TEX}نشان دهید:  با استفاده از شکل 1 و نامساوی واسطه های حسابی و هندسی برای هر {TEX()} {n} {TEX}نشان دهید:
 ::{picture=img/daneshnameh_up/8/89/com0040b.jpg}:: ::{picture=img/daneshnameh_up/8/89/com0040b.jpg}::
 @@{TEX()} {y_{n+1}-x_{n+1}<\frac{y_n-x_n}{4}} {TEX} @@  @@{TEX()} {y_{n+1}-x_{n+1}<\frac{y_n-x_n}{4}} {TEX} @@
  @@{TEX()} {x_n<y_n \Rightarrow \ x_{n+1}<y_{n+1}} {TEX}@@  @@{TEX()} {x_n<y_n \Rightarrow \ x_{n+1}<y_{n+1}} {TEX}@@
 همچنین ثابت کنید {TEX()} {x} {TEX}حد دنبالهُ {TEX()} {x_n} {TEX} و {TEX()} {y} {TEX}حد دنبالهُ {TEX()} {y_n} {TEX} با هم مساوی اند.  همچنین ثابت کنید {TEX()} {x} {TEX}حد دنبالهُ {TEX()} {x_n} {TEX} و {TEX()} {y} {TEX}حد دنبالهُ {TEX()} {y_n} {TEX} با هم مساوی اند.
 #@ #@
 @#16: @#16:
 __حل__ __حل__
  در اینجا نیز اصل عدم تغییر به کمک ما می آید. به تغییرات {TEX()} {\frac{x_n}{y_n}} {TEX} و {TEX()} { x_n-y_n } {TEX} وقتی از مرحلهُ {TEX()} {n} {TEX}ام به مرحلهُ {TEX()} {n+1} {TEX}ام می رویم، توجه کنید:  در اینجا نیز اصل عدم تغییر به کمک ما می آید. به تغییرات {TEX()} {\frac{x_n}{y_n}} {TEX} و {TEX()} { x_n-y_n } {TEX} وقتی از مرحلهُ {TEX()} {n} {TEX}ام به مرحلهُ {TEX()} {n+1} {TEX}ام می رویم، توجه کنید:
 (1) @@{TEX()} {\frac{x_{n+1}}{y_{n+1}}=\frac{x_{n+1}}{\sqrt{x_{n+1} y_n}}=\sqrt{\frac{x_{n+1}}{y_n}}=\sqrt{\frac{1+\frac{x_n}{y_n}}{2}}} {TEX}@@ (1) @@{TEX()} {\frac{x_{n+1}}{y_{n+1}}=\frac{x_{n+1}}{\sqrt{x_{n+1} y_n}}=\sqrt{\frac{x_{n+1}}{y_n}}=\sqrt{\frac{1+\frac{x_n}{y_n}}{2}}} {TEX}@@
 این رابطه ما را به یاد رابطهُ بین کسینوس نصف یک زاویه با کسینوس خود آن زاویه می اندازد:  این رابطه ما را به یاد رابطهُ بین کسینوس نصف یک زاویه با کسینوس خود آن زاویه می اندازد:
 @@{TEX()} {cos \frac{\alpha}{2}=\sqrt{\frac{1+\cos \alpha}{2}}} {TEX}@@ @@{TEX()} {cos \frac{\alpha}{2}=\sqrt{\frac{1+\cos \alpha}{2}}} {TEX}@@
 از آنجا که رابطهُ {TEX()} {0<\frac{x_n}{y_n} <1} {TEX} همیشه برقرار است می توانیم فرض کنیم {TEX()} {\frac{x_n}{y_n}=cos \ {\alpha}_n} {TEX}. بنابراین رابطهُ (1) به صورت زیر درمی آید:  از آنجا که رابطهُ {TEX()} {0<\frac{x_n}{y_n} <1} {TEX} همیشه برقرار است می توانیم فرض کنیم {TEX()} {\frac{x_n}{y_n}=cos \ {\alpha}_n} {TEX}. بنابراین رابطهُ (1) به صورت زیر درمی آید:
 (2) @@{TEX()} {cos {\alpha}_{n+1}=cos \frac{{\alpha}_n}{2} \ \Rightarrow \ {\alpha}_n=\frac{{\alpha}_0}{2^n} \ \Rightarrow \ 2^n{\alpha}_n={\alpha}-0} {TEX}@@ (2) @@{TEX()} {cos {\alpha}_{n+1}=cos \frac{{\alpha}_n}{2} \ \Rightarrow \ {\alpha}_n=\frac{{\alpha}_0}{2^n} \ \Rightarrow \ 2^n{\alpha}_n={\alpha}-0} {TEX}@@
 بنابراین می توان نتیجه گرفت:  بنابراین می توان نتیجه گرفت:
 @@{TEX()} {2^n Arccos \frac{x_n}{y_n}=Arccos \frac{x_0}{y_0}} {TEX}@@ @@{TEX()} {2^n Arccos \frac{x_n}{y_n}=Arccos \frac{x_0}{y_0}} {TEX}@@
 که همواره برای هر {TEX()} {n} {TEX}برقرار است.  که همواره برای هر {TEX()} {n} {TEX}برقرار است.
 برای اینکه از ریشه دوم پرهیز کنیم به جای {TEX()} {x_n-y_n} {TEX}، {TEX()} {x_n^2-y_n^2} {TEX} را بررسی می کنیم.  برای اینکه از ریشه دوم پرهیز کنیم به جای {TEX()} {x_n-y_n} {TEX}، {TEX()} {x_n^2-y_n^2} {TEX} را بررسی می کنیم.
 داریم:  داریم:
 @@{TEX()} {y_{n+1}^2-x_{n+1}^2=\frac{y_n^2-x_n^2}{4}} {TEX}@@ @@{TEX()} {y_{n+1}^2-x_{n+1}^2=\frac{y_n^2-x_n^2}{4}} {TEX}@@
 @@{TEX()} {\Rightarrow \ 2 \sqrt{y_{n+1}^2-x_{n+1}^2}=\sqrt{y_n^2-x_n^2}} {TEX}@@ @@{TEX()} {\Rightarrow \ 2 \sqrt{y_{n+1}^2-x_{n+1}^2}=\sqrt{y_n^2-x_n^2}} {TEX}@@
 که با تکرار چند بارهُ آن به دست می آید:  که با تکرار چند بارهُ آن به دست می آید:
 (3) @@ {TEX()} {2^n \sqrt{y_n^2+x_n^2}=\sqrt{y_0^2-x_0^2}} {TEX}@@ (3) @@ {TEX()} {2^n \sqrt{y_n^2+x_n^2}=\sqrt{y_0^2-x_0^2}} {TEX}@@
 که این نیز رابطهُ مفید دیگری است.  که این نیز رابطهُ مفید دیگری است.
 @@{TEX()} {s=\sqrt{1-t^2} \qquad , \qquad arccos(t)=arcsin(s)} {TEX}@@ @@{TEX()} {s=\sqrt{1-t^2} \qquad , \qquad arccos(t)=arcsin(s)} {TEX}@@
 از شکل 2 و روابط (2) و (3) می توان نتیجه گرفت:  از شکل 2 و روابط (2) و (3) می توان نتیجه گرفت:
 ::{picture=img/daneshnameh_up/f/f5/com0040c.jpg}:: ::{picture=img/daneshnameh_up/f/f5/com0040c.jpg}::
 #@ #@
 @#16: @#16:
 @@{TEX()} {arccos \frac{x_0}{y_0}=2^n arccos \frac{x_n}{y_n}=2arcsin \frac{\sqrt{y_n^2+x_n^2}}{y_n}=2^n arcsin \frac{\sqrt{y_0^2-x_0^2}}{2^n y_n}} {TEX}@@ @@{TEX()} {arccos \frac{x_0}{y_0}=2^n arccos \frac{x_n}{y_n}=2arcsin \frac{\sqrt{y_n^2+x_n^2}}{y_n}=2^n arcsin \frac{\sqrt{y_0^2-x_0^2}}{2^n y_n}} {TEX}@@
 حد سمت راست وقتی {TEX()} {n} {TEX}به سمت بینهایت میل کند برابر {TEX()} {\frac{\sqrt{y_0^2+x_0^2}}{2}} {TEX} است و درنتیجه رابطهُ زیر به دست می آید.  حد سمت راست وقتی {TEX()} {n} {TEX}به سمت بینهایت میل کند برابر {TEX()} {\frac{\sqrt{y_0^2+x_0^2}}{2}} {TEX} است و درنتیجه رابطهُ زیر به دست می آید.
 @@{TEX()} {x=y=\frac{\sqrt{y_0^2-x_0^2}}{arccos \frac{x_0}{y_0}}} {TEX}@@ @@{TEX()} {x=y=\frac{\sqrt{y_0^2-x_0^2}}{arccos \frac{x_0}{y_0}}} {TEX}@@
 ما این مسأله را به سختی می توانستیم بدون اصل عدم تغییر حل نماییم اسن مسأله یقیناً مسأله ای دشوار در برابر استاندارد رقابت های ریاضی می باشد.  ما این مسأله را به سختی می توانستیم بدون اصل عدم تغییر حل نماییم اسن مسأله یقیناً مسأله ای دشوار در برابر استاندارد رقابت های ریاضی می باشد.
 --- ---
 !!مثال 7  !!مثال 7
 هر یک از اعداد {TEX()} {a_1,a_2,\cdots ,a_n} {TEX} برابر 1 یا -1 هستند و داریم:  هر یک از اعداد {TEX()} {a_1,a_2,\cdots ,a_n} {TEX} برابر 1 یا -1 هستند و داریم:
 @@{TEX()} {S=a_1a_2a_3a_4+a_2a_3a_4a_5+\cdots +a_na_1a_2a_3=0} {TEX}@@ @@{TEX()} {S=a_1a_2a_3a_4+a_2a_3a_4a_5+\cdots +a_na_1a_2a_3=0} {TEX}@@
 ثابت کنید {TEX()} {4|n} {TEX}. . ثابت کنید {TEX()} {4|n} {TEX}. .
 __حل__ __حل__
  این یک مسأله در نظریهُ اعداد است برای حل مسأله باز هم از اصل عدم همخوانی استفاده کنیم. یکی از {TEX()} {a_i} {TEX}ها را به {TEX()} {-a_i} {TEX} تغییر می دهیم و تغییرات {TEX()} {S} {TEX}را بررسی می کنیم می بینیم که علامت 4 جملهُ متوالی که شامل {TEX()} {a_i} {TEX} است تغییر خواهد کرد. اگر هر 4 جمله قبلاً هم علامت بودند، {TEX()} {S} {TEX}به اندازهُ {TEX()} {\pm 8} {TEX} تغییر می کند اگر 2 تا مثبت و 2 تا منفی بودند، {TEX()} {S} {TEX}تغییری نمی کند و اگر 3 تا هم علامت بودند و یکی از علامت مخالف، {TEX()} {S} {TEX}به اندازهُ {TEX()} {\pm 4} {TEX} تغییر می کند. مشاهده می کنیم که باقیماندهُ {TEX()} {S} {TEX}در تقسیم بر 4 نیز ثابت باقی می ماند. حالا تغییرات را طوری انجام می دهیم که تمام {TEX()} {a_i} {TEX}ها برابر 1 شود مشخص است که در این حالت {TEX()} {S=n} {TEX} خواهد شد ولی باقیماندهُ آن به 4 تغییر نکرده است یعنی باقیماندهُ {TEX()} {n} {TEX}بر 4 برابر 0 است.   این یک مسأله در نظریهُ اعداد است برای حل مسأله باز هم از اصل عدم همخوانی استفاده کنیم. یکی از {TEX()} {a_i} {TEX}ها را به {TEX()} {-a_i} {TEX} تغییر می دهیم و تغییرات {TEX()} {S} {TEX}را بررسی می کنیم می بینیم که علامت 4 جملهُ متوالی که شامل {TEX()} {a_i} {TEX} است تغییر خواهد کرد. اگر هر 4 جمله قبلاً هم علامت بودند، {TEX()} {S} {TEX}به اندازهُ {TEX()} {\pm 8} {TEX} تغییر می کند اگر 2 تا مثبت و 2 تا منفی بودند، {TEX()} {S} {TEX}تغییری نمی کند و اگر 3 تا هم علامت بودند و یکی از علامت مخالف، {TEX()} {S} {TEX}به اندازهُ {TEX()} {\pm 4} {TEX} تغییر می کند. مشاهده می کنیم که باقیماندهُ {TEX()} {S} {TEX}در تقسیم بر 4 نیز ثابت باقی می ماند. حالا تغییرات را طوری انجام می دهیم که تمام {TEX()} {a_i} {TEX}ها برابر 1 شود مشخص است که در این حالت {TEX()} {S=n} {TEX} خواهد شد ولی باقیماندهُ آن به 4 تغییر نکرده است یعنی باقیماندهُ {TEX()} {n} {TEX}بر 4 برابر 0 است.
 --- ---
 !!مثال 8  !!مثال 8
  {TEX()} {2n} {TEX}سفیر به یک مهمانی دعوت شده اند که هر کدام حداکثر {TEX()} {n-1} {TEX} دشمن در بین سفرای دیگر دارند. ثابت کنید این {TEX()} {2n} {TEX}سفیر را می توان دور یک میزگرد طوری نشاند که دو طرف هر سفیر، سفیرانی قرار گرفته باشند که با او دشمن نباشند.   {TEX()} {2n} {TEX}سفیر به یک مهمانی دعوت شده اند که هر کدام حداکثر {TEX()} {n-1} {TEX} دشمن در بین سفرای دیگر دارند. ثابت کنید این {TEX()} {2n} {TEX}سفیر را می توان دور یک میزگرد طوری نشاند که دو طرف هر سفیر، سفیرانی قرار گرفته باشند که با او دشمن نباشند.
 __حل__ __حل__
 #@ #@
 @#16: @#16:
  این مسأله دارای حلی با استفاده از نظریه گراف می باشد، اما اینجا ما سعی می کنیم با استفاده از پایان پذیری آن را حل کنیم: در ابتدا افراد را به صورت تصادفی دور میزگرد می نشانیم فرض کنید {TEX()} {H} {TEX}تعداد زوج های دشمن که کنار هم هستند، باشد. باید روشی ارائه دهیم که در هر مرحله باعث کاهش مقدار {TEX()} {H} {TEX}گردد. فرض کنید {TEX()} {A} {TEX}و {TEX()} {B} {TEX}دو سفیر مجاور و دشمن باشند، به طوری که {TEX()} {B} {TEX}سمت راست {TEX()} {A} {TEX}باشد (شکل 3) ثابت می کنیم افراد مجاور {TEX()} {A^\prime} {TEX}و {TEX()} {B^\prime} {TEX}وجود دارد به طوری که {TEX()} {B^\prime} {TEX}سمت راست {TEX()} {A^\prime} {TEX}باشد و {TEX()} {(A,A^\prime )} {TEX}و {TEX()} {(B,B^\prime)} {TEX}زوج های دوست باشند. می دانیم {TEX()} {A} {TEX}حداقل {TEX()} {n} {TEX}دوست در بین سفرای کشورها دارد. دور میزگرد {TEX()} {n} {TEX}نفر نشسته اند که هر کدام دست راست یکی از این {TEX()} {n} {TEX}نفر قرار دارند. اگر همهُ این افراد با {TEX()} {B} {TEX}دشمن باشند {TEX()} {B} {TEX}بیشتر از {TEX()} {n-1} {TEX} دشمن خواهد داشت بنابراین سفیر {TEX()} {B^\prime} {TEX}وجود دارد که سمت راست سفیر {TEX()} {A^\prime} {TEX}قرار گرفته باشد به طوری که{TEX()} {(B,B^\prime )} {TEX}و {TEX()} {(A,A^\prime)} {TEX}با هم دوست باشند.   این مسأله دارای حلی با استفاده از نظریه گراف می باشد، اما اینجا ما سعی می کنیم با استفاده از پایان پذیری آن را حل کنیم: در ابتدا افراد را به صورت تصادفی دور میزگرد می نشانیم فرض کنید {TEX()} {H} {TEX}تعداد زوج های دشمن که کنار هم هستند، باشد. باید روشی ارائه دهیم که در هر مرحله باعث کاهش مقدار {TEX()} {H} {TEX}گردد. فرض کنید {TEX()} {A} {TEX}و {TEX()} {B} {TEX}دو سفیر مجاور و دشمن باشند، به طوری که {TEX()} {B} {TEX}سمت راست {TEX()} {A} {TEX}باشد (شکل 3) ثابت می کنیم افراد مجاور {TEX()} {A^\prime} {TEX}و {TEX()} {B^\prime} {TEX}وجود دارد به طوری که {TEX()} {B^\prime} {TEX}سمت راست {TEX()} {A^\prime} {TEX}باشد و {TEX()} {(A,A^\prime )} {TEX}و {TEX()} {(B,B^\prime)} {TEX}زوج های دوست باشند. می دانیم {TEX()} {A} {TEX}حداقل {TEX()} {n} {TEX}دوست در بین سفرای کشورها دارد. دور میزگرد {TEX()} {n} {TEX}نفر نشسته اند که هر کدام دست راست یکی از این {TEX()} {n} {TEX}نفر قرار دارند. اگر همهُ این افراد با {TEX()} {B} {TEX}دشمن باشند {TEX()} {B} {TEX}بیشتر از {TEX()} {n-1} {TEX} دشمن خواهد داشت بنابراین سفیر {TEX()} {B^\prime} {TEX}وجود دارد که سمت راست سفیر {TEX()} {A^\prime} {TEX}قرار گرفته باشد به طوری که{TEX()} {(B,B^\prime )} {TEX}و {TEX()} {(A,A^\prime)} {TEX}با هم دوست باشند.
 مطابق شکل 3 آرایش جدیدی از افراد با {TEX()} {H} {TEX}کمتر می توان ساخت. دقت کنید در شکل جدید، قرار گرفتن افراد بین {TEX()} {B} {TEX}و {TEX()} {A^\prime} {TEX}در جهت خلاف قرار گرفتن قبلی است.  مطابق شکل 3 آرایش جدیدی از افراد با {TEX()} {H} {TEX}کمتر می توان ساخت. دقت کنید در شکل جدید، قرار گرفتن افراد بین {TEX()} {B} {TEX}و {TEX()} {A^\prime} {TEX}در جهت خلاف قرار گرفتن قبلی است.
 ::{picture=img/daneshnameh_up/3/33/com0040d.jpg}:: ::{picture=img/daneshnameh_up/3/33/com0040d.jpg}::
-مسأله فوق یک مساألهُ نظریه گراف است و معادل این مسأله است که اگر در یک گراف ساده با {TEX()} {n} {TEX}رأس درجهُ هر رأس بزرگتر یا مساوی {TEX()} {\frac{n}{2}} {TEX} باشد آنگاه آن گراف دارای دور هامیلتونی است. روش حل دیگر این مسأله از طریق استقراء قهقرایی روی تعداد یال های گراف است. حالت پایهُ استقراء حالتی است که گراف ساده و کامل داریم. +مسأله فوق یک مساألهُ نظریه گراف است و معادل این مسأله است که اگر در یک گراف ساده با {TEX()} {n} {TEX}رأس درجهُ هر رأس بزرگتر یا مساوی {TEX()} {\frac{n}{2}} {TEX} باشد آنگاه آن گراف دارای دور هامیلتونی است. روش حل دیگر این مسأله از طریق ((استقرا قهقرایی)) روی تعداد یال های گراف است. حالت پایهُ ((استقرا)) حالتی است که گراف ساده و کامل داریم.
 --- ---
 !!مثال 9 !!مثال 9
  به هر رأس یک پنج ضلعی عدد صحیح {TEX()} {(i=1,\cdots , 5) x_i} {TEX} را نسبت می دهیم به طوری که {TEX()} {s=\sum_{i=1}^{5} x_i >0} {TEX} در هر مرحله 3 عدد {TEX()} {x,y,z} {TEX}که به ترتیب اعداد نسبت داده شده به 3 رأس متوالی پنج ضلعی هستند را انتخاب می کنیم به طوری که {TEX()} {y<0} {TEX} باشد و سه تایی {TEX()} {(x,y,z)} {TEX} را تبدیل به سه تایی {TEX()} {(x+y,-y,z+y)} {TEX} می کنیم و این کار را تا زمانی که عدد کوچکتر از صفری وجود داشته باشد ادامه می دهیم. آیا این عمل پایان می یابد یا خیر؟ (این مسأله مشکلترین مسألهُ المپیاد بین المللی ریاضی سال 1986 بود).   به هر رأس یک پنج ضلعی عدد صحیح {TEX()} {(i=1,\cdots , 5) x_i} {TEX} را نسبت می دهیم به طوری که {TEX()} {s=\sum_{i=1}^{5} x_i >0} {TEX} در هر مرحله 3 عدد {TEX()} {x,y,z} {TEX}که به ترتیب اعداد نسبت داده شده به 3 رأس متوالی پنج ضلعی هستند را انتخاب می کنیم به طوری که {TEX()} {y<0} {TEX} باشد و سه تایی {TEX()} {(x,y,z)} {TEX} را تبدیل به سه تایی {TEX()} {(x+y,-y,z+y)} {TEX} می کنیم و این کار را تا زمانی که عدد کوچکتر از صفری وجود داشته باشد ادامه می دهیم. آیا این عمل پایان می یابد یا خیر؟ (این مسأله مشکلترین مسألهُ المپیاد بین المللی ریاضی سال 1986 بود).
 __حل__ __حل__
 #@ #@
 @#16: @#16:
  این عمل همیشه پایان پذیر است. کلید اثبات (همانند مثال های 4 و 8) یافتن تابع صحیح {TEX()} {f(x_1,\cdots ,x_5)} {TEX} است به طوری که مقدار {TEX()} {f} {TEX}در هر مرحله که 3 عدد را عوض می کنیم کاهش یابد. از 11 دانش آموزی که این مسأله را حل کردند یکی تابعی مشابه تابع زیر معرفی کرد:   این عمل همیشه پایان پذیر است. کلید اثبات (همانند مثال های 4 و 8) یافتن تابع صحیح {TEX()} {f(x_1,\cdots ,x_5)} {TEX} است به طوری که مقدار {TEX()} {f} {TEX}در هر مرحله که 3 عدد را عوض می کنیم کاهش یابد. از 11 دانش آموزی که این مسأله را حل کردند یکی تابعی مشابه تابع زیر معرفی کرد:
 @@{TEX()} {f(x_1,x_2,x_3,x_4,x_5)=\sum_{i=1}^5 (x_i-x_{i+2})^2 \ , \ x_6=x_1,x_7=x_2} {TEX}@@ @@{TEX()} {f(x_1,x_2,x_3,x_4,x_5)=\sum_{i=1}^5 (x_i-x_{i+2})^2 \ , \ x_6=x_1,x_7=x_2} {TEX}@@
 فرض کنید {TEX()} {y=x_4<0} {TEX}. در این صورت اگر {TEX()} {f_{new}} {TEX} مقدار {TEX()} {f} {TEX}پس از انجام یک تغییر به مرکزیت {TEX()} {x_4} {TEX} باشد و {TEX()} {f_{old}} {TEX} مقدار {TEX()} {f} {TEX}قبل از تغییر باشد داریم:  فرض کنید {TEX()} {y=x_4<0} {TEX}. در این صورت اگر {TEX()} {f_{new}} {TEX} مقدار {TEX()} {f} {TEX}پس از انجام یک تغییر به مرکزیت {TEX()} {x_4} {TEX} باشد و {TEX()} {f_{old}} {TEX} مقدار {TEX()} {f} {TEX}قبل از تغییر باشد داریم:
 @@{TEX()} {f_{new}-f_{old}=2sx_4} {TEX}@@ @@{TEX()} {f_{new}-f_{old}=2sx_4} {TEX}@@
-و از آنجا که {TEX()} {s>0} {TEX} مقدار {TEX()} {f_{new}-f_{old}} {TEX} منفی است یعنی تابع {TEX()} {f} {TEX}در هر مرحله در حال کاهش است. بنابراین اگر این عمل پایان ناپذیر باشد ما یک دنبالهُ نامتناهی اکیداً نزولی از اعداد صحیح و غیرمنفی یافته ایم که غیرممکن است. +و از آنجا که {TEX()} {s>0} {TEX} مقدار {TEX()} {f_{new}-f_{old}} {TEX} منفی است یعنی تابع {TEX()} {f} {TEX}در هر مرحله در حال کاهش است. بنابراین اگر این عمل پایان ناپذیر باشد ما یک ((دنبالهُ)) نامتناهی ((اکیداً نزولی)) از اعداد صحیح و غیرمنفی یافته ایم که غیرممکن است.
 «برنالد چازل» از دانشگاه پرینستون این سوال را مطرح کرد: چند مرحله لازم است تا الگوریتم متوقف شود. او دنبالهُ نامتناهی {TEX()} {S} {TEX}از مجموع هایی را در نظر گرفت که به صورت{TEX()} {S(i,j)=x_i+\cdots , x_{j-1}} {TEX} تعریف می شوند. ({TEX()} {\cdots , x_7=x_2,x_6=x_1} {TEX}) ({TEX()} {(j>i \ , \ 1 \le i \le 5} {TEX}). وقتی به عنوان مثال {TEX()} {x_4} {TEX} به {TEX()} {-x_4} {TEX} (همان گونه که در بالا مثال گفته شد) تبدیل می شود تنها جملهُ منفی که بین اعداد {TEX()} {S} {TEX}مثبت می شود {TEX()} {S(4,5)=x_4} {TEX} است که تغییر می کند و به {TEX()} {-x_4} {TEX} (همان گونه که در مثال بالا گفته شد) تبدیل می شود تنها جملهُ منفی که بین اعداد {TEX()} {S} {TEX}که منفی بود مثبت می شود. ار آنجا که {TEX()} {S>0} {TEX} است، {TEX()} {S} {TEX}شامل تعداد متناهی عدد منفی می باشد بنابراین تعداد مراحل لازم برای توقف برابر تعداد اعداد منفی داخل {TEX()} {S} {TEX}می باشد همچنین دیدیم که نیازی به صحیح بودن مقدار {TEX()} {x_i} {TEX}ها هم نیست.  «برنالد چازل» از دانشگاه پرینستون این سوال را مطرح کرد: چند مرحله لازم است تا الگوریتم متوقف شود. او دنبالهُ نامتناهی {TEX()} {S} {TEX}از مجموع هایی را در نظر گرفت که به صورت{TEX()} {S(i,j)=x_i+\cdots , x_{j-1}} {TEX} تعریف می شوند. ({TEX()} {\cdots , x_7=x_2,x_6=x_1} {TEX}) ({TEX()} {(j>i \ , \ 1 \le i \le 5} {TEX}). وقتی به عنوان مثال {TEX()} {x_4} {TEX} به {TEX()} {-x_4} {TEX} (همان گونه که در بالا مثال گفته شد) تبدیل می شود تنها جملهُ منفی که بین اعداد {TEX()} {S} {TEX}مثبت می شود {TEX()} {S(4,5)=x_4} {TEX} است که تغییر می کند و به {TEX()} {-x_4} {TEX} (همان گونه که در مثال بالا گفته شد) تبدیل می شود تنها جملهُ منفی که بین اعداد {TEX()} {S} {TEX}که منفی بود مثبت می شود. ار آنجا که {TEX()} {S>0} {TEX} است، {TEX()} {S} {TEX}شامل تعداد متناهی عدد منفی می باشد بنابراین تعداد مراحل لازم برای توقف برابر تعداد اعداد منفی داخل {TEX()} {S} {TEX}می باشد همچنین دیدیم که نیازی به صحیح بودن مقدار {TEX()} {x_i} {TEX}ها هم نیست.
 __ملاحظه __ __ملاحظه __
  جالب است که یک فرمول را با کامپیوتر بیابیم که این فرمول برای هر ورودی {TEX()} {(a,b,c,d,e)} {TEX} از اعداد تعداد مراحل لازم تا زمان توقف را بیابد. یافتن این فرمول برای حالت های که {TEX()} {S=1} {TEX} است چندان مشکل نیست برای مثال برای ورودی {TEX()} {(n,n,1-4n,n,n)} {TEX} تعداد مراحل {TEX()} {20n-10} {TEX} است.   جالب است که یک فرمول را با کامپیوتر بیابیم که این فرمول برای هر ورودی {TEX()} {(a,b,c,d,e)} {TEX} از اعداد تعداد مراحل لازم تا زمان توقف را بیابد. یافتن این فرمول برای حالت های که {TEX()} {S=1} {TEX} است چندان مشکل نیست برای مثال برای ورودی {TEX()} {(n,n,1-4n,n,n)} {TEX} تعداد مراحل {TEX()} {20n-10} {TEX} است.
 #@ #@
 @#16: @#16:
 --- ---
 !!مثال 10 . کاهش مربع ها (یک تحقیق تجربی)  !!مثال 10 . کاهش مربع ها (یک تحقیق تجربی)
- از چهارتایی {TEX()} {S=(a,b,c,d)} {TEX} از اعداد صحیح و مثبت شروع می کنیم و چهارتایی جدید {TEX()} {S_1=T(S)=(|a-b|,|b-c|,|c-d|,|d-a|} {TEX} را از {TEX()} {S} {TEX}به دست می آوریم به همین ترتیب دنبالهُ نامتناهی {TEX()} {S_1,S_2=T(S_1),S_3=T(S_2), \cdots} {TEX} را می سازیم آیا همیشه در این دنباله ها به چهارتایی های {TEX()} {(0,0,0,0)} {TEX} می رسیم. + از چهارتایی {TEX()} {S=(a,b,c,d)} {TEX} از ((اعداد صحیح)) و مثبت شروع می کنیم و چهارتایی جدید {TEX()} {S_1=T(S)=(|a-b|,|b-c|,|c-d|,|d-a|} {TEX} را از {TEX()} {S} {TEX}به دست می آوریم به همین ترتیب دنبالهُ نامتناهی {TEX()} {S_1,S_2=T(S_1),S_3=T(S_2), \cdots} {TEX} را می سازیم آیا همیشه در این دنباله ها به چهارتایی های {TEX()} {(0,0,0,0)} {TEX} می رسیم.
 __حل__ __حل__
  برای اینکه جواب را حدس بزنیم چند مثال شروع می کنیم:   برای اینکه جواب را حدس بزنیم چند مثال شروع می کنیم:
 @@ {TEX()} {(0,3,1,0,13)\rightarrow (3,7,3,13)\rightarrow (4,4,10,10)\rightarrow (0,6,0,6)\rightarrow (6,6,6,6)\rightarrow (0,0,0,0)} {TEX} @@  @@ {TEX()} {(0,3,1,0,13)\rightarrow (3,7,3,13)\rightarrow (4,4,10,10)\rightarrow (0,6,0,6)\rightarrow (6,6,6,6)\rightarrow (0,0,0,0)} {TEX} @@
 @@{TEX()} {(8,7,3,107)\rightarrow (9,14,104,99)\rightarrow (0,90,5,90)\rightarrow (85,85,85,85)\rightarrow(0,0,0,0)} {TEX}@@ @@{TEX()} {(8,7,3,107)\rightarrow (9,14,104,99)\rightarrow (0,90,5,90)\rightarrow (85,85,85,85)\rightarrow(0,0,0,0)} {TEX}@@
 @@ {TEX()} {(91,108,95,294)\rightarrow (17,13,99,203)\rightarrow (4,86,104,186)\rightarrow (82,18,82,182) \rightarrow (64,64,100,100)} {TEX}@@ @@ {TEX()} {(91,108,95,294)\rightarrow (17,13,99,203)\rightarrow (4,86,104,186)\rightarrow (82,18,82,182) \rightarrow (64,64,100,100)} {TEX}@@
 @@ {TEX()} {\rightarrow (0,36,0,36)\rightarrow (36,36,36,36) \rightarrow (0,0,0,0)} {TEX}@@ @@ {TEX()} {\rightarrow (0,36,0,36)\rightarrow (36,36,36,36) \rightarrow (0,0,0,0)} {TEX}@@
 --- ---
 !مشاهدات  !مشاهدات
 !!(1) !!(1)
  اگر{TEX()} { max \ S } {TEX} را بزرگترین عضو 4 تایی {TEX()} {S} {TEX}تعریف کنیم در این صورت:   اگر{TEX()} { max \ S } {TEX} را بزرگترین عضو 4 تایی {TEX()} {S} {TEX}تعریف کنیم در این صورت:
 @@{TEX()} {max \ S_{i+1} \le max \ S_i} {TEX}@@ @@{TEX()} {max \ S_{i+1} \le max \ S_i} {TEX}@@
 و همچنین تا زمانی که {TEX()} {max \ S_i >0} {TEX} داریم:  و همچنین تا زمانی که {TEX()} {max \ S_i >0} {TEX} داریم:
 @@{TEX()} {max \ S_{i+4}<max \ S_i} {TEX}@@ @@{TEX()} {max \ S_{i+4}<max \ S_i} {TEX}@@
 اگر این نامساوی ها اثبات شود، مسأله ثابت شده است.  اگر این نامساوی ها اثبات شود، مسأله ثابت شده است.
 !! (2)  !! (2)
 {TEX()} {S} {TEX}و {TEX()} {tS} {TEX} (4 تایی که از ضرب اعداد {TEX()} {S} {TEX}در عدد {TEX()} {t} {TEX}به دست می آید) دارای یک طول عمر می باشند.  {TEX()} {S} {TEX}و {TEX()} {tS} {TEX} (4 تایی که از ضرب اعداد {TEX()} {S} {TEX}در عدد {TEX()} {t} {TEX}به دست می آید) دارای یک طول عمر می باشند.
 #@ #@
 @#16: @#16:
 !!(3) !!(3)
  بعد از 4 مرحله هر 4 عدد به دست آمده حتماً زوج خواهند بود. برای اثبات این نکته می توانیم محاسبات را به پیمانهُ 2 انجام دهیم و تمام حالت ها را آزمایش کنیم به خاطر اینکه تغییر دوری جای 4 تایی ها تأثیری در استدلال ندارد تنها چند حالت ساده را لازم است آزمایش کنیم:   بعد از 4 مرحله هر 4 عدد به دست آمده حتماً زوج خواهند بود. برای اثبات این نکته می توانیم محاسبات را به پیمانهُ 2 انجام دهیم و تمام حالت ها را آزمایش کنیم به خاطر اینکه تغییر دوری جای 4 تایی ها تأثیری در استدلال ندارد تنها چند حالت ساده را لازم است آزمایش کنیم:
 @@{TEX()} {0001\rightarrow 0011 \rightarrow 0101 \rightarrow 1111 \rightarrow 0000} {TEX}@@ @@{TEX()} {0001\rightarrow 0011 \rightarrow 0101 \rightarrow 1111 \rightarrow 0000} {TEX}@@
 و و
 @@بقیه مشابه بالا {TEX()} {1110 \rightarrow 0011 \rightarrow } {TEX}@@ @@بقیه مشابه بالا {TEX()} {1110 \rightarrow 0011 \rightarrow } {TEX}@@
 --- ---
 __ملاحظه__ __ملاحظه__
  در اثبات مشاهدهُ (3) از تقارن دوری استفاده کردیم ما همیشه بایستی بتوانیم در صورت امکان از این ایده استفاده کنیم. البته این بخش به این موضوع اختصاص ندارد.   در اثبات مشاهدهُ (3) از تقارن دوری استفاده کردیم ما همیشه بایستی بتوانیم در صورت امکان از این ایده استفاده کنیم. البته این بخش به این موضوع اختصاص ندارد.
-مشاهدهُ (3) اثبات شد. پس حداکثر بعد از 4 مرحله ما با 4 عدد زوج سروکار داریم و حداکثر بعد از 8 مرحله هر جمله مضرب {TEX()} {2^2} {TEX} خواهد بود و ... و بعد از {TEX()} {4k} {TEX} مرحله هر عدد دنباله مضرب {TEX()} {2^k} {TEX} خواهد بود. اگر {TEX()} {k} {TEX}را طوری تعیین کنیم که {TEX()} {max \ S <2^k} {TEX} باشد در این صورت چون بیشترین عدد {TEX()} {S} {TEX}در چهار تایی های بعدی بزرگتر نمی شود بنابراین پس از {TEX()} {4k} {TEX} مرحله بایستی هر 4 عدد برابر 0 باشد (چون بعد از {TEX()} {4k} {TEX} مرحله تمام اعداد مضرب {TEX()} {2^k} {TEX} هستند ولی همگی از {TEX()} {2^k} {TEX} کوچکترند بنابراین باید 0 باشند.) . اگر مشاهدهُ اول هم اثبات شود می توان روش دیگری برای حل مسأله به دست آورد. برای اثبات مشاهدهُ اول می توان از اصل اکسترمال استفاده کرد انتخاب عنصر مازیمال! که در بخش 3 به آن می پردازیم. +مشاهدهُ (3) اثبات شد. پس حداکثر بعد از 4 مرحله ما با 4 عدد زوج سروکار داریم و حداکثر بعد از 8 مرحله هر جمله مضرب {TEX()} {2^2} {TEX} خواهد بود و ... و بعد از {TEX()} {4k} {TEX} مرحله هر عدد دنباله مضرب {TEX()} {2^k} {TEX} خواهد بود. اگر {TEX()} {k} {TEX}را طوری تعیین کنیم که {TEX()} {max \ S <2^k} {TEX} باشد در این صورت چون بیشترین عدد {TEX()} {S} {TEX}در چهار تایی های بعدی بزرگتر نمی شود بنابراین پس از {TEX()} {4k} {TEX} مرحله بایستی هر 4 عدد برابر 0 باشد (چون بعد از {TEX()} {4k} {TEX} مرحله تمام اعداد مضرب {TEX()} {2^k} {TEX} هستند ولی همگی از {TEX()} {2^k} {TEX} کوچکترند بنابراین باید 0 باشند.) . اگر مشاهدهُ اول هم اثبات شود می توان روش دیگری برای حل مسأله به دست آورد. برای اثبات مشاهدهُ اول می توان از اصل اکسترمال استفاده کرد انتخاب عنصر مازیمال! که در بخش 3 به آن می پردازیم.
 --- ---
 ! نتایج  ! نتایج
 !! الف !! الف
  اگر از اعداد حقیقی شروع کنیم برای مثال:   اگر از اعداد حقیقی شروع کنیم برای مثال:
 ::{picture=img/daneshnameh_up/9/9b/com0040e.jpg} ::  ::{picture=img/daneshnameh_up/9/9b/com0040e.jpg} ::
 می توان نتایج خاصی به دست آورد. که هنوز اثبات نشده است. آیا همیشه به {TEX()} {(0,0,0,0)} {TEX} می رسیم؟ فرض کنید {TEX()} {S=(1,t,t^2,t^3)} {TEX} داریم:  می توان نتایج خاصی به دست آورد. که هنوز اثبات نشده است. آیا همیشه به {TEX()} {(0,0,0,0)} {TEX} می رسیم؟ فرض کنید {TEX()} {S=(1,t,t^2,t^3)} {TEX} داریم:
 #@ #@
 @#16: @#16:
 @@{TEX()} {T(S)=[(t-1),t(t-1),(t-1)^2,(t-1)(t^2+t+1)]} {TEX}@@ @@{TEX()} {T(S)=[(t-1),t(t-1),(t-1)^2,(t-1)(t^2+t+1)]} {TEX}@@
 اگر {TEX()} {t} {TEX}به گونه ای اختیار شود که {TEX()} {t^3=t^2+t+1} {TEX} شود. این عمل هرگز پایان نمی یابد (برای مثال اگر {TEX()} {t=1.8392867552} {TEX}) همچنین این مقدار {TEX()} {t} {TEX}با صرف نظر از تغییراتی به صورت {TEX()} {f(t)=at+b} {TEX} منحصر به فرد خواهد بود.  اگر {TEX()} {t} {TEX}به گونه ای اختیار شود که {TEX()} {t^3=t^2+t+1} {TEX} شود. این عمل هرگز پایان نمی یابد (برای مثال اگر {TEX()} {t=1.8392867552} {TEX}) همچنین این مقدار {TEX()} {t} {TEX}با صرف نظر از تغییراتی به صورت {TEX()} {f(t)=at+b} {TEX} منحصر به فرد خواهد بود.
 !!ب !!ب
  از {TEX()} {S=(a_0,a_1,\cdots ,a_{n-1}} {TEX} شروع می کنیم و فرض می کنیم {TEX()} {a_i} {TEX}ها اعداد صحیح غیرمنفی   از {TEX()} {S=(a_0,a_1,\cdots ,a_{n-1}} {TEX} شروع می کنیم و فرض می کنیم {TEX()} {a_i} {TEX}ها اعداد صحیح غیرمنفی
 هستند. برای {TEX()} {n=2} {TEX} پس از 1 مرحله به {TEX()} {(0,0)} {TEX} می رسیم. برای {TEX()} {n=3} {TEX} داریم:  هستند. برای {TEX()} {n=2} {TEX} پس از 1 مرحله به {TEX()} {(0,0)} {TEX} می رسیم. برای {TEX()} {n=3} {TEX} داریم:
 @@{TEX()} {001 \rightarrow 101\rightarrow 110 \rightarrow 011} {TEX}@@ @@{TEX()} {001 \rightarrow 101\rightarrow 110 \rightarrow 011} {TEX}@@
 همچنین برای {TEX()} {n=5} {TEX} داریم:  همچنین برای {TEX()} {n=5} {TEX} داریم:
 @@{TEX()} {00011\rightarrow 00101\rightarrow 01111 \rightarrow 10001 \rightarrow 10010 \rightarrow 10111 \rightarrow 11000 \rightarrow 01001 \rightarrow 11011} {TEX}@@  @@{TEX()} {00011\rightarrow 00101\rightarrow 01111 \rightarrow 10001 \rightarrow 10010 \rightarrow 10111 \rightarrow 11000 \rightarrow 01001 \rightarrow 11011} {TEX}@@
 @@{TEX()} {\rightarrow 01100 \rightarrow 10100 \rightarrow 11101 \rightarrow 00110 \rightarrow 01010 \rightarrow 11110 \rightarrow 00011} {TEX}@@ @@{TEX()} {\rightarrow 01100 \rightarrow 10100 \rightarrow 11101 \rightarrow 00110 \rightarrow 01010 \rightarrow 11110 \rightarrow 00011} {TEX}@@
 که یک حلقه به طول 15 می باشد.  که یک حلقه به طول 15 می باشد.
 --- ---
 !مسئله !مسئله
 1.طول حلقه ها را برای {TEX()} {n=6} {TEX} (یا {TEX()} {n=8} {TEX}) با دنبالهُ{TEX()} {000001000011} {TEX} بیابید.  1.طول حلقه ها را برای {TEX()} {n=6} {TEX} (یا {TEX()} {n=8} {TEX}) با دنبالهُ{TEX()} {000001000011} {TEX} بیابید.
 2.نشان دهید برای {TEX()} {n=8} {TEX} الگوریتم با ورودی{TEX()} {00000011} {TEX} متوقف می شود.  2.نشان دهید برای {TEX()} {n=8} {TEX} الگوریتم با ورودی{TEX()} {00000011} {TEX} متوقف می شود.
 3.نشان دهید برای {TEX()} {n=2^r} {TEX} همیشه به دنبالهُ {TEX()} {(0,0,\cdots , 0)} {TEX} می رسیم و برای {TEX()} {n\neq 2^r} {TEX} همیشه به دنباله ای از حلقه ها تکرار شونده می رسیم که شامل تنها 2 عدد می باشند که یکی 0 و دیگری غیرصفر است برای اثبات این قضیه می توان از اثبات مشاهدهُ 2 استفاده کرد.  3.نشان دهید برای {TEX()} {n=2^r} {TEX} همیشه به دنبالهُ {TEX()} {(0,0,\cdots , 0)} {TEX} می رسیم و برای {TEX()} {n\neq 2^r} {TEX} همیشه به دنباله ای از حلقه ها تکرار شونده می رسیم که شامل تنها 2 عدد می باشند که یکی 0 و دیگری غیرصفر است برای اثبات این قضیه می توان از اثبات مشاهدهُ 2 استفاده کرد.
 4.فرض کنیم {TEX()} {c(n)} {TEX} حداکثر طول حلقهُ تکرار شونده برای {TEX()} {n\neq 2^r} {TEX} باشد ثابت کنید {TEX()} {c(2n)=2c(n)} {TEX}.  4.فرض کنیم {TEX()} {c(n)} {TEX} حداکثر طول حلقهُ تکرار شونده برای {TEX()} {n\neq 2^r} {TEX} باشد ثابت کنید {TEX()} {c(2n)=2c(n)} {TEX}.
 5.ثابت کنید که برای {TEX()} {n} {TEX}های فرد دنبالهُ {TEX()} {(0,0,\cdots ,0,1,1)} {TEX} از همان ابتدا روی حلقهُ تکرار شونده است.  5.ثابت کنید که برای {TEX()} {n} {TEX}های فرد دنبالهُ {TEX()} {(0,0,\cdots ,0,1,1)} {TEX} از همان ابتدا روی حلقهُ تکرار شونده است.
 6.جبری کردن. به دنبالهُ {TEX()} {(a_0,a_1,\cdots ,a_{n-1}} {TEX} چندجمله ای {TEX()} {\rho (x)=a_{n-1}+a_{n-2}x+\cdots +a_0x^{n-1}} {TEX} را اختصاص می دهیم که در آن {TEX()} {x^n=1} {TEX} ({TEX()} {x} {TEX}یکی از ریشه های {TEX()} {n} {TEX}ام عدد 1 است در بحث اعداد مختلط ثابت می شود عدد 1، {TEX()} {n} {TEX}تا ریشهُ {TEX()} {n} {TEX}ام متمایز دارد) در این صورت چندجمله ای {TEX()} {(1+x) \rho (x)} {TEX} به دنبالهُ {TEX()} {T(S)} {TEX} تعلق دارد. آیا می توانید از این جبری کردن استفاده نمایید.  6.جبری کردن. به دنبالهُ {TEX()} {(a_0,a_1,\cdots ,a_{n-1}} {TEX} چندجمله ای {TEX()} {\rho (x)=a_{n-1}+a_{n-2}x+\cdots +a_0x^{n-1}} {TEX} را اختصاص می دهیم که در آن {TEX()} {x^n=1} {TEX} ({TEX()} {x} {TEX}یکی از ریشه های {TEX()} {n} {TEX}ام عدد 1 است در بحث اعداد مختلط ثابت می شود عدد 1، {TEX()} {n} {TEX}تا ریشهُ {TEX()} {n} {TEX}ام متمایز دارد) در این صورت چندجمله ای {TEX()} {(1+x) \rho (x)} {TEX} به دنبالهُ {TEX()} {T(S)} {TEX} تعلق دارد. آیا می توانید از این جبری کردن استفاده نمایید.
 7.جدول زیر توسط کامپیوتر تولید شده است با استفاده از جدول زیر حدس هایی برای {TEX()} {c(n)} {TEX} بزنید و آنها را اثبات کنید. 7.جدول زیر توسط کامپیوتر تولید شده است با استفاده از جدول زیر حدس هایی برای {TEX()} {c(n)} {TEX} بزنید و آنها را اثبات کنید.
 ::{picture=img/daneshnameh_up/7/71/com0040f.jpg}::  ::{picture=img/daneshnameh_up/7/71/com0040f.jpg}::
 --- ---
 ! پیوند های خارجی ! پیوند های خارجی
 [http://Olympiad.roshd.ir/computer/content/pdf/0146.pdf] [http://Olympiad.roshd.ir/computer/content/pdf/0146.pdf]
- +---
!همچنین ببینید
*((اصل اکسترمال ))
*((رنگ آمیزی و همخوانیI ))
*((رنگ آمیزی و همخوانیII ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:42 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [11:27 ]   2   زینب معزی      v  c  d  s 
 پنج شنبه 16 شهریور 1385 [09:03 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..