المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۳:سوالات ۹ تا ۱۰

سوالات ۹ تا ۱۰

در این دسته سوال، با یک تیم فوتبال سر و کار داریم که ۱۱ بازی‌کن در آن عضو هستند. در یک چینش تیم، بازی‌کن ها در ۱۱ جایگاه متمایز قرار می‌گیرند. آن‌ها در ابتدا در یک چینش اولیه قرار گرفته‌اند. بازی‌کن‌های تیم می‌توانند جابه‌جا شوند و یک چینش جدید بسازند. چینش جدید می‌تواند همان چینش اولیه هم باشد. می‌خواهیم تعداد چینش‌های جدید تیم با شرایط گفته شده در هر سوال را حساب کنیم. دو چینش را متمایز در نظر می‌گیریم، اگر جایگاهی وجود داشته باشد که بازی‌کن آن جایگاه، در این دو چینش متفاوت باشند.

با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید.

سوال ۹

در این سوال، به جز دروازه‌بان، چهار بازی‌کن در خط دفاع، پنج بازی‌کن در خط میانی و یک بازی‌کن در خط حمله حضور دارند. جایگاه‌های مجاز هر بازی‌کن در چینش جدید، به صورت زیر است:

  • دروازه‌بان چینش اولیه، باید سر جایش باقی بماند.
  • هر بازی‌کن خط دفاع از چینش اولیه، می‌تواند در یکی از جایگاه‌های خط دفاع یا خط میانی بازی کند.
  • هر بازی‌کن خط میانی از چینش اولیه، می‌تواند در تمام جایگاه‌ها به جز جایگاه دروازه‌بان بازی کند.
  • هر بازی‌کن خط حمله از چینش اولیه، می‌تواند در یکی از جایگاه‌های خط میانی یا خط حمله بازی کند.

با این شرایط، چند چینش جدید برای تیم وجود دارد؟

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

راهنمایی

با توجه به اینکه در خط حمله فقط یک بازیکن حضور دارد، احتمالاً حالت‌بندی روی جایگاه این بازیکن راحت‌تر است!
چند چینش جدید وجود دارد، به طوری که در آنها بازیکن حط حمله سر جایش باقی مانده باشد؟
چند چینش جدید وجود دارد، به طوری که در آنها بازیکن حط حمله سر جایش باقی نمانده باشد؟

راهنمایی

دروازه‌بان باید سر جایش باقی بماند. اگر بازیکن خط حمله هم سر جایش بماند، همه‌ی جایگاه‌های باقی‌مانده برای بازیکن‌های دیگر مجاز هستند.

راهنمایی

پس $9! = 362880$ چینش جدید با شرایط گفته شده وجود دارد، در حالتی که بازیکن خط حمله سر جایش باقی بماند.

راهنمایی

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

راهنمایی

باز هم همه‌ی جایگاه‌های باقی مانده برای همه‌ی بازیکن‌های باقی مانده مجاز هستند! (چرا؟ همه‌ی جایگاه‌های باقی مانده، در خط دفاع و خط میانی هستند؛ همه‌ی بازیکن‌های باقی مانده هم بازیکنان خط دفاع یا خط میانی در چینش اولیه هستند. پس هرکدام از بازیکن‌های باقی مانده اجازه دارد در هرکدام از جایگاه‌های باقی مانده قرار بگیرد.)
پس این بازیکن‌ها به $8! = 40320$ روش می‌توانند در جایگاه‌های باقی مانده قرار بگیرند. بنا به اصل ضرب، در حالتی که بازیکن خط حمله سر جایش نماند، تعداد چینش‌های جدید با شرایط گفته شده $5 * 5 * 8! = 1008000$ است.

سوال ۱۰

در این سوال، مطابق شکل زیر، هر بازی‌کن مانند $P$ می تواند در جایگاه‌های زیر بازی کند:

  • در جایگاه خودش در چینش اولیه
  • در جایگاه بازی‌کن هایی مانند $Q$ که $P$ و $Q$ در شکل، با خطی بدون جهت به هم وصل شده باشند.
  • در جایگاه بازی‌کن‌هایی مانند $Q$ که در شکل، خطی جهت‌دار از $P$ به $Q$ موجود باشد.

با این شرایط، چند چینش جدید برای تیم وجود دارد؟

  1. ۱۰۲۴
  2. ۲۴
  3. ۴۸
  4. ۹۶
  5. ۷۲۰

راهنمایی

چند چینش جدید وجود دارد به طوری که بازیکن $P$ در جایگاه بازیکن $Q$ قرار بگیرد؟

راهنمایی

هیچ حالتی وجود ندارد!
هافبک‌های میانی(جایگاه‌های قرمز) باید در جایگاه هافبک میانی باقی بمانند، چون بقیه‌ی بازیکن‌ها نمی‌توانند در جایگاه آنها بازی کنند. پس جایگاه هافبک‌های میانی $2$ حالت دارد.

راهنمایی

نشان دادیم خط‌های جهت‌دار قرمز قابل استفاده نیستند. نشان دهید هیچ‌کدام از خط‌های جهت‌دار قابل استفاده نیستند!

راهنمایی

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

راهنمایی

بازیکنان باقی مانده در همه‌ی جایگاه‌های باقی‌مانده می‌توانند بازی کنند و چینش آنها $4!$ حالت دارد.
پس برای چینش جدید $2 * 2 * 4!$ حالت با شرایط گفته شده وجود دارد.


ابزار صفحه