تاریخچه ی:
تعمیم اولیه اصل استقرا I
تفاوت با نگارش: 1
| | ||V{maketoc}|| | | ||V{maketoc}|| |
| | ^@#16: | | ^@#16: |
| | !تعمیم اولیه اصل استقرا | | !تعمیم اولیه اصل استقرا |
| | !!استقرای ضعیف | | !!استقرای ضعیف |
| | __اصل استقرای ریاضی ضعیف :__ | | __اصل استقرای ریاضی ضعیف :__ |
| | اگر {TEX()} {m} {TEX}یک عدد صحیح و {TEX()} {p(n)} {TEX} یک جمله بر اساس پارامتر {TEX()} {n} {TEX}باشد، به طوری که: | | اگر {TEX()} {m} {TEX}یک عدد صحیح و {TEX()} {p(n)} {TEX} یک جمله بر اساس پارامتر {TEX()} {n} {TEX}باشد، به طوری که: |
| | الف. {TEX()} {p(m)} {TEX} برقرار باشد. | | الف. {TEX()} {p(m)} {TEX} برقرار باشد. |
| | ب. به ازای هر {TEX()} {n>m} {TEX}، {TEX()} {p(n-1) \Rightarrow p(n)} {TEX}. | | ب. به ازای هر {TEX()} {n>m} {TEX}، {TEX()} {p(n-1) \Rightarrow p(n)} {TEX}. |
| | در این صورت، به ازای هر {TEX()} {n\ge m} {TEX}، {TEX()} {p(n)} {TEX} برقرار است. | | در این صورت، به ازای هر {TEX()} {n\ge m} {TEX}، {TEX()} {p(n)} {TEX} برقرار است. |
| | __اثبات . __ | | __اثبات . __ |
| | فرض کنید که چنین نباشد، یعنی حکم برای برخی مقادیر صحیح {TEX()} {n\ge m} {TEX} صحیح نباشد. در این صورت طبق اصل خوش ترتیبی، عددی مثل p وجود دارد به طوری که: | | فرض کنید که چنین نباشد، یعنی حکم برای برخی مقادیر صحیح {TEX()} {n\ge m} {TEX} صحیح نباشد. در این صورت طبق اصل خوش ترتیبی، عددی مثل p وجود دارد به طوری که: |
| | 1.حکم به ازای {TEX()} {n=p} {TEX} برقرار نباشد. | | 1.حکم به ازای {TEX()} {n=p} {TEX} برقرار نباشد. |
| | 2.برای تمام مقادیر {TEX()} {m\ge n <p} {TEX}، حکم برقرار باشد. | | 2.برای تمام مقادیر {TEX()} {m\ge n <p} {TEX}، حکم برقرار باشد. |
| - | به عبارت دیگر {TEX()} {p} {TEX}اولین عدد صحیح بزرگ تر یا مساوی {TEX()} {n} {TEX}باشد که به ازای آن، حکم مفروض نیست. |
+ | به عبارت دیگر {TEX()} {p} {TEX}اولین ((عدد صحیح)) بزرگ تر یا مساوی {TEX()} {n} {TEX}باشد که به ازای آن، حکم مفروض نیست. |
| | واضح است که {TEX()} {p>m} {TEX} است، زیرا به ازای {TEX()} {n=m} {TEX} طبق شرط الف، حکم صحیح است. بنابراین {TEX()} {p-1} {TEX} یک عدد صحیح بزرگ تر یا مساوی {TEX()} {m} {TEX}است. از اینجا نتیجه می شود که برای عدد صحیح بعد از آن برقرار نیست و این با فرض ب، متناقض است. | | واضح است که {TEX()} {p>m} {TEX} است، زیرا به ازای {TEX()} {n=m} {TEX} طبق شرط الف، حکم صحیح است. بنابراین {TEX()} {p-1} {TEX} یک عدد صحیح بزرگ تر یا مساوی {TEX()} {m} {TEX}است. از اینجا نتیجه می شود که برای عدد صحیح بعد از آن برقرار نیست و این با فرض ب، متناقض است. |
| | {TEX()} {p(m)} {TEX} را پایه استقرا و {TEX()} {p(n-1)} {TEX} را فرض استقرا و {TEX()} {p(n)} {TEX} را حکم استقرا می گوییم. بنابراین برای اثبات یک مساله با استقرا، ابتدا باید درستی پایه استقرا را ثابت کنیم. سپس، با فرض درستی فرض استقرا، درستی حکم استقرا را نتیجه بگیریم. اگر هر کدام از دو گام فوق را انجام ندهیم، مساله ما ثابت نمی شود. | | {TEX()} {p(m)} {TEX} را پایه استقرا و {TEX()} {p(n-1)} {TEX} را فرض استقرا و {TEX()} {p(n)} {TEX} را حکم استقرا می گوییم. بنابراین برای اثبات یک مساله با استقرا، ابتدا باید درستی پایه استقرا را ثابت کنیم. سپس، با فرض درستی فرض استقرا، درستی حکم استقرا را نتیجه بگیریم. اگر هر کدام از دو گام فوق را انجام ندهیم، مساله ما ثابت نمی شود. |
| | --- | | --- |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | حال بهتر است به بررسی چند مثال بپردازیم. | | حال بهتر است به بررسی چند مثال بپردازیم. |
| | !چند مثال | | !چند مثال |
| | !!مثال1 | | !!مثال1 |
| | به ازای هر{TEX()} {n\in N} {TEX}، ثابت کنید: | | به ازای هر{TEX()} {n\in N} {TEX}، ثابت کنید: |
| | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ | | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ |
| | __حل__ | | __حل__ |
| | قدم اول در استفاده از استقرا بررسی درستی پایه ی استقرا است. پس باید بررسی کنیم که آیا{TEX()} {1=\frac{1\times 2}{2}} {TEX} ؟ می بینیم که پایه ی استقرا برقرار است. | | قدم اول در استفاده از استقرا بررسی درستی پایه ی استقرا است. پس باید بررسی کنیم که آیا{TEX()} {1=\frac{1\times 2}{2}} {TEX} ؟ می بینیم که پایه ی استقرا برقرار است. |
| | قدم دوم باید فرض کنید که {TEX()} {p(n)} {TEX} درست است یعنی: | | قدم دوم باید فرض کنید که {TEX()} {p(n)} {TEX} درست است یعنی: |
| | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ | | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ |
| | و از درستی آن، درستی {TEX()} {p(n+1)} {TEX}را نتیجه بگیریم؛ یعنی: | | و از درستی آن، درستی {TEX()} {p(n+1)} {TEX}را نتیجه بگیریم؛ یعنی: |
| | @@{TEX()} {\sum_{i=1}^{n+1} i=\frac{(n+1)(n+2)}{2}} {TEX}@@ | | @@{TEX()} {\sum_{i=1}^{n+1} i=\frac{(n+1)(n+2)}{2}} {TEX}@@ |
| | طبق فرض استقرا داریم: | | طبق فرض استقرا داریم: |
| | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ | | @@{TEX()} {\sum_{i=1}^n i=\frac{n(n+1)}{2}} {TEX}@@ |
| | بنابراین، با اضافه کردن {TEX()} {n+1} {TEX} به طرفین تساوی داریم: | | بنابراین، با اضافه کردن {TEX()} {n+1} {TEX} به طرفین تساوی داریم: |
| | @@{TEX()} {\sum_{i=1}^{n+1} i=\sum_{i=1}^n i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}} {TEX}@@ | | @@{TEX()} {\sum_{i=1}^{n+1} i=\sum_{i=1}^n i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}} {TEX}@@ |
| | پس اثبات مساله کامل شد. | | پس اثبات مساله کامل شد. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال2 | | !!مثال2 |
| - | __ نامساوی برنولی : __به ازای هر عدد صحیح{TEX()} {n\ge 0} {TEX} و هر عدد حقیقی{TEX()} {x \ge -1} {TEX} ثابت کنید: |
+ | __ نامساوی ((برنولی)) : __به ازای هر عدد صحیح{TEX()} {n\ge 0} {TEX} و هر عدد حقیقی{TEX()} {x \ge -1} {TEX} ثابت کنید: |
| | @@{TEX()} {(1+x)^n \ge 1+nx} {TEX}@@ | | @@{TEX()} {(1+x)^n \ge 1+nx} {TEX}@@ |
| | __حل __ | | __حل __ |
| | برقراری پایه ی استقرا : | | برقراری پایه ی استقرا : |
| | @@{TEX()} {1\ge 1} {TEX} یا {TEX()} {(1+x)^0 \ge 1+0x} {TEX}@@ | | @@{TEX()} {1\ge 1} {TEX} یا {TEX()} {(1+x)^0 \ge 1+0x} {TEX}@@ |
| | طبق فرض استقرا داریم: | | طبق فرض استقرا داریم: |
| | @@{TEX()} {(1+x)^n \ge 1+nx} {TEX}@@ | | @@{TEX()} {(1+x)^n \ge 1+nx} {TEX}@@ |
| | حال با توجه به این که{TEX()} {1+x\ge 0} {TEX} داریم: | | حال با توجه به این که{TEX()} {1+x\ge 0} {TEX} داریم: |
| | @@{TEX()} {(1+x)^{n+1}=(1+x)(1+x)^n \ge (1+x)(1+nx) \ge 1+(n+1)x+nx^2 \ge 1+(n+1)x} {TEX}@@ | | @@{TEX()} {(1+x)^{n+1}=(1+x)(1+x)^n \ge (1+x)(1+nx) \ge 1+(n+1)x+nx^2 \ge 1+(n+1)x} {TEX}@@ |
| | پس حکم استقرا ثابت شد و اثبات به پایان می رسد. | | پس حکم استقرا ثابت شد و اثبات به پایان می رسد. |
| | دقت کنید که اگر شرط{TEX()} {1+x \ge 0} {TEX} را نداشتیم، نمی توانستیم طرفین را در {TEX()} {1+x} {TEX} ضرب کنیم و علامت نامساوی تغییر نکند. به این مسایل دقت داشته باشید، چون می تواند باعث خطا در اثبات شود؛ به خطاهای استقرا در بخش های بعدی خواهیم پرداخت.#@ | | دقت کنید که اگر شرط{TEX()} {1+x \ge 0} {TEX} را نداشتیم، نمی توانستیم طرفین را در {TEX()} {1+x} {TEX} ضرب کنیم و علامت نامساوی تغییر نکند. به این مسایل دقت داشته باشید، چون می تواند باعث خطا در اثبات شود؛ به خطاهای استقرا در بخش های بعدی خواهیم پرداخت.#@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال3 | | !!مثال3 |
| | فرض کنید {TEX()} {n} {TEX}تیم در یک تورنمنت (هر تیم با هر یک از {TEX()} {n-1} {TEX}تیم دیگر دقیقاً یک بار بازی کرده است) با یکدیگر بازی کرده اند. اگر هیچ دو تیمی مساوی نکرده باشند ثابت کنید دنباله {TEX()} {t_1,t_2,\cdots ,t_n} {TEX} از تیم ها وجود دارد به طوری که، تیم{TEX()} {t_1} {TEX} از تیم{TEX()} {t_2} {TEX} برده، تیم{TEX()} {t_2} {TEX} از تیم{TEX()} {t_3} {TEX} برده، ... و تیم{TEX()} {t_{n-1}} {TEX} از تیم{TEX()} {t_n} {TEX} برده است. | | فرض کنید {TEX()} {n} {TEX}تیم در یک تورنمنت (هر تیم با هر یک از {TEX()} {n-1} {TEX}تیم دیگر دقیقاً یک بار بازی کرده است) با یکدیگر بازی کرده اند. اگر هیچ دو تیمی مساوی نکرده باشند ثابت کنید دنباله {TEX()} {t_1,t_2,\cdots ,t_n} {TEX} از تیم ها وجود دارد به طوری که، تیم{TEX()} {t_1} {TEX} از تیم{TEX()} {t_2} {TEX} برده، تیم{TEX()} {t_2} {TEX} از تیم{TEX()} {t_3} {TEX} برده، ... و تیم{TEX()} {t_{n-1}} {TEX} از تیم{TEX()} {t_n} {TEX} برده است. |
| | ::{picture=img/daneshnameh_up/5/51/comm0003a.JPG}:: | | ::{picture=img/daneshnameh_up/5/51/comm0003a.JPG}:: |
| | به عنوان مثال شکل بالا یک تورنمنت 5 رأسی را نشان می دهد که در آن تیم 5 از تیم 3، تیم 3 از تیم 4، تیم 4 از تیم 2 و تیم 2 از تیم 1 برده است. | | به عنوان مثال شکل بالا یک تورنمنت 5 رأسی را نشان می دهد که در آن تیم 5 از تیم 3، تیم 3 از تیم 4، تیم 4 از تیم 2 و تیم 2 از تیم 1 برده است. |
| | __حل __ | | __حل __ |
| | پایه ی استقرا : در یک تورنمنت {TEX()} {n=1} {TEX}تیمی، دنباله ی{TEX()} {t_1} {TEX} (تنها تیم شرکت کننده) جواب است. | | پایه ی استقرا : در یک تورنمنت {TEX()} {n=1} {TEX}تیمی، دنباله ی{TEX()} {t_1} {TEX} (تنها تیم شرکت کننده) جواب است. |
| | ::{picture=img/daneshnameh_up/8/8c/comm0003b.JPG}:: | | ::{picture=img/daneshnameh_up/8/8c/comm0003b.JPG}:: |
| | حال فرض کنید برای هر تورنمنت با {TEX()} {n} {TEX} تیم، چنین دنباله ای وجود دارد. می خواهیم ثابت کنیم برای هر تورنمنت {TEX()} {n+1} {TEX}تیمی نیز، چنین دنباله ای وجود دارد. یکی از {TEX()} {n+1} {TEX} تیم مثلاً تیم{TEX()} {t_{n+1}} {TEX} را در نظر نگیرید. با در نظر گرفتن بازی بین {TEX()} {n} {TEX} تیم باقی مانده، ما یک تورنمنت {TEX()} {n} {TEX} تیمی داریم و طبق فرض استقرا، دنباله ی{TEX()} {t_1,t_2,\cdots ,t_n} {TEX} از این {TEX()} {n} {TEX} تیم وجود دارد که تیم{TEX()} {t_i} {TEX} {TEX()} {(i=1,2,\cdots ,n-1)} {TEX} از تیم{TEX()} {t_{i+1}} {TEX} برده است. | | حال فرض کنید برای هر تورنمنت با {TEX()} {n} {TEX} تیم، چنین دنباله ای وجود دارد. می خواهیم ثابت کنیم برای هر تورنمنت {TEX()} {n+1} {TEX}تیمی نیز، چنین دنباله ای وجود دارد. یکی از {TEX()} {n+1} {TEX} تیم مثلاً تیم{TEX()} {t_{n+1}} {TEX} را در نظر نگیرید. با در نظر گرفتن بازی بین {TEX()} {n} {TEX} تیم باقی مانده، ما یک تورنمنت {TEX()} {n} {TEX} تیمی داریم و طبق فرض استقرا، دنباله ی{TEX()} {t_1,t_2,\cdots ,t_n} {TEX} از این {TEX()} {n} {TEX} تیم وجود دارد که تیم{TEX()} {t_i} {TEX} {TEX()} {(i=1,2,\cdots ,n-1)} {TEX} از تیم{TEX()} {t_{i+1}} {TEX} برده است. |
| | ::{picture=img/daneshnameh_up/a/a3/comm0003c.JPG}:: | | ::{picture=img/daneshnameh_up/a/a3/comm0003c.JPG}:: |
| | اگر تیم{TEX()} {t_{n+1}} {TEX} به تیم{TEX()} {t_n} {TEX} باخته باشد، دنباله ی{TEX()} {t_1,t_2,\cdots ,t_n ,t_{n+1}} {TEX} جواب مساله است. همچنین اگر تیم{TEX()} {t_{n+1}} {TEX} تیم{TEX()} {t_1} {TEX} را برده باشد، دنباله ی{TEX()} {t_{n+1},t_1,t_2,\cdots ,t_n} {TEX} جواب مساله است. در غیر این حالات فرض کنید تیم{TEX()} {t_i} {TEX} اولین تیمی (کوچک ترین {TEX()} {i} {TEX} ای) باشد که به{TEX()} {t_{n+1}} {TEX} باخته است. چنین تیمی وجود دارد زیرا تیم{TEX()} {t_{n+1}} {TEX} حداقل یک برد از تیم {TEX()} {t_n} {TEX} دارد. پس تیم{TEX()} {t_{i-1}} {TEX}،{TEX()} {t_{n+1}} {TEX} را برده و تیم{TEX()} {t_{n+1}} {TEX} هم{TEX()} {t_i} {TEX} را برده است. پس دنباله ی{TEX()} {t_1,t_2,\cdots ,t_{i-1} ,t_{n+1} ,t_i ,\cdots ,t_n} {TEX} جواب مساله است. | | اگر تیم{TEX()} {t_{n+1}} {TEX} به تیم{TEX()} {t_n} {TEX} باخته باشد، دنباله ی{TEX()} {t_1,t_2,\cdots ,t_n ,t_{n+1}} {TEX} جواب مساله است. همچنین اگر تیم{TEX()} {t_{n+1}} {TEX} تیم{TEX()} {t_1} {TEX} را برده باشد، دنباله ی{TEX()} {t_{n+1},t_1,t_2,\cdots ,t_n} {TEX} جواب مساله است. در غیر این حالات فرض کنید تیم{TEX()} {t_i} {TEX} اولین تیمی (کوچک ترین {TEX()} {i} {TEX} ای) باشد که به{TEX()} {t_{n+1}} {TEX} باخته است. چنین تیمی وجود دارد زیرا تیم{TEX()} {t_{n+1}} {TEX} حداقل یک برد از تیم {TEX()} {t_n} {TEX} دارد. پس تیم{TEX()} {t_{i-1}} {TEX}،{TEX()} {t_{n+1}} {TEX} را برده و تیم{TEX()} {t_{n+1}} {TEX} هم{TEX()} {t_i} {TEX} را برده است. پس دنباله ی{TEX()} {t_1,t_2,\cdots ,t_{i-1} ,t_{n+1} ,t_i ,\cdots ,t_n} {TEX} جواب مساله است. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال4 | | !!مثال4 |
| | {TEX()} {n} {TEX} عدد مثبت و متمایز{TEX()} {a_1,a_2,\cdots ,a_n} {TEX} مفروض اند. اگر{TEX()} {(i=1,2,\cdots ,n) e_i=0,1} {TEX} باشد. ثابت کنید از بین {TEX()} {2^n} {TEX} مقداری که{TEX()} {e_1a_1+e_2a_2+\cdots +e_na_n} {TEX}، می تواند بگیرد، حداقل{TEX()} {\frac{n(n+1)}{2}+1} {TEX} عدد متمایز پیدا می شود. | | {TEX()} {n} {TEX} عدد مثبت و متمایز{TEX()} {a_1,a_2,\cdots ,a_n} {TEX} مفروض اند. اگر{TEX()} {(i=1,2,\cdots ,n) e_i=0,1} {TEX} باشد. ثابت کنید از بین {TEX()} {2^n} {TEX} مقداری که{TEX()} {e_1a_1+e_2a_2+\cdots +e_na_n} {TEX}، می تواند بگیرد، حداقل{TEX()} {\frac{n(n+1)}{2}+1} {TEX} عدد متمایز پیدا می شود. |
| | __حل __ | | __حل __ |
| | بدون این که به کلیت مساله لطمه بخورد فرض کنید{TEX()} {0<a_1<a_2<\cdots <a_n} {TEX}. با استقرا روی {TEX()} {n} {TEX} ثابت می کنیم که لااقل{TEX()} {\frac{n(n+1)}{2}+1} {TEX} تعداد از جملات فوق متمایز هستند. | | بدون این که به کلیت مساله لطمه بخورد فرض کنید{TEX()} {0<a_1<a_2<\cdots <a_n} {TEX}. با استقرا روی {TEX()} {n} {TEX} ثابت می کنیم که لااقل{TEX()} {\frac{n(n+1)}{2}+1} {TEX} تعداد از جملات فوق متمایز هستند. |
| | برای پایه ی استقرا {TEX()} {(n=1)} {TEX} که حکم برقرار است. {TEX()} {0,a_1} {TEX} دو جمله ی مورد نظر است. | | برای پایه ی استقرا {TEX()} {(n=1)} {TEX} که حکم برقرار است. {TEX()} {0,a_1} {TEX} دو جمله ی مورد نظر است. |
| | حال حکم را به ازای {TEX()} {n=k} {TEX} درست فرض کنید؛ می خواهیم درستی آن را به ازای {TEX()} {n=k+1} {TEX} اثبات کنیم. با اعداد {TEX()} {0<a_1<a_2<\cdots <a_k} {TEX}، حداقل{TEX()} {\frac{k(k+1)}{2}+1} {TEX} جمله ی متمایز ساخته می شود. باید {TEX()} {\frac{(k+1)(k+2)}{2}+1-\left (\frac{k(k+1)}{2}+1 \right )=k+1} {TEX} جمله ی دیگر بسازیم. این {TEX()} {k+1} {TEX} جمله را به روش زیر می سازیم. | | حال حکم را به ازای {TEX()} {n=k} {TEX} درست فرض کنید؛ می خواهیم درستی آن را به ازای {TEX()} {n=k+1} {TEX} اثبات کنیم. با اعداد {TEX()} {0<a_1<a_2<\cdots <a_k} {TEX}، حداقل{TEX()} {\frac{k(k+1)}{2}+1} {TEX} جمله ی متمایز ساخته می شود. باید {TEX()} {\frac{(k+1)(k+2)}{2}+1-\left (\frac{k(k+1)}{2}+1 \right )=k+1} {TEX} جمله ی دیگر بسازیم. این {TEX()} {k+1} {TEX} جمله را به روش زیر می سازیم. |
| | فرض کنید{TEX()} {S=\sum_{i=1}^k a_i} {TEX}. (در نتیجه {TEX()} {S} {TEX} بزرگتر یا مساوی تمام جملات قبلی است.) حال ادعا می کنیم که | | فرض کنید{TEX()} {S=\sum_{i=1}^k a_i} {TEX}. (در نتیجه {TEX()} {S} {TEX} بزرگتر یا مساوی تمام جملات قبلی است.) حال ادعا می کنیم که |
| | @@{TEX()} {S+a_{k+1}>S+a_{k+1}-a_1>S+a_{k+1}-a_2>\cdots >S+a_{k+1}-a_k} {TEX}@@ | | @@{TEX()} {S+a_{k+1}>S+a_{k+1}-a_1>S+a_{k+1}-a_2>\cdots >S+a_{k+1}-a_k} {TEX}@@ |
| | {TEX()} {k+1} {TEX} جمله ی متمایز هستند و هر کدام از سایر جملات قبلی بزرگتر می باشد زیرا اگر {TEX()} {A} {TEX}یکی از {TEX()} {\frac{k(k+1)}{2}+1} {TEX} جمله ی ساخته شده ی قبلی باشد،{TEX()} {S\ge A} {TEX} ولی{TEX()} {S+a_{k+1}-a_k>S} {TEX} می باشد. پس حکم اثبات شد.#@ | | {TEX()} {k+1} {TEX} جمله ی متمایز هستند و هر کدام از سایر جملات قبلی بزرگتر می باشد زیرا اگر {TEX()} {A} {TEX}یکی از {TEX()} {\frac{k(k+1)}{2}+1} {TEX} جمله ی ساخته شده ی قبلی باشد،{TEX()} {S\ge A} {TEX} ولی{TEX()} {S+a_{k+1}-a_k>S} {TEX} می باشد. پس حکم اثبات شد.#@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال5 | | !!مثال5 |
| | در یک مدرسه {TEX()} {n} {TEX}دبیر تدریس می کنند. این دبیرها را با شماره های 1 تا {TEX()} {n} {TEX}شماره گذاری می کنیم. می دانیم که دبیر {TEX()} {i} {TEX} ام، {TEX()} {i+1} {TEX}نفر از دانش آموزان را می شناسد. هر دانش آموز می تواند توسط بیش از یک دبیر شناخته شود. هر یک از این دبیرها می خواهد یکی از دانش آموزانی را که می شناسد به عنوان نماینده ی خود برگزیند به شرط این که هیچ دانش آموزی به عنوان نماینده ی بیش از یک دبیر انتخاب نشود. ثابت کنید که انتخاب این نماینده ها حداقل به{TEX()} {2^n} {TEX} حالت مختلف امکان پذیر است. | | در یک مدرسه {TEX()} {n} {TEX}دبیر تدریس می کنند. این دبیرها را با شماره های 1 تا {TEX()} {n} {TEX}شماره گذاری می کنیم. می دانیم که دبیر {TEX()} {i} {TEX} ام، {TEX()} {i+1} {TEX}نفر از دانش آموزان را می شناسد. هر دانش آموز می تواند توسط بیش از یک دبیر شناخته شود. هر یک از این دبیرها می خواهد یکی از دانش آموزانی را که می شناسد به عنوان نماینده ی خود برگزیند به شرط این که هیچ دانش آموزی به عنوان نماینده ی بیش از یک دبیر انتخاب نشود. ثابت کنید که انتخاب این نماینده ها حداقل به{TEX()} {2^n} {TEX} حالت مختلف امکان پذیر است. |
| | __حل __ | | __حل __ |
| | باز مساله را با استقرا روی تعداد دبیرها حل می کنیم. برای {TEX()} {n=1} {TEX}، حکم بدیهی است. اگر برای {TEX()} {n} {TEX}دبیر، حداقل{TEX()} {2^n} {TEX} حالت وجود داشته باشد، می خواهیم ثابت کنیم برای {TEX()} {n+1} {TEX}دبیر هم، حداقل{TEX()} {2^{n+1}} {TEX} حالت وجود دارد. طبق فرض استقرا دبیرهای اول تا {TEX()} {n} {TEX} ام به{TEX()} {2^n} {TEX} طریق می توانند نماینده های خود را انتخاب کنند؛ و چون دبیر {TEX()} {n+1} {TEX}ام حداقل {TEX()} {n+2} {TEX} نفر را می شناسد که حداکثر {TEX()} {n} {TEX} نفر از آنها قبلاً به عنوان نماینده انتخاب شده اند، پس دبیر {TEX()} {n+1} {TEX} ام - در هر کدام از{TEX()} {2^n} {TEX} حالت- حداقل به 2 طریق می تواند نماینده ی خود را انتخاب کند. بنابراین {TEX()} {n+1} {TEX} دبیر حداقل به{TEX()} {2\times 2^n=2^{n+1}} {TEX} طریق می توانند نماینده های خود را انتخاب کنند. | | باز مساله را با استقرا روی تعداد دبیرها حل می کنیم. برای {TEX()} {n=1} {TEX}، حکم بدیهی است. اگر برای {TEX()} {n} {TEX}دبیر، حداقل{TEX()} {2^n} {TEX} حالت وجود داشته باشد، می خواهیم ثابت کنیم برای {TEX()} {n+1} {TEX}دبیر هم، حداقل{TEX()} {2^{n+1}} {TEX} حالت وجود دارد. طبق فرض استقرا دبیرهای اول تا {TEX()} {n} {TEX} ام به{TEX()} {2^n} {TEX} طریق می توانند نماینده های خود را انتخاب کنند؛ و چون دبیر {TEX()} {n+1} {TEX}ام حداقل {TEX()} {n+2} {TEX} نفر را می شناسد که حداکثر {TEX()} {n} {TEX} نفر از آنها قبلاً به عنوان نماینده انتخاب شده اند، پس دبیر {TEX()} {n+1} {TEX} ام - در هر کدام از{TEX()} {2^n} {TEX} حالت- حداقل به 2 طریق می تواند نماینده ی خود را انتخاب کند. بنابراین {TEX()} {n+1} {TEX} دبیر حداقل به{TEX()} {2\times 2^n=2^{n+1}} {TEX} طریق می توانند نماینده های خود را انتخاب کنند. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال6 | | !!مثال6 |
| | ثابت کنید برای هر عدد طبیعی {TEX()} {n} {TEX} می توان{TEX()} {7^n} {TEX} دایره به شعاع واحد را درون یک دایره به شعاع{TEX()} {3^n} {TEX} جا داد به طوری که هیچ دو دایره ای متقاطع نباشند (هر دو دایره حداکثر در یک نقطه می توانند با هم اشتراک داشته باشند). | | ثابت کنید برای هر عدد طبیعی {TEX()} {n} {TEX} می توان{TEX()} {7^n} {TEX} دایره به شعاع واحد را درون یک دایره به شعاع{TEX()} {3^n} {TEX} جا داد به طوری که هیچ دو دایره ای متقاطع نباشند (هر دو دایره حداکثر در یک نقطه می توانند با هم اشتراک داشته باشند). |
| | __حل __ | | __حل __ |
| | با استقرا روی {TEX()} {n} {TEX} ثابت می کنیم که{TEX()} {7^n} {TEX} دایره به شعاع واحد را می توان درون یک دایره به شعاع{TEX()} {3^n} {TEX} جا داد. برای {TEX()} {n=1} {TEX}، دایره ها را به صورتی که در شکل نشان داده شده است قرار می دهیم. | | با استقرا روی {TEX()} {n} {TEX} ثابت می کنیم که{TEX()} {7^n} {TEX} دایره به شعاع واحد را می توان درون یک دایره به شعاع{TEX()} {3^n} {TEX} جا داد. برای {TEX()} {n=1} {TEX}، دایره ها را به صورتی که در شکل نشان داده شده است قرار می دهیم. |
| | ::{picture=img/daneshnameh_up/3/34/comm0003d.JPG} :: | | ::{picture=img/daneshnameh_up/3/34/comm0003d.JPG} :: |
| - | حال فرض کنید که حکم برای {TEX()} {n=m} {TEX}درست باشد، می خواهیم حکم را برای {TEX()} {n=m+1} {TEX} ثابت کنیم. ابتدا درون دایره ای به شعاع{TEX()} {3^{m+1}} {TEX}، مانند حالت {TEX()} {n=1} {TEX}، 7 دایره به شعاع{TEX()} {3^m} {TEX} رسم می کنیم. حال طبق فرض استقرا می توان دورن هر یک از این 7 دایره،{TEX()} {7^m} {TEX} دایره به شعاع واحد رسم کرد. چون هیچ کدام از 7 دایره ی به شعاع{TEX()} {3^m} {TEX}، بیش از یک نقطه ی تلاقی ندارند، بنابراین توانستیم درون یک دایره به شعاع{TEX()} {3^{m+1}} {TEX} ، {TEX()} {7\times 7^m=7^{m+1}} {TEX} دایره به شعاع واحد رسم کنیم که هیچ دو دایره ای در بیش از یک نقطه با یکدیگر تقاطع نداشته باشند. پس حکم ثابت شد. |
+ | حال فرض کنید که حکم برای {TEX()} {n=m} {TEX}درست باشد، می خواهیم حکم را برای {TEX()} {n=m+1} {TEX} ثابت کنیم. ابتدا درون دایره ای به شعاع{TEX()} {3^{m+1}} {TEX}، مانند حالت {TEX()} {n=1} {TEX}، 7 دایره به شعاع{TEX()} {3^m} {TEX} رسم می کنیم. حال طبق فرض استقرا می توان دورن هر یک از این 7 دایره،{TEX()} {7^m} {TEX} دایره به شعاع واحد رسم کرد. چون هیچ کدام از 7 دایره ی به شعاع{TEX()} {3^m} {TEX}، بیش از یک نقطه ی تلاقی ندارند، بنابراین توانستیم درون یک دایره به شعاع{TEX()} {3^{m+1}} {TEX} ، {TEX()} {7\times 7^m=7^{m+1}} {TEX} دایره به شعاع واحد رسم کنیم که هیچ دو ((دایره)) ای در بیش از یک ((نقطه)) با یکدیگر تقاطع نداشته باشند. پس حکم ثابت شد. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال7 | | !!مثال7 |
| | {TEX()} {A} {TEX} و {TEX()} {B} {TEX}دو مجموعه ی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر{TEX()} {x\in A\cup B} {TEX}، {TEX()} {x+1 \in A} {TEX} یا{TEX()} {x-2\in B} {TEX} است. ثابت کنید که تعداد عناصر مجموعه ی {TEX()} {A} {TEX} دو برابر تعداد عناصر مجموعه ی {TEX()} {B} {TEX} است. | | {TEX()} {A} {TEX} و {TEX()} {B} {TEX}دو مجموعه ی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر{TEX()} {x\in A\cup B} {TEX}، {TEX()} {x+1 \in A} {TEX} یا{TEX()} {x-2\in B} {TEX} است. ثابت کنید که تعداد عناصر مجموعه ی {TEX()} {A} {TEX} دو برابر تعداد عناصر مجموعه ی {TEX()} {B} {TEX} است. |
| | __حل__ | | __حل__ |
| | از استقرا روی تعداد عناصر {TEX()} {B} {TEX}استفاده می کنیم. اگر تعداد عناصر {TEX()} {B} {TEX}صفر باشد، یعنی {TEX()} {B} {TEX}تهی باشد، نشان می دهیم که {TEX()} {A} {TEX}نیز تهی است. چون برای هر عنصر{TEX()} {x\in A} {TEX}،{TEX()} {x\in A\cup B} {TEX} نیز می باشد، در نتیجه طبق فرض مسئله باید{TEX()} {x+1\in A} {TEX} باشد. بنابراین اگر {TEX()} {A} {TEX} تهی نباشد، باید نامتناهی باشد و این برخلاف فرض مساله است. | | از استقرا روی تعداد عناصر {TEX()} {B} {TEX}استفاده می کنیم. اگر تعداد عناصر {TEX()} {B} {TEX}صفر باشد، یعنی {TEX()} {B} {TEX}تهی باشد، نشان می دهیم که {TEX()} {A} {TEX}نیز تهی است. چون برای هر عنصر{TEX()} {x\in A} {TEX}،{TEX()} {x\in A\cup B} {TEX} نیز می باشد، در نتیجه طبق فرض مسئله باید{TEX()} {x+1\in A} {TEX} باشد. بنابراین اگر {TEX()} {A} {TEX} تهی نباشد، باید نامتناهی باشد و این برخلاف فرض مساله است. |
| | حالا فرض کنید که مسئله برای{TEX()} {|B|=n-1} {TEX} ثابت شده باشد، حال آن را برای{TEX()} {|B|=n} {TEX} ثابت می کنیم. برای این منظور کوچک ترین عضو {TEX()} {B} {TEX} را در نظر گرفته و آن را {TEX()} {y} {TEX}می نامیم. چون {TEX()} {y} {TEX}کوچک ترین عضو {TEX()} {B} {TEX}است، پس {TEX()} {y-2\notin B} {TEX}؛ در نتیجه{TEX()} {y+1\in A} {TEX} است. در نتیجه چون{TEX()} {y+1\in A} {TEX} و{TEX()} {y-1 \notin B} {TEX} (زیرا {TEX()} {y} {TEX}کوچک ترین عصو {TEX()} {B} {TEX}است). بنابراین{TEX()} {y+2\in A} {TEX}. چون مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}جدا از هم می باشند، بنابراین{TEX()} {y \notin A} {TEX} و{TEX()} {y+1 ,y+2 \notin B} {TEX} . | | حالا فرض کنید که مسئله برای{TEX()} {|B|=n-1} {TEX} ثابت شده باشد، حال آن را برای{TEX()} {|B|=n} {TEX} ثابت می کنیم. برای این منظور کوچک ترین عضو {TEX()} {B} {TEX} را در نظر گرفته و آن را {TEX()} {y} {TEX}می نامیم. چون {TEX()} {y} {TEX}کوچک ترین عضو {TEX()} {B} {TEX}است، پس {TEX()} {y-2\notin B} {TEX}؛ در نتیجه{TEX()} {y+1\in A} {TEX} است. در نتیجه چون{TEX()} {y+1\in A} {TEX} و{TEX()} {y-1 \notin B} {TEX} (زیرا {TEX()} {y} {TEX}کوچک ترین عصو {TEX()} {B} {TEX}است). بنابراین{TEX()} {y+2\in A} {TEX}. چون مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}جدا از هم می باشند، بنابراین{TEX()} {y \notin A} {TEX} و{TEX()} {y+1 ,y+2 \notin B} {TEX} . |
| | حال مجموعه های {TEX()} {A^\prime =A-\{y+1,y+2 \}} {TEX} و {TEX()} {B^\prime=B-\{y\}} {TEX} را در نظر بگیرید. به ازای هر{TEX()} {x \in A^\prime \cup B^\prime} {TEX}، داریم{TEX()} {x+1 \in A^\prime} {TEX} یا{TEX()} {x-2 \in B^\prime} {TEX}. زیرا اگر{TEX()} {x \in A^\prime \cup B^\prime} {TEX} باشد، آن گاه{TEX()} {x \in A\cup B} {TEX} است و طبق فرض مساله {TEX()} {x+1 \in A} {TEX} یا{TEX()} {x-2 \in B} {TEX} می باشد. اگر مثلاً{TEX()} {x+1 \in A} {TEX} باشد، با توجه به این که{TEX()} {x \neq y \ , \ y+1 \ , \ y+2} {TEX} (چرا؟)، پس{TEX()} {x+1 \in A^\prime} {TEX}. به طریق مشابه اگر{TEX()} {x-2 \in B} {TEX} باشد، با توجه به این که{TEX()} {x \neq y \ , \ y+1 \ , \ y+2} {TEX}، پس باید {TEX()} {x-2 \in B^\prime} {TEX} باشد. از طرف دیگر واضح است که چون مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}جدا از هم می باشند، پس مجموعه های {TEX()} {A^\prime} {TEX} و{TEX()} {B^\prime} {TEX} هم جدا از هم می باشند. پس مجموعه های{TEX()} {A^\prime} {TEX} و{TEX()} {B^\prime} {TEX} دارای شرایط مساله هستند و{TEX()} {|B^\prime |=n-1} {TEX}، پس طبق فرض استقرا{TEX()} {|A^\prime |= 2| B^\prime |} {TEX}. ولی{TEX()} {|A|=|A^\prime |+2} {TEX} و{TEX()} {|B|+ | B^\prime |+1} {TEX} پس{TEX()} {|A|= 2|B|} {TEX}. | | حال مجموعه های {TEX()} {A^\prime =A-\{y+1,y+2 \}} {TEX} و {TEX()} {B^\prime=B-\{y\}} {TEX} را در نظر بگیرید. به ازای هر{TEX()} {x \in A^\prime \cup B^\prime} {TEX}، داریم{TEX()} {x+1 \in A^\prime} {TEX} یا{TEX()} {x-2 \in B^\prime} {TEX}. زیرا اگر{TEX()} {x \in A^\prime \cup B^\prime} {TEX} باشد، آن گاه{TEX()} {x \in A\cup B} {TEX} است و طبق فرض مساله {TEX()} {x+1 \in A} {TEX} یا{TEX()} {x-2 \in B} {TEX} می باشد. اگر مثلاً{TEX()} {x+1 \in A} {TEX} باشد، با توجه به این که{TEX()} {x \neq y \ , \ y+1 \ , \ y+2} {TEX} (چرا؟)، پس{TEX()} {x+1 \in A^\prime} {TEX}. به طریق مشابه اگر{TEX()} {x-2 \in B} {TEX} باشد، با توجه به این که{TEX()} {x \neq y \ , \ y+1 \ , \ y+2} {TEX}، پس باید {TEX()} {x-2 \in B^\prime} {TEX} باشد. از طرف دیگر واضح است که چون مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}جدا از هم می باشند، پس مجموعه های {TEX()} {A^\prime} {TEX} و{TEX()} {B^\prime} {TEX} هم جدا از هم می باشند. پس مجموعه های{TEX()} {A^\prime} {TEX} و{TEX()} {B^\prime} {TEX} دارای شرایط مساله هستند و{TEX()} {|B^\prime |=n-1} {TEX}، پس طبق فرض استقرا{TEX()} {|A^\prime |= 2| B^\prime |} {TEX}. ولی{TEX()} {|A|=|A^\prime |+2} {TEX} و{TEX()} {|B|+ | B^\prime |+1} {TEX} پس{TEX()} {|A|= 2|B|} {TEX}. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | --- | | --- |
| | !!مثال8 | | !!مثال8 |
| | تعداد{TEX()} {2^k} {TEX} دیسک داریم که روی هر کدام، یکی از عددهای 1 تا{TEX()} {2^k} {TEX} نوشته شده است. {TEX()} {k+ 2} {TEX} میله با شماره های صفر تا {TEX()} { k+ 1 } {TEX} در یک ردیف پشت سر هم قرار گرفته اند. در ابتدا، دیسک ها با یک ترتیب داده شده در میله ی صفر روی هم قرار دارند. در هر حرکت می توان بالاترین دیسک موجود روی میله ی{TEX()} { i } {TEX} را برداشته و روی میله ی {TEX()} { i + 1 } {TEX} ام قرار داد{TEX()} {0 \le i \le k} {TEX}. این حرکت را با{TEX()} {T_i } {TEX} نمایش می دهیم. حالت نهایی مرتب، حالتی است که در آن تمام دیسک ها به ترتیب از شماره ی 1 تا{TEX()} {2^k} {TEX} (پایین به بالا) روی میله ی شماره ی{TEX()} { k + 1} {TEX} ام قرار گرفته باشند. برای مثال، به ازای{TEX()} { k = 1} {TEX} ، حرکت های لازم برای رسیدن به حالت نهایی مرتب از حالت اولیه ای به شکل زیر می تواند به صورت{TEX()} {(T_0 , T_0 , T_1 , T_1)} {TEX} باشد. | | تعداد{TEX()} {2^k} {TEX} دیسک داریم که روی هر کدام، یکی از عددهای 1 تا{TEX()} {2^k} {TEX} نوشته شده است. {TEX()} {k+ 2} {TEX} میله با شماره های صفر تا {TEX()} { k+ 1 } {TEX} در یک ردیف پشت سر هم قرار گرفته اند. در ابتدا، دیسک ها با یک ترتیب داده شده در میله ی صفر روی هم قرار دارند. در هر حرکت می توان بالاترین دیسک موجود روی میله ی{TEX()} { i } {TEX} را برداشته و روی میله ی {TEX()} { i + 1 } {TEX} ام قرار داد{TEX()} {0 \le i \le k} {TEX}. این حرکت را با{TEX()} {T_i } {TEX} نمایش می دهیم. حالت نهایی مرتب، حالتی است که در آن تمام دیسک ها به ترتیب از شماره ی 1 تا{TEX()} {2^k} {TEX} (پایین به بالا) روی میله ی شماره ی{TEX()} { k + 1} {TEX} ام قرار گرفته باشند. برای مثال، به ازای{TEX()} { k = 1} {TEX} ، حرکت های لازم برای رسیدن به حالت نهایی مرتب از حالت اولیه ای به شکل زیر می تواند به صورت{TEX()} {(T_0 , T_0 , T_1 , T_1)} {TEX} باشد. |
| | ثابت کنید به ازای هر{TEX()} { k } {TEX} می توان از هر ترتیب اولیه ی دیسک ها روی میله ی شماره ی صفر به یک حالت نهایی مرتب رسید. | | ثابت کنید به ازای هر{TEX()} { k } {TEX} می توان از هر ترتیب اولیه ی دیسک ها روی میله ی شماره ی صفر به یک حالت نهایی مرتب رسید. |
| | __حل __ | | __حل __ |
| - | اگر{TEX()} {k=0 } {TEX} باشد که حکم بدیهی است. حال فرض کنید مسئله برای{TEX()} {k=m} {TEX} حل شده باشد؛ درستی آن را برای{TEX()} { k = m + 1 } {TEX} ثابت می کنیم. حال{TEX()} { m + 3 } {TEX}میله و{TEX()} {2^{m+1}} {TEX} مهره داریم. اگر مهره های شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} وجود نداشتند، می توانستیم مهره های شماره ی 1 تا{TEX()} {2^m} {TEX} را بدون استفاده از میله ی شماره ی 1 به میله ی شماره{TEX()} { m + 2 } {TEX} منتقل کنیم. ولی این مشکل را می توان به این صورت حل کرد که هر گاه نوبت حرکت یک مهره با شماره ی 1 تا {TEX()} {2^m} {TEX} شد و مهره یا مهره هایی با شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} بالاتر از آن روی میله ی شماره ی صفر قرار داشت، آن مهره ها را به میله ی شماره ی یک منتقل می کنیم و بعد حرکت مورد نظر را انجام می دهیم. توجه کنید که در حرکات مورد نظر، حرکت{TEX()} {T_i } {TEX} به حرکت{TEX()} {T_{i+1}} {TEX}{TEX()} {I \ge 1} {TEX} و حرکت{TEX()} {T_0} {TEX} به حرکت های لازم{TEX()} {T_0} {TEX} برای انتقال مهره های با شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} و سپس حرکت{TEX()} {T_0} {TEX} به{TEX()} {T_1} {TEX} تبدیل شده است. |
+ | اگر{TEX()} {k=0 } {TEX} باشد که حکم بدیهی است. حال فرض کنید مسئله برای{TEX()} {k=m} {TEX} حل شده باشد؛ درستی آن را برای{TEX()} { k = m + 1 } {TEX} ثابت می کنیم. حال{TEX()} { m + 3 } {TEX}میله و{TEX()} {2^{m+1}} {TEX} مهره داریم. اگر مهره های شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} وجود نداشتند، می توانستیم مهره های شماره ی 1 تا{TEX()} {2^m} {TEX} را بدون استفاده از میله ی شماره ی 1 به میله ی شماره{TEX()} { m + 2 } {TEX} منتقل کنیم. ولی این مشکل را می توان به این صورت حل کرد که هر گاه نوبت حرکت یک مهره با شماره ی 1 تا {TEX()} {2^m} {TEX} شد و مهره یا مهره هایی با شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} بالاتر از آن روی میله ی شماره ی صفر قرار داشت، آن مهره ها را به میله ی شماره ی یک منتقل می کنیم و بعد حرکت مورد نظر را انجام می دهیم. توجه کنید که در حرکات مورد نظر، حرکت{TEX()} {T_i } {TEX} به حرکت{TEX()} {T_{i+1}} {TEX}{TEX()} {I \ge 1} {TEX} و حرکت{TEX()} {T_0} {TEX} به حرکت های لازم{TEX()} {T_0} {TEX} برای ((انتقال)) مهره های با شماره ی{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} و سپس حرکت{TEX()} {T_0} {TEX} به{TEX()} {T_1} {TEX} تبدیل شده است. |
| | #@ | | #@ |
| | @#16: | | @#16: |
| | حال مهره های با شماره ی 1 تا{TEX()} {2^m} {TEX} با ترتیب پایین به بالا روی میله ی شماره ی {TEX()} { m + 2} {TEX} قرار گرفته اند. حال{TEX()} {2^m} {TEX} دیسک با شماره های{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} راکه روی میله ی شماره ی یک قرار گرفته اند، طبق فرض استقرا به میله ی شماره ی {TEX()} { m + 2} {TEX} منتقل می کنیم. بنابراین دیسک ها از شماره ی 1 تا{TEX()} {2^{m+1}} {TEX} به ترتیب ( از پایین به بالا) روی میله ی شماره ی {TEX()} { m + 2} {TEX} قرار گرفته اند و حکم ثابت شد. | | حال مهره های با شماره ی 1 تا{TEX()} {2^m} {TEX} با ترتیب پایین به بالا روی میله ی شماره ی {TEX()} { m + 2} {TEX} قرار گرفته اند. حال{TEX()} {2^m} {TEX} دیسک با شماره های{TEX()} {2^m+1} {TEX} تا{TEX()} {2^{m+1}} {TEX} راکه روی میله ی شماره ی یک قرار گرفته اند، طبق فرض استقرا به میله ی شماره ی {TEX()} { m + 2} {TEX} منتقل می کنیم. بنابراین دیسک ها از شماره ی 1 تا{TEX()} {2^{m+1}} {TEX} به ترتیب ( از پایین به بالا) روی میله ی شماره ی {TEX()} { m + 2} {TEX} قرار گرفته اند و حکم ثابت شد. |
| | + | --- |
| | + | !پیوندهای خارجی |
| | + | [http://olympiad.roshd.ir/computer/content/pdf/0006.pdf] |
| | + | --- |
| | + | !همچنین ببینید |
| | + | *((تعمیم اولیه اصل استقرا II )) |
| | + | *((استقرای قوی و چندگانه)) |
| | + | *((استقرای قوی)) |
| | #@^ | | #@^ |
