المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۸

در پارکینگ مشتی ممدعلی سیستم عجیبی برای پارک کردن ماشین‌ها برقرار است. این پارکینگ هفت جای پارک دارد که به ترتیب با شماره‌های صفر تا شش مشخص‌ شده‌اند. هر ماشینی که به پارکینگ وارد می‌شود ابتدا سراغ جای پارکی می‌رود که به شماره‌ی آن برابر باقی‌مانده‌ی تقسیم شماره‌ی پلاک ماشین بر عدد هفت است.اگر این جای پارک پر بود به سراغ بعدی می‌رود ( اگر جای پارک شماره شش پر بود به سراغ شماره صفر می‌رود) و همین‌طور ادامه می‌دهد تا به اولین جای پارک خالی برسد و آن جا پارک می‌کندو سپس ماشین بعدی وارد پارکینگ می‌شود. اگر در انتها ماشین‌ها در پارکینگ به ترتیب ۴۶، ۶۸، ۳۹، ۹۳، ۲۳، ۷۰، ۹۸ ایستاده باشند (پلاک شماره‌ی ۹۸ در جای پارک شماره‌ی صفر و پلاک ۴۶ در پارکینگ شماره‌ی ۶)، چند ترتیب ممکنِ اولیه برای ورود آن‌ها ممکن است؟

  1. ۵۰۴۰
  2. ۲۱۰
  3. ۳۰۵
  4. ۴۲۰
  5. ۷۲۰

پاسخ

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

باقی‌مانده اعداد داده شده بر ۷ از چپ به راست به ترتیب برابر ۵٬۴٬۲٬۲٬۰٬۰ و ۴ می‌باشد. اگر ماشین‌ها را از چپ به راست به ترتیب با $a$،$b$،$c$،$d$،$e$،$f$ و $g$ نام‌گذاری کنیم آن‌گاه باید $a$ قبل از $b$،$c$ قبل از $d$ و بالاخره $g$ بعد از دو ماشین $f$ و $e$ به پارکینگ وارد شوند که تعداد جای‌گشت‌های مورد نظر با شرط فوق برابر $\frac{7!}{2\times2\times3}$ یعنی ۴۲۰ به‌دست می‌آید.


ابزار صفحه