سوالات ۲۵ تا ۲۷
بر روی صندلیهای یک مترو افراد $A_1$، $A_2$، $A_3$ در یک ردیف و $B_1$، $B_2$، $B_3$ در ردیف مقابل نشستهاند. طبق عادت همیشگی، هر کس به دلخواه بهیکی از افراد روبهروی خود زیرزیرکی نگاه میکند!}
سوال ۲۵
یک حالت را پایدار گوییم، اگر هیچ دو نفری نباشند که بهیکدیگر نگاه کنند (چشمتوچشم شوند!). چند حالت پایدار وجود دارد؟
- ۱۸
- ۳۶
- ۴۸
- ۱۰۸
- ۱۵۶
راهنمایی
مجموعه افرادی که A ها به آن ها نگاه میکنند را در نظر بگیرید حداقل دو عضو دارد. در مجموعه دو عضوی یک B وجود دارد که توسط یک نفر نگاه میشود و دیگری توسط دو نفر. در مجموعه سه عضوی هر B دقیقا توسط یک نفر نگاه میشود.
پاسخ
گزینهی ۵ درست است.
مجموعهی افرادی که $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$ هیچکدام دیگری را نگاه نکنند. به ترتیب حداقل و حداکثر چند زوج بیربط داریم؟
- ۰ و ۶
- ۳ و ۶
- ۳ و ۳
- ۱ و ۳
- ۰ و ۳
راهنمایی
اگر هر کس دقیقا به رو به روییش نگاه کند چه میشود؟ و اگر هر A به رو به روییش و هر $B_j$ به $A_{j+1}$ نگاه کنید و $B_3$ به $A_1$ نگاه کنید چه میشود؟
پاسخ
گزینهی ۲ درست است.
یک $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$ را نگاه کند؟
- ۴
- ۵
- ۶
- ۸
- ۱۲
راهنمایی
هر فرد به طور غیر مستقیم حداکثر یک نفر را میبیند
پاسخ
گزینهی ۳ درست است.
هر فرد به طور غیر مستقیم حداکثر یک نفر را میبیند. پس پاسخ حداکثر برابر ۶ است. از طرفی اگر هر $A_i$ به $B_i$ و هر $B_i$ به $A_{i+1}$ نگاه کند (و $B_3$ به $A_1$ نگاه کند)، آنگاه مثال ۶ نیز ساخته میشود.
| < سوال قبل | سوال بعد > |