جلسهی 7: مسیرها روی جدول Paths on a Grid
از گوشه به گوشه با قدمهای راست و بالا: شمردن با جمع کردنِ عددها روی نقطهها، فرمول با ترکیب، گذشتن از یک نقطهی خاص، دور زدنِ نقطههای ممنوع، و یک تونل!
در این جلسه یاد میگیری
- مسیرهای روی جدول را با عددگذاری روی نقطهها میشماری.
- میدانی هر مسیر یک رشته از «راست» و «بالا» است و تعدادش یک ترکیب است.
- مسیرهایی که از یک نقطه میگذرند یا از نقطهای دوری میکنند را میشماری.
درس
از گوشهی پایین چپ به بالا راست، هر قدم یک واحد به راست یا به بالا. «شمارش قدمبهقدم» را بزن: عدد هر نقطه = عدد چپ + عدد پایین. بعد «یک مسیر تصادفی» را چند بار بزن.
چرا جمع؟ آخرین قدم برای رسیدن به هر نقطه یا از چپ است یا از پایین، و این دو دسته مشترک ندارند (اصل جمع). نقطههای ردیف پایین و ستون چپ فقط یک راه دارند.
راه دوم: هر مسیر از (۰,۰) تا (۴,۳) دقیقاً ۴ قدم راست (ر) و ۳ قدم بالا (ب) دارد، مثل «ررببررب». پس مسیر یعنی انتخاب جای ۳ تا «ب» در ۷ قدم: C(۷, ۳) = ۳۵. همان عدد بازی!
گذشتن از یک نقطه: چند مسیر از A به B از نقطهی M میگذرد؟ مسیر دو تکه است: A تا M و بعد M تا B. اصل ضرب: (مسیرهای A تا M) × (مسیرهای M تا B).
مثال: در جدول ۴ × ۴ از (۰,۰) تا (۴,۴) با گذشتن از (۲,۲): C(۴, ۲) × C(۴, ۲) = ۶ × ۶ = ۳۶.
نقطهی ممنوع: اگر یک نقطه خراب باشد و نشود از آن گذشت، دو راه داری:
۱) روی نقطهی خراب ۰ بنویس و باقی را مثل قبل جمع بزن.
۲) همهی مسیرها منهای مسیرهایی که از نقطهی خراب میگذرند.
در بازی پایین، نقطهی (۲,۱) خراب است. ببین عددها چطور عوض میشوند.
اشتباه رایج: وقتی دو نقطهی ممنوع داری، «همه منهای مسیرهای از نقطهی اول منهای مسیرهای از نقطهی دوم» درست نیست اگر مسیری از هر دو بگذرد؛ آن مسیرها دو بار کم شدهاند. روش ۱ (عددگذاری با صفر) این دردسر را ندارد. در المپیاد، وقتی شکل عجیب است (تونل، نقطهی ممنوع، حرکتهای اریب)، عددگذاری روی نقطهها مطمئنترین راه است.
چالشها
- A Small Grid (آسان)
- Five Rights and Two Ups (آسان)
- Through the Middle (متوسط)
- A Broken Crossing (متوسط)
- Two Broken Crossings (سخت)
- The Magic Tunnel (سخت)
- Try It in Python: Round a Broken Crossing (سخت)