جلسهی 13: استقرا: از کوچک به بزرگ Induction and Step-by-Step Counting
اگر مسئلهی کوچک را بلدی و میدانی چطور از هر اندازه به اندازهی بعدی بروی، همهی اندازهها را بلدی. برج هانوی، کاشیکاریِ نوارها، و خطهایی که صفحه را میبُرند.
در این جلسه یاد میگیری
- مسئله را برای اندازههای کوچک حل میکنی و الگو پیدا میکنی.
- رابطهای بین جوابِ یک اندازه و اندازههای قبلی مینویسی (رابطهی بازگشتی).
- میفهمی استقرا یعنی پایه + قدم، مثل افتادنِ دومینوها.
درس
برج هانوی: همهی حلقهها را از میلهی اول به میلهی آخر ببر. هر بار فقط یک حلقه، و هیچوقت حلقهی بزرگ روی کوچک. با ۳ حلقه کمترین تعداد حرکت چند است؟
فکر استقرایی: برای جابهجا کردنِ n حلقه، باید n − ۱ حلقهی بالایی را کنار بگذاری (روی میلهی وسط)، بزرگترین را ببری، و آن n − ۱ حلقه را دوباره رویش بگذاری. اگر T(n) کمترین تعداد حرکت باشد:
T(n) = T(n − ۱) + ۱ + T(n − ۱) = ۲T(n − ۱) + ۱
T(۱) = ۱، T(۲) = ۳، T(۳) = ۷، T(۴) = ۱۵ … یعنی ۲ⁿ − ۱.
استقرا مثل یک ردیف دومینوست: ۱) پایه: دومینوی اول میافتد (حالت کوچک درست است). ۲) قدم: هر دومینو که بیفتد، بعدی را میاندازد (اگر برای n درست باشد، برای n + ۱ هم درست است). پس همه میافتند! در مرحلهی اول معمولاً کافی است الگو را پیدا کنی؛ در مرحلهی دوم باید پایه و قدم را بنویسی (فاز ۵).
کاشیکاریِ نوار: یک نوارِ ۲ × n را با دومینو بپوش. به ستون آخر نگاه کن: یا یک دومینوی ایستاده آن را پر کرده (بقیه یک نوار ۲ × (n − ۱) است)، یا دو دومینوی خوابیده دو ستون آخر را پر کردهاند (بقیه ۲ × (n − ۲)). پس:
a(n) = a(n − ۱) + a(n − ۲)
a(۱) = ۱، a(۲) = ۲، a(۳) = ۳، a(۴) = ۵ … همان فیبوناچیِ قورباغه! صفحهی ۲ × ۴ را امتحان کن:
یک الگوی معروف دیگر: n خط در صفحه که هیچ دو تایی موازی نیستند و هیچ سه تایی از یک نقطه نمیگذرند. خط nام با n − ۱ خطِ قبلی برخورد دارد، پس از n ناحیه رد میشود و هر کدام را دو تکه میکند: n ناحیهی تازه.
R(n) = R(n − ۱) + n، با R(۰) = ۱. پس R(n) = ۱ + (۱ + ۲ + … + n).
اشتباه رایج: از روی ۳ عدد اول حدس زدن بدون فهمیدنِ «چرا». مثلاً ۱، ۲، ۴ را ببینی و بگویی بعدی ۸ است، در حالی که R(۳) = ۷.
چالشها
- Four Disks (آسان)
- A 2 by 5 Strip (آسان)
- Five Lines (متوسط)
- No Two Neighbours (متوسط)
- Hanoi with a Rule (سخت)
- Dominoes and Squares (سخت)
← جلسهی 12: رنگآمیزی: یک استدلالِ رنگی جلسهی 14: راستگوها و دروغگوها →