المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳:سوال ۴

سوال ۴

در یک مدرسه $x$ دبیر تدریس می‌کنند. این دبیرها را با شماره‌های ۱ تا $n$ نام‌گذاری می‌کنیم. می‌دانیم که دبیر $i$ ام، $i+1$ نفر از دانش‌آموزان مدرسه را می‌شناسد. هر دانش‌آموز می‌تواند توسط بیش از یک دبیر شناخته شود. هر یک از این دبیرها می‌خواهد یکی از دانش‌آموزانی را که می‌شناسد به عنوان نماینده‌ی خود برگزیند به شرط این که هیچ دانش‌آموزی به عنوان نماینده‌ی بیش از یک دبیر انتخاب نشود. ثابت کنید که انتخاب این نماینده‌ها حداقل به $2^n$‌حالت مختلف امکان‌پذیر است.


ابزار صفحه