المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۶

برای جایگشت $p$ از اعداد ۱ تا $n$، ‎$f(p)$‎ را برابر‎$\sum_{i=1}^n\left|p_i-i\right|$‎ تعریف می‌کنیم . میانگین ‎$f(p)$‎ برای کل جایگشت‌های ‎۷‎ تایی چند است؟

  1. ‎۰
  2. ۷
  3. ۱۴
  4. ۱۶
  5. ۲۱

پاسخ

گزینه (۴) درست است.

می‌دانیم تعدا کل جایگشت‌ها برابر $7!$ می‌باشد. در $\frac{1}{7}$ از جایگشت‌ها رقم اول ٬۱ در $\frac{1}{7}$ از آن‌ها رقم اول ٬۲… و بالاخره در $\frac{1}{7}$ ا جایگشت‌ها رقم اول ۷ می‌باشد که در این صورت ‎$\sum\left|p_i-i\right|$ بر رقم اول کل جایگشت‌ها $6!\times (0+1+2+...+6)$؛ یعنی $21\times 6!$ خواهد شد. این مجموع بر ارقام دوم٬ سوم٬ … و هفتم نیز به ترتیب برابر ۱۶٬۱۳٬۱۲٬۱۳٬۱۶ و ۲۱ می‌باشد٬ بنابراین:

$$\overline{x}=\frac{‎\sum\left|p_i-i\right|}{7!}=\frac{6! \times (21+16+13+12+13+16+21)}{7!}$$


ابزار صفحه