تعمیم اولیه اصل استقرا II





استقرای چند پایه

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



چند مثال

مثال1

فرض کنید دنباله ای از اعداد حقیقی ناصفر باشند که در رابطه ی زیر صدق می کنند:

شرط لازم و کافی- روی و- برای این که به ازای تعداد نامتناهی مقدار، صحیح باشد را به دست آورید.
حل
بهتر است برای فهمیدن مساله چند جمله ی اول این دنباله را- بر اساس و- محاسبه کنیم؛ شاید بتوانیم یک الگوی کلی برای جمله ی عمومی این دنباله- بر اساس و- به دست آوریم.
برای چند جمله ی اول این دنباله داریم:




اگر خوب به جملات بالا نگاه کنیم می توانیم یک الگوی کلی حدس بزنیم و آن به این صورت است که

یا به عبارت دیگر:

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


پس حکم با استقرای چند پایه روی ثابت شد.


مثال2

در دو انتهای قطری از دایره، عددهای 1 را قرار داده ایم. هر یک از نیم دایره های حاصل را نصف کرده ایم و در وسط کمان هر نیم دایره، مجموع دو عددی که در دو انتهای آن وجود دارند قرار داده ایم (مرحله ی اول). در مرحله ی بعدی باز هر یک از چهار کمان حاصل را نصف کرده و در نقطه ی وسط آنها، مجموع دو عددی را که در دو انتهای آن ها است، قرار داده ایم (مرحله ی دوم). این عمل را n بار ادامه داده ایم. در پایان مرحله ی ام مجموع همه ی عددهایی را پیدا کنید که روی محیط دایره نوشته ایم.
img/daneshnameh_up/6/6f/comm0003f.JPG

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

در نتیجه حکم با استقرا روی مراحل ثابت شد.


مثال3

مجموع اعداد سطر ام مثلث زیر را بیابید.
img/daneshnameh_up/1/1b/comm0003g.JPG

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



لم

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

چند مثال

مثال1

برای عددهای می دانیم:

ثابت کنید در مجموع می توان علامت ها را طوری تعیین کرد که داشته باشیم .


حل
بیایید باز حکم را با استقرا ثابت کنیم. به ازایکه حکم واضح است. حال برای عدد حکم را درست فرض کنید یعنی فرض کنید بتوانیم در عبارت

img/daneshnameh_up/8/8f/comm0003h.JPG
جدول 4.3: طی کردن صفحات شطرنجیوبا حرکت اسب

علامت های مثبت و منفی را طوری انتخاب کنیم که باشد.
می خواهیم ثابت کنیم در عبارت

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


پس با توجه به این که می باشد. براساس این که مقدار در کدام یک از دو محدوده ی یا باشد، می توان عبارت را طوری علامت گذاری کرد که باشد.



مثال2

ثابت کنید اسب بازی شطرنج را روی صفحه ی شطرنجی می توان طوری حرکت داد که در همه ی خانه ها، و در ضمن در هر کدام، تنها یک بار قرار گیرد.
حل
در مسایلی مثل مساله ی فوق که مسئله به صورت پارامتری داده نشده است ما باید حدس بزنیم که مساله برای چه پارامترهایی درست است که 2001 هم یکی از آنها باشد. به عبارت دیگر باید رابطه ی بین هایی را پیدا کنیم که مسئله برای آنها درست است و 2001 هم در آن رابطه صدق می کند؛ سپس با استفاده از استقرا درستی آن مسئله را برای آن ها ثابت کنیم. اگر این کار ار انجام دهیم مسئله برای آن عدد خاص هم ثابت شده است.
پس ابتدا درستی حکم را برای صفحات شطرنجی ، وقتی کوچک باشد امتحان می کنیم. می بینیم که حکم به ازایدرست است. در جدول 3.4 حرکت اسب در صفحات شطرنجی ونشان داده شده است (اسب از خانه ی شماره ی 1 شروع می کند و از خانه ی شماره ی به خانه ی شماره یمی رود).
پس توانستیم نشان دهیم که حکم به ازای درست است. بنابراین احتمالاً باید حکم به ازای درست باشد. همان طور که در دو مثال نشان داده شده است اسب از وسط صفحه شطرنجی حرکت خود را آغاز کرده است و در خانه ی گوشه ی بالا سمت راست حرکت خود را به پایان رسانده است. همچنین حرکت اسب تا حد امکان در جهت حرکت عقربه های ساعت می باشد. پس سعی می کنیم برای n بزرگتر هم از این قوانین پیروی کنیم.
پایه ی استقرا به ازای درست است. فرض کنید اسب بتواند با شروع از مرکز یک صفحه ی شطرنجی از تمام خانه ها یک و فقط یک بار عبور کند و خود را به خانه ی گوشه ی بالای سمت راست، برساند. می خواهیم ثابت کنیم می تواند در صفحه ی شطرنجی نیز این کار را انجام دهد.
ابتدا اسب صفحه ی شطرنجی وسطی را طبق فرض استقرا پیمایش می کند. حالا در خانه یقرار دارد و فقط ستون های و سطرهای طی نشده اند. حال برای طی کردن خانه های باقی مانده از خانه های به ترتیب به خانه های زیر می رویم (در جهت عقربه های ساعت حرکت می کنیم).


img/daneshnameh_up/c/c2/comm0003i.JPG
جدول 4.4: طی کردن صفحه ی شطرنجیبا حرکت اسب


















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

مثال3

