المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

تیم فوتبال سلطان، با سیستم $4-4-2$ بازی می‌کند؛ یعنی ۱ دروازه‌بان، ۴ مدافع و ۴ هافبک و ۲ مهاجم دارد. هر توپی که به یک بازیکن در این تیم می‌رسد، یا آن را با یک شوت، تبدیل به گل می‌کند یا پاس می‌دهد.

هیچ بازیکنی حق ندارد به بازیکنی پاس بدهد که قبلا توپ به او رسیده و یا در خطوط عقب‌تر بازی می‌کند؛ برای مثال یک هافبک نمی‌تواند به یک مدافع پاس بدهد، اما می‌تواند به یک هافبکی که توپ به آن نرسیده و یا یک مهاجم پاس بدهد.

فرض کنید توپ در ابتدا در اختیار دروازه‌بان است و تیم می‌خواهد یک گل بزند (همانند شکل زیر). به چند طریق می‌توان این کار را انجام داد؟ (حتی دروازه‌بان هم می‌تواند با یک ضربه‌ی مستقیم گل بزند.)

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

پاسخ

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

فرض کنید یک خط در این سیستم $k$ نفر داشته باشد. می‌خواهیم تعداد حالاتی را از لحظه‌ی رسیدن توپ به یکی از بازی‌کنان این خط تا لحظه‌ی بیرون کردن توپ از این خط (با پاس رو به جلو یا شوت) حساب کنیم. این تعداد حالات را $a_k$ می‌نامیم. یک حالت وجود دارد که توپ اصلن به هیچ یک از بازی‌کنان این خط نرسد. در غیر این صورت $k$ حالت برای انتخاب بازی‌کن شروع کننده در این خط وجود دارد. انجام بقیه‌ی کار به $a_{k-1}$ حالت توسط بقیه‌ی بازی‌کنان این خط قابل انجام است. پس $$a_k = ka_{k-1} + 1$$

حال طبق اصل ضرب پاسخ برابر «تعداد حالات توپ در خط دفاعی ضرب در تعداد حالات توپ در خط هافبک ضرب در تعداد حالات توپ در خط حمله» است. پس پاسخ برابر $$a_4 \times a_4 \times a_2$$ خواهد بود. از طرفی $$a_1 = 2, a_2 = 2 \times 2 + 1 = 5, a_3 = 3 \times 5 + 1 = 16, a_4 = 4 \times 16 + 1 = 65$$ پس پاسخ برابر $$65 \times 65 \times 5 = 21125$$ است.


ابزار صفحه