المپدیا

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

ابزار کاربر

ابزار سایت


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

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

بر روی صندلی‌های یک مترو افراد $A_1$، $A_2$، $A_3$ در یک ردیف و $B_1$، $B_2$، $B_3$ در ردیف مقابل نشسته‌اند. طبق عادت همیشگی، هر کس به دل‌خواه به یکی از افراد روبه‌روی خود زیرزیرکی نگاه می‌کند!}

سوال ۲۵

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

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

پاسخ

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

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

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

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

سوال ۲۶

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

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

پاسخ

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

یک $A_i$ دل‌خواه را در نظر بگیرید که به $B_j$ نگاه می‌کند. از دیگر افراد دسته‌ی $B$ حداقل یک و حداکثر دو نفر به $A_i$ نگاه نمی‌کنند. پس $A_i$ در حداقل یک و حداکثر دو زوج بی‌ربط حضور دارد. پس حداقل ۳ و حداکثر ۶ زوج بی‌ربط داریم. از طرفی مثال برای ۳ و ۶ زوج بی‌ربط وجود دارد. برای مثال ۳ زوج بی‌ربط فرض کنید به ازای هر $i$، $A_i, B_i$ به یک‌دیگر نگاه کنند. برای مثال ۶ زوج بی‌ربط فرض کنید هر $A_i$ به $B_i$ و هر $B_i$ به $A_{i+1}$ نگاه کند (و $B_3$ به $A_1$ نگاه کند).

سوال ۲۷

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

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

پاسخ

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

هر فرد به طور غیر مستقیم حداکثر یک نفر را می‌بیند. پس پاسخ حداکثر برابر ۶ است. از طرفی اگر هر $A_i$ به $B_i$ و هر $B_i$ به $A_{i+1}$ نگاه کند (و $B_3$ به $A_1$ نگاه کند)، آن‌گاه مثال ۶ نیز ساخته می‌شود.


ابزار صفحه