Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۵ تا ۲۷

بر روی صندلی‌های یک مترو افراد A1، A2، A3 در یک ردیف و B1، B2، B3 در ردیف مقابل نشسته‌اند. طبق عادت همیشگی، هر کس به دل‌خواه به یکی از افراد روبه‌روی خود زیرزیرکی نگاه می‌کند!}

سوال ۲۵

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

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

راهنمایی

مجموعه افرادی که A ها به آن ها نگاه میکنند را در نظر بگیرید حداقل دو عضو دارد. در مجموعه دو عضوی یک B وجود دارد که توسط یک نفر نگاه می شود و دیگری توسط دو نفر. در مجموعه سه عضوی هر B دقیقا توسط یک نفر نگاه می شود.

پاسخ

گزینه‌ی ۵ درست است.

مجموعه‌ی افرادی که Aiها به آن‌ها نگاه می‌کنند را در نظر بگیرید. چند حالت داریم:

  • اگر این مجموعه تک‌عضوی باشد (یعنی همه‌ی Aiها به یک نفر خاص نگاه کنند، آن نفر خاص به هیچ Ai نمی‌تواند نگاه کند. پس این حالت معتبر نیست.
  • اگر این مجموعه دوعضوی باشد، دو نفر از Aiها به یک نفر خاص و دیگری به نفری دیگر نگاه می‌کند. تا این‌جا Aiها به 3×3×2=18 حالت می‌توانند نگاه کنند. از Biها یک نفر هست که دو نفر به آن نگاه می‌کند. این فرد باید به تنها Aiای نگاه کند که به او نگاه نمی‌کند. یک نفر دیگر از Biها وجود دارد که یک نفر به او نگاه می‌کند. این فرد دو انتخاب برای نگاه کردن دارد. یک نفر دیگر هم از Biها وجود که کسی به او نگاه نمی‌کند. او سه انتخاب برای نگاه کردن دارد. بنابراین Biها برای نگاه کردن 3×2×1=6 انتخاب برای نگاه کردن دارند. در مجموع 18×6=108 انتخاب برای نگاه کردن در این حالت وجود دارد.
  • اگر این مجموعه سه‌عضوی باشد، Aiها 3!=6 انتخاب و Biها 23=8 انتخاب برای نگاه کردن دارند که در مجموع برابر با ‌48 انتخاب می‌شود.

پس پاسخ برابر ۱۵۶ است.

سوال ۲۶

زوج مرتب (i,j) را بی‌‌ربط گوییم، اگر Ai و Bj هیچ‌کدام دیگری را نگاه نکنند. به ترتیب حداقل و حداکثر چند زوج بی‌ربط داریم؟

  1. ۰ و ۶
  2. ۳ و ۶
  3. ۳ و ۳
  4. ۱ و ۳
  5. ۰ و ۳

راهنمایی

اگر هر کس دقیقا به رو به روییش نگاه کند چه می شود؟ و اگر هر A به رو به روییش و هر Bj به Aj+1 نگاه کنید و B3 به A1 نگاه کنید چه می شود؟

پاسخ

گزینه‌ی ۲ درست است.

یک Ai دل‌خواه را در نظر بگیرید که به Bj نگاه می‌کند. از دیگر افراد دسته‌ی B حداقل یک و حداکثر دو نفر به Ai نگاه نمی‌کنند. پس Ai در حداقل یک و حداکثر دو زوج بی‌ربط حضور دارد. پس حداقل ۳ و حداکثر ۶ زوج بی‌ربط داریم. از طرفی مثال برای ۳ و ۶ زوج بی‌ربط وجود دارد. برای مثال ۶ زوج بی‌ربط فرض کنید به ازای هر i، Ai,Bi به یک‌دیگر نگاه کنند. برای مثال ۳ زوج بی‌ربط فرض کنید هر Ai به Bi و هر Bi به Ai+1 نگاه کند (و B3 به A1 نگاه کند).

سوال ۲۷

می‌گوییم فرد X غیر مستقیم فرد Y را می‌بیند، اگر فردی مانند Z وجود داشته باشد که X، Z را نگاه کند و Z، Y را نگاه کند. حداکثر چند زوج (X,Y) داریم که X به طور غیرمستقیم Y را نگاه کند؟

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

راهنمایی

هر فرد‌ به طور غیر مستقیم حداکثر یک نفر را می بیند

پاسخ

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

هر فرد به طور غیر مستقیم حداکثر یک نفر را می‌بیند. پس پاسخ حداکثر برابر ۶ است. از طرفی اگر هر Ai به Bi و هر Bi به Ai+1 نگاه کند (و B3 به A1 نگاه کند)، آن‌گاه مثال ۶ نیز ساخته می‌شود.


ابزار صفحه