Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۹:سوال ۱

تالارهای دوستی

یک مدرسه، سه تالار اجتماع A، B و C دارد. یک روز، همه‌ی دانش‌آموزان در تالار A‌ جمع شدند و معلوم شد هر دانش‌آموز لااقل s+t نفر را می‌شناسد. بعد از این، تعدادی از دانش‌آموزان به تالار B و تعدادی به تالار C رفتند. می‌دانیم که در تالار B هر نفر لااقل s نفر را در همان تالار می‌شناسد و در تالار C نیز هر نفر حداقل t نفر را در همان تالار می‌شناسد. ثابت کنید افرادی که در تالار A مانده‌اند را می‌توان به گونه‌ای بین دو تالار B و C تقسیم کرد، به طوری که بعد از تقسیم باز هم هر نفر در تالار B لااقل s نفر از افراد همان تالار و هر نفر در تالار C لااقل t نفر از افراد همان تالار را بشناسد (فرض کنید آشنایی یک رابطه‌ی دو طرفه است، یعنی اگر a شخص b را بشناسد b نیز a را می‌شناسد).


ابزار صفحه