المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۹

برای انجام پروژه‌ی خاصی به انجام هفت کار مختلف نیازمندیم. ترتیب انجام کارها در شکل مقابل آمده است٬ به این صورت نشان می‌دهد که کار $a$ باید قبل از کار $b$ صورت گیرد. این پروژه را به چند ترتیب مختلف می‌توان انجام داد؟

  1. ۱۸
  2. ۱۵
  3. ۱۲
  4. ۹
  5. ۶

پاسخ

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

اگر کار شماره‌ی ۲ را در نظر نگیریم بقیه‌ی ۶ کار به دو صورت:

$$1 \longrightarrow4\longrightarrow5\longrightarrow6\longrightarrow3\longrightarrow7 \quad and \quad 1\longrightarrow4\longrightarrow5\longrightarrow3\longrightarrow6\longrightarrow7$$

قابل انجام است. حال اگر توجه کنیم کار شماره ۲ بعد از کار شماره ۱ در هر مرحله قابل اجراست؛ یعنی بر هر دو مورد بالا ۶ حالت ممکن است اتفاق افتد(یعنی کار شماره ۲ بعد از هر کدام از کارهای شماره ۶٬۵٬۴٬۳٬۱ و ۷ می‌تواند انجام گیرد). پس در کل٬ تعداد حالات ممکن برای انجام پروژه ۱۲ می‌باشد.


ابزار صفحه