بر روی صندلیهای یک مترو افراد A1، A2، A3 در یک ردیف و B1، B2، B3 در ردیف مقابل نشستهاند. طبق عادت همیشگی، هر کس به دلخواه به یکی از افراد روبهروی خود زیرزیرکی نگاه میکند!}
یک حالت را پایدار گوییم، اگر هیچ دو نفری نباشند که به یکدیگر نگاه کنند (چشمتوچشم شوند!). چند حالت پایدار وجود دارد؟
راهنمایی
مجموعه افرادی که A ها به آن ها نگاه میکنند را در نظر بگیرید حداقل دو عضو دارد. در مجموعه دو عضوی یک B وجود دارد که توسط یک نفر نگاه می شود و دیگری توسط دو نفر. در مجموعه سه عضوی هر B دقیقا توسط یک نفر نگاه می شود.
پاسخ
گزینهی ۵ درست است.
مجموعهی افرادی که Aiها به آنها نگاه میکنند را در نظر بگیرید. چند حالت داریم:
پس پاسخ برابر ۱۵۶ است.
زوج مرتب (i,j) را بیربط گوییم، اگر Ai و Bj هیچکدام دیگری را نگاه نکنند. به ترتیب حداقل و حداکثر چند زوج بیربط داریم؟
راهنمایی
اگر هر کس دقیقا به رو به روییش نگاه کند چه می شود؟ و اگر هر 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 را نگاه کند؟
راهنمایی
هر فرد به طور غیر مستقیم حداکثر یک نفر را می بیند
پاسخ
گزینهی ۳ درست است.
هر فرد به طور غیر مستقیم حداکثر یک نفر را میبیند. پس پاسخ حداکثر برابر ۶ است. از طرفی اگر هر Ai به Bi و هر Bi به Ai+1 نگاه کند (و B3 به A1 نگاه کند)، آنگاه مثال ۶ نیز ساخته میشود.