المپدیا

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

ابزار کاربر

ابزار سایت


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

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۸:سوالات_۲۳_و_۲۴ [2018/12/20 13:45] (فعلی)
Hamidreza seydi ایجاد شد
خط 1: خط 1:
 +====== سوالات ۲۳ و ۲۴ ======
 +
 +
 +
 +$n$
 +دستگاه پخش کننده‌ی موسیقی یکسان و $n$ هندزفری یکسان داریم. به هر کدام از دستگاه‌ها یک هندزفری وصل کرده‌ایم. هر هندزفری نیز دو گوشی دارد که یکی مخصوص گوش راست و یکی مخصوص گوش چپ است.
 +
 +$n$
 + ​نفر در یک گروه هستند و می‌خواهند از طریق این دستگاه‌ها و هندزفری‌ها موسیقی گوش کنند. هر کس می‌تواند یک گوشی‌ چپ و یک گوشی راست برداشته و آهنگ گوش کند. دو گوشی‌ای که یک فرد برمی‌دارد می‌توانند از یک هندزفری نباشند، اما باید آهنگ یکسانی را پخش کنند.
 +
 +در انتها تأکید می‌کنیم دستگاه‌های پخش‌ کننده و هندزفری‌ها را یکسان در نظر بگیرید.
 +
 +
 +
 +
 +====== سوال ۲۳ ======
 +
 +
 +
 +
 +فرض کنید
 +$n=4$
 +است. دو تا از دستگاه‌ها در حال پخش موسیقی
 +$M_1$
 +و دو تای دیگر در حال پخش موسیقی
 +$M_2$
 +هستند. افراد به چند طریق می‌توانند هندزفری‌ها را استفاده کرده و موسیقی‌ها را گوش کنند؟
 +
 +
 +  - ۱۲
 +  - ۲۴
 +  - ۴۸
 +  - ۱۶
 +  - ۱۸
 +
 +
 +
 +
 +
 +
 +
 +<​پاسخ>​
 +گزینه‌ی ۲ درست است.
 +
 +
 +
 +
 +انتخاب دو نفری که در حال گوش کردن به موسیقی $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$
 +هستند. به حالتی از گوش کردن موسیقی‌ها
 +**سلطانی**
 +گوییم، اگر هیچ دو نفر غیر آشنایی، موسیقی یکسانی گوش نکنند.
 +افراد به چند حالت سلطانی می‌توانند هندزفری‌ها را استفاده کرده و موسیقی‌ها را گوش کنند؟
 +
 +
 +
 +  - $10!$
 +  - $2^9$
 +  - $\frac{10!}{25}$
 +  - $9!$
 +  - $2^8 \times 5! \times 5!$
 +
 +
 +
 +
 +<​پاسخ>​
 +
 +
 +گزینه‌ی ۳ درست است.
 +
 +
 +
 +$\binom{10}{5}$
 +حالت برای
 +انتخاب پنج نفر موسیقی $M_1$ داریم. بقیه باید موسیقی $M_2$ را گوش کنند. پنج نفر هر موسیقی یک جایگشت دوری با هندزفری‌ها می‌سازند که 
 +$4!$
 +حالت دارد. پس پاسخ برابر
 +$$\binom{10}{5} \times 4! \times 4! = \frac{10!}{25}$$
 +است.
 +
 +
 +
 +</​پاسخ>​
 +
 +  * [[سوال ۲۲|سوال قبل]]
 +  * [[سوالات ۲۵ تا ۲۷|سوال بعد]]
 +
  

ابزار صفحه