المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۴:سوال ۱۷

سوال ۱۷

در شکل مقابل٬ چند مسیر مختلف به طول ۸ از $A$ به $B$ داریم که تعداد زوجی علامت ـ داشته باشند؟ یکی از این مسیر‌ها در شکل نشان داده شده است.

  1. ۱۶
  2. ۳۲
  3. ۳۳
  4. ۳۵
  5. ۶۴

پاسخ

گزینه (؟) درست است.

برای هر راس٬ خانه‌ای مطابق شکل مقابل متناظر می‌کنیم. عدد بالایی در هر خانه نشان‌گر تعداد مسیرهایی از $A$ تا به راس متناظر به آن خانه می‌باشد که تعداد علامت‌های - در آن مسیرها٬ زوج باشد و عدد پایینی نشان‌گر تعداد مسیرهای از $A$ به آن مقصد می‌باشد که تعداد علامت‌های - در آن مسیرها٬ فرد است. اگر علامت راسی + باشد(رئوس متناظر به خانه‌های سفید)٬ آن‌گاه عدد بالایی خانه متناظرش با مجموع دو عدد بالایی خانه‌های پایین و چپش و عدد پایینی آن با مجموع دو عدد پایینی آن دو خانه برابر است٬ و اگر علامت راسی - باشد(رئوس متناظر به خانه‌های تیره)٬ آن‌گاه عدد بالایی خانه متناظرش با مجموع دو عدد پایینی خانه‌های پایین و چپش و عدد پایینی آن با مجموع دو عدد بالایی آن دو خانه برابر خواهد بود.


ابزار صفحه