المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:استقرا

استقرا

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

بطور کلی استقرا یا استدلال استقرایی شیوه‌ای است که در آن از وجود یک ویژگی در چند مثال به قاعده‌ای کلی می‌رسند. ولی در ریاضیات استقرا روشی برای اثبات قضایا روی اعداد طبیعی است.

صورت‌های مختلف استقرا

استقرا به چند روش مختلف استفاده می‌شود:

استقرای ساده

فرض کنید می‌خواهیم حکم $P(n)$ را برای هر $n \in N$ ثابت کنیم. برای اثبات این قضیه با استقرا باید دو گام برداریم.

  • پایه‌ی استقرا: باید ثابت کنیم $P(1)$ درست است. معمولا پایه استقرا بسادگی اثبات می‌شود.
  • گام استقرا: اکنون با فرض اینکه حکم استقرا برای $P(k)$ درست است، حکم را برای $P(k+1)$ نیز اثبات می‌کنیم که $k$ عددی طبیعی است.

بدین ترتیب $P(1)$ درست است. با توجه به گام استقرا و درستی $P(1)$، $P(2)$ نیز درست خواهد بود و به همین ترتیب $P(n)$ برای هر عددی به اثبات می‌رسد.

مثال: ثابت کنید برای هر عدد طبیعی $\sum_{i=1}^{n} i = \frac{n \times (n+1)}{2}$.

پاسخ

می‌خواهیم حکم را با استقرای ساده ثابت کنیم. پس باید فرض استقرا و گام استقرا را توضیح دهیم. پایه‌ی استقرا: حکم به ازای $n=1$ درست است. چون $1= \frac{1 \times 2}{2}$. گام استقرا: فرض کنید حکم به ازای $n=k$ درست باشد. ثابت می‌کنیم حکم برای $n=k+1$ نیز صحیح است. برای اثبات این ادعا مجموع اعداد را بدین صورت می‌نویسیم: $\sum_{i=1}^{k+1} i = (1 + 2 + ... + k) + (k+1) = \sum_{i=1}^{k} i + (k+1) = \frac{k \times (k+1)}{2} + (k+1) = \frac{(k+1) \times (k+2)}{2}$

در نتیجه حکم مسئله به ازای $n=k+1$ به اثبات رسید.

مثال: ثابت کنید به ازای هر عدد طبیعی همانند $n$، عددی $n$ رقمی همانند $A_n$ وجود دارد که تنها از ارقام 1 و 2 تشکیل شده و بر $2^n$ بخش‌پذیر است.

پاسخ

روی عدد $n$ استقرا می‌زنیم.

پایه‌ی استقرا: به ازای $n=1$ عدد «2» یک رقمی است و بر $2^1$ بخش‌پذیر است. گام استقرا: فرض کنید مسئله به ازای $n=k$ درست باشد، ثابت می‌کنیم به ازای $n=k+1$ نیز صحیح است.

چون $A_k$ بر $2^k$ بخش‌پذیر است، باقیمانده‌اش بر $2^{k+1}$ دو حالت دارد:

حالت اول: $A_k \equiv 0 \pmod {2^{k+1}}$. در این حالت با اضافه کردن عدد 2 به سمت چپ $A_k$ حکم مسئله بدست می‌آید، زیرا در این صورت $A_{k+1} = A_k + 2^{k+1} \times 5^k$ که هر دو جمله‌ی سمت راست بر $2^{k+1}$ بخش‌پذیر هستند، پس $A_{k+1}$ نیز بخش‌پذیر خواهد بود.

حالت دوم: $A_k \equiv 2^k \pmod {2^{k+1}}$. در این حالت نیز با اضافه کردن عدد 1 به سمت چپ $A_k$ جواب بدست می‌آید. زیرا در این صورت $A_{k+1} = A_k + 2^{k} \times 5^k \equiv 2^k + 2^k = 2^{k+1} \pmod {2^{k+1}}$ که باز هم $A_{k+1}$ بر $2^{k+1}$ بخش‌پذیر شد.

پس گام استقرا ثابت و مسئله حل شد.

مثال: $n$ اتومبیل در یک مسیر دایره‌ای قرار دارند. مجموع سوخت آنها به میزانی است که یک اتومبیل بتواند این مسیر را بطور کامل طی کند. اگر اتومبیلی به اتومبیل دیگر برسد سوخت آن را می‌گیرد . ثابت کنید اتومبیلی وجود دارد که قبل از اتمام سوختش بتواند تمام مسیر را یکبار طی کند.

پاسخ

با استقرای ساده مسئله را حل می‌کنیم:

پایه‌ی استقرا: به ازای $n=1$ همان یک اتومبیل به میزان کافی سوخت دارد.

گام استقرا: فرض کنید قضیه برای $n=k$ برقرار است و می‌خواهیم مسئله را برای $n=k+1$ اتومبیل حل کنیم.

اتومبیلی همانند $A$ وجود دارد که به اتومبیل بعدی $B$ می‌تواند برسد (اگر هیچ‌کدام از اتومبیل‌ها نتوانند به اتومبیل بعدی خود برسند مجموع سوخت آنها به میزان یک دور کامل نیست). فرض کنید سوخت $B$ را به $A$ بدهیم و $B$ را حذف کنیم. حال $k$ اتومبیل داریم که سوخت آنها برای یک دور کافیست. طبق فرض استقرا اتومبیلی وجود دارد که می‌تواند تمام مسیر را طی کند. همین اتومبیل در بین $k+1$ اتومبیل نیز می‌تواند مسیر را بپیماید. زیرا مسیر از $A$ تا $B$ را می‌تواند با سوخت اتومبیل $A$ طی کند و مابقی مسیر را با سوختی که از دیگر اتومبیل‌ها در حالت $k$ اتومبیل گرفته می‌پیماید.

در نتیجه مسئله به ازای $n=k+1$ اتومبیل نیز اثبات شد.

استقرای قوی

تفاوت اصلی در این استقرا تنها در قسمت «گام استقرا» است. در این روش به جای فرض درستی $P(k)$، فرض می‌کنیم تمام عبارت‌های $P(1)$ تا $P(k)$ درست هستند و با استفاده از آنها درستی $P(k+1)$ را نتیجه می‌گیریم.

برای اثبات درستی استقرای قوی همانند قبل، می‌دانیم $P(1)$ درست است. درستی $P(2)$ از $P(1)$ نتیجه می‌‌شود. چون این دو عبارت صحیح هستند، $P(3)$ نیز درست خواهد بود و به همین ترتیب برای هر عددی $P(n)$ ثابت می‌شود.

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

استقرای قهقرایی

TO DO


ابزار صفحه