المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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


ابزار صفحه