عدد طبیعی دلخواه است. یک ترتیب دلخواه از اعداد 1 تا که در آن هر یک از اعداد 1 تا دقیقاً یک بار آمده باشند را یک جایگشت از می نامیم. می گوییم جایگشت در دنباله ی ظاهر شده است، اگر اندیس های وجود داشته باشند به طوری که برای هر داشته باشیم. به عنوان مثال جایگشت 2 , 3 , 1 در دنباله ی 3 , 2 , 3 , 2 , 1 , 3 ظاهر شده است.
یک دنباله از اعداد 1 تا «دنباله ی جالب» نامیده می شود، اگر هر جایگشت دلخواهی از
در این دنباله ظاهر شده باشد.
ثابت کنید برای هر عدد طبیعی حداقل یک دنباله ی جالب به طول وجود دارد.


حل
راه حل اول:
اگر بخواهیم از استقرا استفاده کنیم باید ساختار ساختن دنباله ی جالب برای از ساختار دنباله ی جالب برای به دست آید. بنابراین با این فرض بیایید چند دنباله ی جالب برای
بسازیم.
img/daneshnameh_up/a/a1/comm0003j.JPG

در حالت کلی دنباله ی جالب به طول را برای به این صورت می سازیم. ابتدا یک دنباله ی جالب به طول برایمی سازیم، سپس را به آن اضافه می کنیم و بعد باز یک دنباله ی جالب به طول برای به انتهای آن اضافه می کنیم. به عبارت دیگر اگردنباله ی جالب برای باشد، داریم:
واضح است که طول این دنباله برابر با می باشد و یک دنباله ی جالب برای می باشد. زیرا اگر یک جایگشت از اعداد 1 تا باشد و باشد، طبق فرض استقرا زیر دنباله ی در دنباله ی جالب سمت چپ برایوجود دارد و باز طبق فرض استقرا زیر دنباله ی در دنباله ی جالب سمت راست برای وجود دارد، بنابراین جایگشت در دنباله ی جالب برای وجود دارد.
راه حل دوم:
اگر برای یک دنباله ی جالب ساخته باشیم، برای نیز یک دنباله ی جالب به این شکل می سازیم که در ابتدا و انتها و همچنین بین هر دو عنصر از دنباله ی جالب برای ، عدد را می نویسیم. حال به وضوح دیده می شود که دنباله ی ساخته شده یک دنباله ی جالب برای است و اگر دنباله ی جالب برای به طول باشد، دنباله ی جالب ساخته شده برای، به طول می باشد.
img/daneshnameh_up/7/72/comm0003k.JPG

به عنوان مثال در جدول بالا دنباله های جالب به ازای، با استفاده از روش فوق ساخته شده اند.



مثال 4

نفر با شماره های 1 تا دور میزی نشسته اند و هر کدام k مهره در اختیار دارند. با شروع از نفر اول بازی زیر را انجام می دهیم. نفر او مهره ی خود را به نفر دوم می دهد و از این به بعد هر نفر که از نفر قبلی یک مهره دریافت کرده باشد دو مهره به نفر بعدی خود می دهد و اگر دو مهره دریافت کرده باشد، یک مهره به نفر بعدی می دهد. در این بازی منظور از نفر بعدی، نزدیک ترین فرد در جهت عقربه های ساعت است. به محض آن که فردی تمام مهره هایش را از دست بدهد از دور میز کنار می رود. مثلاً اگرباشد، در ابتدای بازی نفر 1 و 2 از دور میز خارج می شوند.
الف. ثابت کنید اگر و توانی از 2 باشد، بازی پایان می پذیرد.
ب.ثابت کنید اگرباشد، بازی تنها در صورتی پایان می پذیرد کهیا توانی از 2 باشند.
حل
بیایید ببینیم که اگر نفر اول مهره و بقیه ی نفرات مهره داشته باشند، چه اتفاقی می افتد. برای این منظور فرض کنید تابعی باشد که مقدار آن 1 یا0 است و بدین شکل تعریف شده است:
مقدار این تابع یک است، اگر نفر باشند و نفر اول مهره و بقیه هر کدام مهره داشته باشند و بازی تمام شدنی باشد؛ همچنین مقدار این تابع صفر است اگر بازی تمام شدنی نباشد.
حال بیاییم چند حالت را با یکدیگر بررسی کنیم فرض کنید اسم این نفر به ترتیب باشد، در ابتدای کار یک مهره به می دهد (حالا، مهره دارد)، سپس چون یک مهره دریافت کرده، دو مهره به می دهد (حالا، مهره دارد)، بعد چون دو مهره دریافت کرده، یک مهره به می دهد (حالا، مهره دارد)، سپس چون یک مهره در یافت کرده است، دو مهره به می دهد (حالا،مهره دارد) و ... .
با دنبال کردن استراتژی بالابه نتایج زیر می رسیم:
1.اگر و فرد باشد، بعد از دور اول، تعداد مهره های هر فرد به ترتیب برابر است با، و چون به نفر اول این دفعه یک مهره رسیده است پس دو مهره به نفر بعدی می دهد بنابراین بعد از یک دور دیگر به نفر اول دو مهره خواهد رسید و تعداد مهره های افراد به ترتیب برابر با می شود (مطابق شکل). یا به عبارت دیگر اگر و باشد، آن گاه است (بازی تمام نشدنی است).
img/daneshnameh_up/7/70/comm0003l.JPG

2.اگر فرد و باشد، چون نفر اول در ابتدای دور دوم حذف می شود، در پایان دور دوم، نفر، دو مهره به نفر می دهد و مهره های نفرات به ترتیب برابر با می شود. پس اگر باشد،.


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

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

http://olympiad.roshd.ir/computer/content/pdf/0006.pdf

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





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