المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

سلطان می خواهد جایگشتی از اعداد $1$ تا $10$ بسازد. او در ابتدا عدد $1$ را می نویسد. سپس به ازای هر $i$ به ترتیب از $2$ تا $10$ عدد $i$ را به شکل زیر به جایگشت اضافه می کند:

فرض کنید جایگشت کنونی $(\pi _ 1,\pi _2,...,\pi_{i-1})$ باشد. سلطان عدد $i$ را به احتمال $\frac 1 {2^1}$ در ابتدای جایگشت، و به ازای هر $j$ به احتمال $\frac 1 {2^j}$ بین $\pi _{j-1}$ و $\pi _j$ و به احتمال $\frac 1 {2^{i-1}}$ در انتهای جایگشت آن را می نویسد.

در جایگشت نهایی به دو عدد ( نه لزوما متوالی ) وارون می گوییم، اگر عدد بزرگ‌تر قبل از عدد کوجک‌تر آمده باشد. امید ریاضی تعداد زوح های وارون را بیابید.

  1. $\binom 92 - \frac 1 {2^9}$
  2. $9$
  3. $\frac {\binom {10} 2} 2 + \frac 1 {2^{10}} $
  4. $\binom 92 + 1 - \frac 1 {2^9}$
  5. $\frac {\binom {10} 2} 2$

پاسخ


ابزار صفحه