منو
 کاربر Online
1992 کاربر online

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

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)




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

استقرای ضعیف

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



حال بهتر است به بررسی چند مثال بپردازیم.

چند مثال

مثال1

به ازای هر، ثابت کنید:

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

و از درستی آن، درستی را نتیجه بگیریم؛ یعنی:

طبق فرض استقرا داریم:

بنابراین، با اضافه کردن به طرفین تساوی داریم:

پس اثبات مساله کامل شد.



مثال2

نامساوی برنولی : به ازای هر عدد صحیح و هر عدد حقیقی ثابت کنید:

حل
برقراری پایه ی استقرا :
یا

طبق فرض استقرا داریم:

حال با توجه به این که داریم:

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




مثال3

فرض کنید تیم در یک تورنمنت (هر تیم با هر یک از تیم دیگر دقیقاً یک بار بازی کرده است) با یکدیگر بازی کرده اند. اگر هیچ دو تیمی مساوی نکرده باشند ثابت کنید دنباله از تیم ها وجود دارد به طوری که، تیم از تیم برده، تیم از تیم برده، ... و تیم از تیم برده است.
img/daneshnameh_up/5/51/comm0003a.JPG

به عنوان مثال شکل بالا یک تورنمنت 5 رأسی را نشان می دهد که در آن تیم 5 از تیم 3، تیم 3 از تیم 4، تیم 4 از تیم 2 و تیم 2 از تیم 1 برده است.
حل
پایه ی استقرا : در یک تورنمنت تیمی، دنباله ی (تنها تیم شرکت کننده) جواب است.
img/daneshnameh_up/8/8c/comm0003b.JPG

حال فرض کنید برای هر تورنمنت با تیم، چنین دنباله ای وجود دارد. می خواهیم ثابت کنیم برای هر تورنمنت تیمی نیز، چنین دنباله ای وجود دارد. یکی از تیم مثلاً تیم را در نظر نگیرید. با در نظر گرفتن بازی بین تیم باقی مانده، ما یک تورنمنت تیمی داریم و طبق فرض استقرا، دنباله ی از این تیم وجود دارد که تیم از تیم برده است.
img/daneshnameh_up/a/a3/comm0003c.JPG

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



مثال4

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

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



مثال5

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



مثال6

ثابت کنید برای هر عدد طبیعی می توان دایره به شعاع واحد را درون یک دایره به شعاع جا داد به طوری که هیچ دو دایره ای متقاطع نباشند (هر دو دایره حداکثر در یک نقطه می توانند با هم اشتراک داشته باشند).
حل
با استقرا روی ثابت می کنیم که دایره به شعاع واحد را می توان درون یک دایره به شعاع جا داد. برای ، دایره ها را به صورتی که در شکل نشان داده شده است قرار می دهیم.
img/daneshnameh_up/3/34/comm0003d.JPG

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



مثال7

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



مثال8

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


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

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

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

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




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


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..