منو
 کاربر Online
777 کاربر online
تاریخچه ی: تکنیک هایی از استقرا II

||V{maketoc}||
^@#16:
---
!تغییر مساله و تعمیم
در بسیاری از مسایل هنگام اثبات یک مساله، ما نیاز به اثبات یک مساله دیگر داریم. مثلا وقتی می گوییم «کافی است نشان دهیم که ...» یا «می توانیم فرض کنیم که ...» یا «بدون کاسته شدن از کلیت مساله ...» یا ...، در حقیقت مساله اصلی (مثلا{TEX()} { A } {TEX}) را به یک مساله دیگر (مثلا{TEX()} { B } {TEX}) تبدیل کرده ایم که اثبات مساله{TEX()} { B } {TEX} منجر به اثبات مساله{TEX()} { A } {TEX} می شود ولی لزوما اثبات درستی مساله{TEX()} { A } {TEX} منجر به اثبات درستی مساله{TEX()} { B } {TEX} نخواهد شد.
بعضی اوقات در حل یک مساله اگر صورت تعمیم یافته آن را مدنظر قرار دهیم خیلی ساده تر به راه حل اصلی آن دسترسی پیدا می کنیم. در به کارگیری استقرا نیز چنین است: چون ممکن است مثلا عبارت های {TEX()} {P(1),P(2),P(3),\cdots} {TEX} اطلاعات کافی به همراه نداشته باشند تا نتیجه گیری استقرایی را امکان پذیر سازند، در چنین مواردی باید حکم موردنظر را به صورت تعمیم یافته ای، مثلا {TEX()} {Q(n)} {TEX} (به طوری که {TEX()} {Q(n)} {TEX}، {TEX()} {P(n)} {TEX} را نتیجه دهد)، بیان کنیم و آنگاه با توجه به {TEX()} {Q(1),Q(2),Q(3),\cdots} {TEX} روش استقرایی را اعمال کنیم.
قدرت تغییر مساله، به قدری است که گاهی می توان مساله ای را که در حالت عادی به سختی حل می شود به راحتی حل کرد. نمونه ای از مسایلی که با تغییر مساله حل می شوند مساله هشتم مرحله دوم دهمین المپیاد کامپیوتر ایران است که تعداد معدودی از شرکت کنندگان توانستند بیش از نصف نمره مساله را بگیرند. حال بهتر است به بررسی چند مثال از این گونه بپردازیم.
---
!مثال
انتخاب دلخواهی از عددهای1 و -1 به طول{TEX()} {2^k} {TEX} را، در نظر می گیریم. از این گروه از عددها، گروه تازه ای با قاعده ی زیر می سازیم: هر عدد را در عدد بعدی خود و آخرین عدد (یعنی عدد{TEX()} {2^k} {TEX} ام)را در عدد اول ضرب می کنیم. از این گروه جدید (طبق همان قاعده)، گروه سوم را به دست می آوریم و ... . ثابت کنید، دست آخر به گروهی از عددها می رسیم که تنها شامل واحدها هستند.
__اثبات.__
این دفعه از چه راهی به مساله هجوم ببریم؟ چگونه از پس این مساله بربیاییم؟ بیایید اول صورت مساله را بهتر درک کنیم. پس مساله را در حالت خاص{TEX()} { k = 1, 2} {TEX} در نظر می گیریم.
فرض کنید دنباله ی{TEX()} {x_1,x_2} {TEX} دنباله ی مفروض باشد. داریم:
@@{TEX()} {0: \ x_1 \qquad x_2} {TEX}@@
@@{TEX()} {1:x_1x_2 \quad x_2x_1} {TEX}@@
@@{TEX()} {2: \ 1 \qquad 1} {TEX}@@
فرض کنید دنباله ی{TEX()} {x_1,x_2,x_3,x_4} {TEX} دنباله ی مفروض باشد. با چند بار تکرار این عمل و با توجه به این که{TEX()} {x_i^2=1} {TEX} داریم:
#@
@#16:
::{picture=img/daneshnameh_up/1/11/comm0009f.JPG}::
از مثال های فوق چه چیزی درمی یابید؟ در حرکت{TEX()} {2^k} {TEX} ام، تمام عناصر دنباله تبدیل به یک می شوند. چه شباهتی بین دو مثال بالا می یابید؟ اگر در مثال {TEX()} { k = 2} {TEX} فقط عناصر{TEX()} {x_1,x_3} {TEX} را نگاه کنیم و سطرهای فرد را کنار بگذاریم به ساختاری شبیه به مثال{TEX()} { k = 1} {TEX} می رسیم. این همان کلید حل مساله است. پس بیایید مساله را در حالت کلی حل کنیم.
حال به جای اثبات حکم مساله حکم قوی تر زیر را اثبات می کنیم: هر دنباله ای از 1 و 1- ها به طول{TEX()} {2^k} {TEX}، بعد از {TEX()} {2^k} {TEX} بار انجام عمل فوق به دنباله ای به طول{TEX()} {2^k} {TEX} تبدیل می شود که تمام عناصر آن یک هستند.
پایه ی استقرا را در بالا بررسی کردیم. تنها بررسی درستی حکم استقرا می ماند. فرض کنید حکم برای هر دنباله ی به طول{TEX()} {2^k} {TEX} درست باشد؛ می خواهیم حکم را برای دنباله ی{TEX()} {x_1,x_3,x_5,\cdots ,x_{2^{k+1}-1}} {TEX} و عددهای ردیف زوج دنباله ی {TEX()} {x_2,x_4,x_6,\cdots ,x_{2^{k+1}}} {TEX} به طول{TEX()} {2^{k+1}} {TEX} ثابت کنیم. پس از چند بار تکرار این عمل داریم:
::{picture=img/daneshnameh_up/d/d8/comm0009g.JPG}::
عددهای ردیف فرد دنباله ی{TEX()} {x_1,x_3,x_5,\cdots,x_{2^{k+1}-1}} {TEX} و عددهای ردیف زوج دنباله ی{TEX()} {x_2,x_4,x_6,\cdots ,x_{2^{k+1}}} {TEX} را به وجود می آورند که هر کدام طولی برابر{TEX()} {2^k} {TEX} دارند. همان طور هم که در جدول بالا می بینیم اگر تنها ردیف عمل های زوج را در نظر بگیریم، دو دنباله به طول{TEX()} {2^k} {TEX} داریم که هر کدام پس از{TEX()} {2^k} {TEX} عمل تبدیل به دنباله ای از یک ها می شوند. بنابراین دنباله ی اصلی پس از{TEX()} {2\times 2^k=2^{k+1}} {TEX} عمل فوق به دنباله ای از 1 ها تبدیل می شود و اثبات تمام شد. با {TEX()} {2^{k+1}} {TEX} عمل به دنباله ای شامل 1 ها می رسیم.
در مثال فوق با اضافه کردن فرض تعداد حرکاتی که منجر به جواب می شود، به مساله ی اصلی، آن را حل کردیم. در برخی از مسایلی که با استقرا حل می شوند، اضافه کردن چنین فرض هایی به مساله می تواند در اثبات حکم استقرا از روی فرض استقرا، کمک زیادی به ما بکند.در زیر یک نمونه دیگر از این مسایل را می بینیم.
#@
@#16:
---
!!مثال
به ازای هر{TEX()} {n\in N} {TEX} ثابت کنید:
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}<1} {TEX}@@
__حل .__
راه حل اول (استفاده از تغییر مساله): به جای این که این مساله را ثابت کنیم، ثابت می کنیم که تساوی زیر برقرار است و در نتیجه حکم مساله ی اصلی از آن نتیجه می شود.
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}=1-\frac{1}{2^n}} {TEX}@@
حکم به ازای{TEX()} { n = 1 } {TEX}که برقرار است. حال فرض کنید
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{2^n}=1-\frac{1}{2^n}} {TEX}@@
با اضافه کردن{TEX()} {\frac{1}{2^{n+1}}} {TEX} به طرفین تساوی حکم استقرا ثابت می شود.
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^{n+1}}=1-\frac{1}{2^n}+\frac{1}{2^{n+1}}=1-\frac{1}{2^{n+1}}} {TEX}@@
راه حل دوم (استفاده از استقرای ساده): حکم به ازای{TEX()} { n = 1 } {TEX}برقرار است{TEX()} {(\frac{1}{2}<1)} {TEX}.
طبق فرض استقرا داریم:
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}<1} {TEX}@@
با ضرب طرفین در{TEX()} {\frac{1}{2}} {TEX} داریم:
@@{TEX()} {\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\cdots +\frac{1}{2^{n+!}}<\frac{1}{2}} {TEX}@@
با جمع کردن طرفین با{TEX()} {\frac{1}{2}} {TEX} حکم استقرا ثابت می شود :
@@{TEX()} {\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\cdots +\frac{1}{2^{n+1}}<\frac{1}{2}+\frac{1}{2}=1} {TEX}@@
این مثال نشان می دهد که یک مساله ممکن است بیش از یک راه حل داشته باشد و هر کدام از راه حل ها هم درست می باشند.
#@
@#16:
---
!!مثال
ثابت کنید مجموع زوایای داخلی یک{TEX()} { n } {TEX} ضلعی منتظم برابر با{TEX()} {(n-2)180^{\circ}} {TEX} است.
اثبات. به جای اثبات این مساله، ثابت می کنیم که مجموع زوایای داخلی هر n ضلعی محدب برابر با{TEX()} { 180(n – 2) } {TEX} درجه است.
به ازای{TEX()} { n = 3،} {TEX} می دانیم مجموع زوایای داخلی هر مثلث برابر{TEX()} {180^{\circ}} {TEX} است. پس پایه ی استقرا درست است.
می خواهیم مجموع زوایای داخلی یک{TEX()} { n + 1 } {TEX}ضلعی محدب را پیدا می کنیم. ما می توانیم مجموع زوایای داخلی هر{TEX()} { n } {TEX} ضلعی محدبی را پیدا کنیم، پس باید سعی کنیم که این{TEX()} { n + 1 } {TEX}ضلعی محدب را به یک n ضلعی محدب تبدیل کنیم. چکار کنیم؟
::{picture=img/daneshnameh_up/6/6a/comm0009h.JPG}::
اگر{TEX()} {v_1v_2\cdots v_nv_{n+1}} {TEX} ،{TEX()} { n + 1 } {TEX} ضلعی محدب ما باشد. با رسم قطر{TEX()} {v_1v_n} {TEX} این{TEX()} { n + 1 } {TEX}ضلعی محدب تبدیل به مثلث {TEX()} {v_1v_nv_{n+1}} {TEX} و{TEX()} { n } {TEX} ضلعی محدب{TEX()} {v_1v_2\cdots v_n} {TEX} می شود ( مطابق شکل ) . حال مجموع زوایای داخلی {TEX()} { n + 1} {TEX} ضلعی محدب برابر است با مجموع زوایای داخلی{TEX()} { n } {TEX} ضلعی محدب{TEX()} {v_1v_2\cdots v_n} {TEX} به علاوه ی مجموع زوایای داخلی مثلث{TEX()} {v_1v_nv_{n+1}} {TEX}. طبق فرض استقرا، مجموع زوایای داخلی این{TEX()} { n } {TEX} ضلعی محدب برابر{TEX()} {180^{\circ}(n-2)} {TEX} است و همچنین می دانیم که مجموع زوایای داخلی هر مثلث برابر{TEX()} {180^{\circ}} {TEX} است. پس مجموع زوایای داخلی این {TEX()} { n + 1} {TEX} ضلعی محدب برابر {TEX()} {180^{\circ}+180^{\circ}(n-2)=180^{\circ}(n-1)} {TEX} است. پس حکم ثابت شد.
دقت کنید که به کمک استقرای قوی می می توان ثابت کرد مجموع زوایای داخلی هر{TEX()} { n } {TEX} ضلعی محدب برابر با{TEX()} { 180(n – 2) } {TEX} درجه است. سعی کنید بعد از این که مبحث مربوط به استقرای قوی را خواندید، این حکم را با کمک استقرای قوی نیز حل کنید.
اگر می خواستیم این مساله را مستقیماً با استقرا حل کنیم، نمی توانستیم این کار را بکنیم زیرا وقتی با رسم یک قطر{TEX()} {v_1v_nv_{n+1}} {TEX}،{TEX()} { n + 1} {TEX} ضلعی منتظم را به یک مثلث و یک{TEX()} { n } {TEX} ضلعی تقسیم می کنیم،{TEX()} { n } {TEX} ضلعی حاصل، منتظم نیست و نمی توانیم از فرض استقرا استفاده کنیم. پس می بینید تغییر مساله چقدر به ما کمک می کند.
#@
@#16:
---
!!مثال
عددهای صحیح و مثبت{TEX()} {a_n,a_{n-1},\cdots ,a_1,a_0} {TEX} مفروضند. اگر{TEX()} {a_1\ge 2a_0} {TEX} و به ازای هر{TEX()} {2\le k\le n} {TEX}، داشته باشیم: {TEX()} {a_k=3a_{k-1}-2a_{k-2}} {TEX}، ثابت کنید: {TEX()} {a_n\ge 2^n} {TEX}.
__اثبات.__
به جای این که مساله ی فوق را ثابت کنیم، ثابت می کنیم که به ازای هر{TEX()} {k\ge 1} {TEX} داریم: {TEX()} {a_k\ge 2_{k-1}} {TEX}. اگر بتوانیم این مساله را ثابت کنیم با توجه به اینکه{TEX()} {a_0\ge 1} {TEX} است می توان با کمک استقرا نتیجه گرفت{TEX()} {a_k\ge 2^k} {TEX}. بنابراین حکم ثابت می شود.
به ازای{TEX()} { k = 1} {TEX}، طبق فرض مساله{TEX()} {a_1\ge 2a_k} {TEX}. حال فرض کنید{TEX()} {a_k\ge 2a_{k-1}} {TEX}؛ می خواهیم ثابت کنیم{TEX()} {a_{k+1}\ge 2a_k} {TEX}.
طبق فرض مساله داریم: {TEX()} {a_{k+1}=3a_k-2a_{k-1}} {TEX}. با توجه به فرض استقرا{TEX()} {a_k\ge 2a_{k-1}} {TEX}، در نتیجه: {TEX()} {a_{k+1}\ge 2a_k} {TEX}، پس حکم ثابت شد.
---
!!مثال
یک جدول{TEX()} { n \times n } {TEX} ، شامل اعداد طبیعی و یک ماشین مقایسه گر در اختیار داریم. می دانیم در این جدول، اعداد در هر سطر و در هر ستون به صورت اکیداً صعودی مرتب شده اند. می خواهیم عدد{TEX()} { k } {TEX} را در جدول جستجو کنیم. برای این کار در هر مرحله، می توانیم یک کارت شامل دو عدد{TEX()} { i } {TEX} و{TEX()} { j } {TEX} به ماشین بدهیم و ماشین با گرفتن این کارت به ما پاسخ می دهد که عددی که در خانه ی سطر{TEX()} { i } {TEX} و ستون{TEX()} { j } {TEX} قرار دارد، بزرگ تر، یا کوچک تر، یا مساوی{TEX()} { k } {TEX} است. روشی ارائه دهید که با حداکثر{TEX()} { 2n – 1 } {TEX}کارت ورودی مشخص کند که{TEX()} { k } {TEX} در این جدول وجود دارد یا نه و در صورت وجود{TEX()} { k } {TEX} ، جای{TEX()} { k } {TEX} را مشخص کند.
روش خود را با پاسخ به سوالات زیر بیان کنید و درستی آن را ثابت کنید:
•با چه کارتی شروع می کنید؟
•بعد از دادن هر کارت و با توجه به جوابی که ماشین می دهد، چه کارتی را به ماشین می دهید؟
حل. مساله را به جای این که در جدول{TEX()} { n \times n } {TEX} حل کنیم، در حالت کلی تر{TEX()} { n \times m } {TEX} حل می کنیم و ثابت می کنیم در یک جدول{TEX()} {m\times n} {TEX} حداکثر با{TEX()} { n + m – 1 } {TEX} مقایسه می توان به جواب رسید.
فرض کنید که ما به ماشین کارت {TEX()} {(i, j) } {TEX} ({TEX()} { i } {TEX} شماره ی سطر و{TEX()} { j } {TEX} شماره ی ستون است) را داده باشیم؛ حال ببینیم براساس جواب ماشین به چه نتایجی می توان رسید. (فرض کنید که عدد خانه ی{TEX()} { (i, j) } {TEX} برابر با{TEX()} {a_{i,j}} {TEX} باشد.)
•{TEX()} {a_{i,j}=k} {TEX} باشد؛ در این صورت به جواب رسیده ایم.
#@
@#16:
•{TEX()} {a_{i,j}>k} {TEX} باشد؛ در این صورت حتماً{TEX()} {k} {TEX} از تمام عناصر{TEX()} {a_{i,j},a_{i,j+1},\cdots ,a_{i,n}} {TEX} و{TEX()} {a_{i,j},a_{i+1,j},\cdots ,a_{m,j}} {TEX} بزرگ تر است و نمی تواند هیچ یک از این عناصر باشد.
•{TEX()} {a_{i,j}<k} {TEX} باشد در این صورت حتماً {TEX()} { k } {TEX} از تمام عناصر{TEX()} {a_{i,j},a_{i,j-1},\cdots ,a_{i,1}} {TEX} و{TEX()} {a_{i,j},a_{i-1,j},\cdots ,a_{1,j}} {TEX} کوچک تر است و نمی تواند این عناصر باشد.
پس باید ما طوری{TEX()} { i, j } {TEX} را انتخاب کنیم که در هر مرحله حداقل یک سطر یا ستون از جدول حذف شود و به صورت بازگشتی (استقرایی) بتوانیم مساله را حل کنیم. اگر کارت داده شده به ماشین کارت{TEX()} { (1, n)} {TEX} باشد، در مقابل جواب{TEX()} {a_{1,n}<k} {TEX} درمی یابیم که عدد{TEX()} { k } {TEX} (در صورت وجود) در جدولی که از حذف ستون{TEX()} { n } {TEX} ام به دست می آید قرار دارد و از جواب{TEX()} {a_{1,n}<k} {TEX} می فهمیم که عدد{TEX()} { k } {TEX} (در صورت وجود) در جدولی که از حذف سطر اول به دست می آید قرار دارد (می توانستیم کارت{TEX()} { (m, 1)} {TEX} را نیز به ماشین بدهیم). در نتیجه با هر پرسش یا به جواب می رسیم یا یکی از اندازه ی سطر یا ستون ها کم می شود، بنابراین با استقرا ثابت می شود که در بدترین حالت با{TEX()} { n + m – 2 } {TEX}پرسش به یک جدول{TEX()} {1\times 1} {TEX} می رسیم که حالا با یک پرسش به جواب خواهیم رسید. پس در بدترین حالت با {TEX()} { n + m – 1} {TEX} مقایسه توانستیم به جواب برسیم.
---
!!مثال
یک دسته با{TEX()} { n } {TEX} سنگ ریزه داده شده است. دو نفر با هم این بازی را انجام می دهند: هر کس در نوبت خود باید تمام دسته های موجود با بیش از یک سنگ ریزه را به دلخواه به دو دسته ی ناتهی تقسیم کند. هر کس در نوبت خود نتواند حرکتی انجام دهد بازنده است (یعنی همه ی دسته ها تنها یک سنگ ریزه داشته باشد) و فرد دیگر برنده ی بازی است.
به عنوان مثال فرض کنید{TEX()} { n = 5} {TEX}. در این صورت نفر اول می تواند این دسته را به {TEX()} {(1,4)} {TEX} یا{TEX()} {(2,3)} {TEX} تقسیم کند. فرض کنید حرکت (2,3) را انتخاب کند. نفر دوم در هر صورت باید دسته ی دو تایی را به دو دسته ی 1 تایی تقسیم کند و دسته ی 3 تایی را باید به دو دسته ی 2 تایی و 1 تایی تقسیم کند. در حرکت بعدی نفر اول بازی را می برد.
به ازای چه{TEX()} { n } {TEX} هایی نفر اول و به ازای چه {TEX()} { n } {TEX} هایی نفر دوم می تواند طوری بازی کند که حتماً برنده شود؟
__حل. __
ثابت می کنیم که اگر{TEX()} { n } {TEX} به صورت{TEX()} {2^m-1} {TEX} باشد، نفر دوم و در غیر این صورت نفر اول برنده می شود.
برای اثبات این مساله حکم کلی تر زیر را ثابت می کنیم:
اگر در هر مرحله از بازی، تعداد سنگ ریره های بزرگ ترین دسته به شکل{TEX()} {2^m-1} {TEX} باشد، شخصی که نوبت اوست بازی را می بازد و در غیر این صورت، بازی را می برد.
#@
@#16:
اثبات با استفاده از استقرا (روی {TEX()} {m} {TEX}). اگر{TEX()} { n = 1 } {TEX} باشد طبق تعریف نفر اول باخته است و اگر{TEX()} { n=2 } {TEX} باشد، بعد از یک حرکت سنگ ریزه ها تبدیل به دو دسته ی یک تایی می شود و در نتیجه نفر دوم می بازد. به طریق مشابه اگر {TEX()} { n = 3} {TEX} باشد، نفر اول می بازد.
حال فرض کنید برای{TEX()} {n\le 2^m-1} {TEX} حکم ثابت شده باشد، می خواهیم درستی حکم را برای{TEX()} {2^m\le n\le 2^{m+1}-1} {TEX} ثابت کنیم.
اگر{TEX()} {n<2^{m+1}-1} {TEX} باشد، یعنی تعداد سنگ ریزه های بزرگ ترین دسته برابر{TEX()} { n } {TEX} باشد، نفر اول می تواند این دسته را به دو دسته ی{TEX()} {2^m-1} {TEX} و{TEX()} {n-2^m+1} {TEX} تایی تقسیم کند (بدیهی است که{TEX()} {n-2^m+1\le 2^m-1} {TEX}) و بقیه ی دسته ها را هم به دو دسته ی حداکثر{TEX()} {2^m-1} {TEX} سنگ ریزه ای تقسیم کند (مثلاً بقیه ی دسته ها را نصف کند). حال در مرحله ی بعد، تعداد سنگ ریزه های بزرگ ترین دسته{TEX()} {2^m-1} {TEX} است و نفر دوم هم شروع می کند. پس بنابر فرض استقرا نفر دوم بازنده است، بنابراین نفر اول برنده می شود.
اگر{TEX()} {n=2^{m+1}-1} {TEX} باشد، چون{TEX()} {[\frac{n}{2}]=2^m} {TEX}، هر طوری نفر اول دسته ها را تقسیم کند، حداقل یکی از دسته ها دارای حداقل{TEX()} {2^m} {TEX} سنگ ریزه است و همچنین تعداد سنگ ریزه های هر دسته حداکثر{TEX()} {2^{m+1}-2} {TEX} می باشد. بنابراین طبق حالت قبل چون نفر دوم شروع کننده است، نفر دوم استراتژی برد دارد، پس نفر اول بازنده است.
مساله ی فوق هم از تکنیک تغییر حل مساله و هم از تکنیک استقرای دوگانه استفاده کرد.

#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 پنج شنبه 16 شهریور 1385 [13:05 ]   2   زینب معزی      جاری 
 دوشنبه 26 تیر 1385 [12:07 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..