المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۷:سوال ۵۳

سوال ۵۳

در شکل زیر خط‌هایی که با $r$ مشخص شده‌اند٬ قرمز و آن‌هایی که با $b$ مشخص شده‌اند آبی هستند.

آیا باتوجه به جهت‌هایی که روی خط‌ها مشخص شده‌اند٬ مسیری از $A$ به $D$ وجود دارد که رنگ خط‌های آن به ترتیب آبی٬ آبی٬ آبی٬ قرمز و آبی باشد؟

پاسخ

زیرا قسمت آخر(پنجم) مسیر مورد نظر باید آبی بوده و به $D$ ختم شود که تنها مسیر $CD$ می‌باشد. قسمت ماقبل آخر(چهارم) مسیر مورد نظر باید قرمز بوده و به $C$ ختم شود که تنها مسیر $DC$ این خاصیت را دارد و اما هیچ مسیر جدیدی(آبی‌رنگ) وجود ندارد که به $D$ ختم شده باشد.

تذکر: اگر مجاز باشیم از یک خط دو بار عبور کنیم آن‌گاه جواب این مسئله مثبت است و مسیر مورد نظر به صورت زیر می‌باشد:

$$A \longrightarrow B \longrightarrow C \longrightarrow D \longrightarrow C \longrightarrow D$$


ابزار صفحه