المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۳ و ۲۴

$n$ دستگاه پخش کننده‌ی موسیقی یکسان و $n$ هندزفری یکسان داریم. به هر کدام از دستگاه‌ها یک هندزفری وصل کرده‌ایم. هر هندزفری نیز دو گوشی دارد که یکی مخصوص گوش راست و یکی مخصوص گوش چپ است.

$n$ نفر در یک گروه هستند و می‌خواهند از طریق این دستگاه‌ها و هندزفری‌ها موسیقی گوش کنند. هر کس می‌تواند یک گوشی‌ چپ و یک گوشی راست برداشته و آهنگ گوش کند. دو گوشی‌ای که یک فرد برمی‌دارد می‌توانند از یک هندزفری نباشند، اما باید آهنگ یکسانی را پخش کنند.

در انتها تأکید می‌کنیم دستگاه‌های پخش‌ کننده و هندزفری‌ها را یکسان در نظر بگیرید.

سوال ۲۳

فرض کنید $n=4$ است. دو تا از دستگاه‌ها در حال پخش موسیقی $M_1$ و دو تای دیگر در حال پخش موسیقی $M_2$ هستند. افراد به چند طریق می‌توانند هندزفری‌ها را استفاده کرده و موسیقی‌ها را گوش کنند؟

  1. ۱۲
  2. ۲۴
  3. ۴۸
  4. ۱۶
  5. ۱۸

پاسخ

گزینه‌ی ۲ درست است.

انتخاب دو نفری که در حال گوش کردن به موسیقی $M_1$ هستند $\binom{4}{2}$ حالت دارد. دو نفر دیگر باید موسیقی $M_2$ را گوش کنند. حال برای دو نفر هر موسیقی دو حالت برای گوش کردن با هندزفری‌ها داریم (یا هر کدام به طور کامل هندزفری یک دستگاه را برمی‌دارند و یا از هر دستگاه یک گوشی هندزفری را برمی‌دارند). پس پاسخ برابر $\binom{4}{2} \times 2 \times 2 = 24$ است.

سوال ۲۴

دو نفر با نام‌های $A$ و $B$ را دوست گوییم، اگر هندزفری‌ای وجود داشته باشد که یک گوشی آن در اختیار $A$ و گوشی دیگر در اختیار $B$ باشد. دو نفر با نام‌های $A$ و $B$ را آشنا گوییم، اگر دنباله‌ی $\langle C_1, C_2, \ldots, C_k \rangle$ از افراد وجود داشته باشد که $k \ge 2$ و $C_1$ خود $A$ باشد، $C_1$ با $C_2$ دوست باشد، $C_2$ با $C_3$ دوست باشد و \ldots\ و $C_{k-1}$ با $C_k$ دوست باشد و $C_k$ خود $B$ باشد. واضح هست که دو دوست، آشنا نیز هستند.

فرض کنید $n=10$ است. پنج تا از دستگاه‌ها در حال پخش موسیقی $M_1$ و پنج تای دیگر در حال پخش موسیقی $M_2$ هستند. به حالتی از گوش کردن موسیقی‌ها سلطانی گوییم، اگر هیچ دو نفر غیر آشنایی، موسیقی یکسانی گوش نکنند. افراد به چند حالت سلطانی می‌توانند هندزفری‌ها را استفاده کرده و موسیقی‌ها را گوش کنند؟

  1. $10!$
  2. $2^9$
  3. $\frac{10!}{25}$
  4. $9!$
  5. $2^8 \times 5! \times 5!$

پاسخ

گزینه‌ی ۳ درست است.

$\binom{10}{5}$ حالت برای انتخاب پنج نفر موسیقی $M_1$ داریم. بقیه باید موسیقی $M_2$ را گوش کنند. پنج نفر هر موسیقی یک جایگشت دوری با هندزفری‌ها می‌سازند که $4!$ حالت دارد. پس پاسخ برابر $$\binom{10}{5} \times 4! \times 4! = \frac{10!}{25}$$ است.


ابزار صفحه