بر روی صندلیهای یک مترو افراد $A_1$، $A_2$، $A_3$ در یک ردیف و $B_1$، $B_2$، $B_3$ در ردیف مقابل نشستهاند. طبق عادت همیشگی، هر کس به دلخواه به یکی از افراد روبهروی خود زیرزیرکی نگاه میکند!}
یک حالت را پایدار گوییم، اگر هیچ دو نفری نباشند که به یکدیگر نگاه کنند (چشمتوچشم شوند!). چند حالت پایدار وجود دارد؟
پاسخ
گزینهی ۵ درست است.
مجموعهی افرادی که $A_i$ها به آنها نگاه میکنند را در نظر بگیرید. چند حالت داریم:
پس پاسخ برابر ۱۵۶ است.
زوج مرتب $(i, j)$ را بیربط گوییم، اگر $A_i$ و $B_j$ هیچکدام دیگری را نگاه نکنند. به ترتیب حداقل و حداکثر چند زوج بیربط داریم؟
پاسخ
گزینهی ۲ درست است.
یک $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$ نگاه کند)، آنگاه مثال ۶ نیز ساخته میشود.