المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

به چند طریق می توان $k$ مهره از میان $n$ مهره ای که در یک ردیف چیده شده اند انتخاب کرد به طوری که فاصله‌ی اولین و آخرین مهره‌ی انتخاب شده حداکثر $۱+k$ باشد. فرض کنید $n$ و $k$ اعداد صحیح بزرگتر از ۲ هستند و $k+۱ \le n$ . دقت کنید که فاصله‌ي دو مهره‌ي کنار هم ۱ است.

  1. $۱+(n-k)(\frac{k^۲+k}{۲})-\frac{k^۲+k}{۲}$
  2. $۱+(n-k)(\frac{k^۲-k}{۲})-\frac{k^۲-k}{۲}$
  3. $۱+(n+k)(\frac{k^۲-k}{۲})-\frac{k^۲-k}{۲}$
  4. $۱+(n-k)(\frac{k^۲+k}{۲})-\frac{k^۲-k}{۲}$
  5. $۱+(n-k)(\frac{k^۲-k}{۲})-\frac{k^۲+k}{۲}$

پاسخ

گزینه‌ی «۴» درست است.

این سوال را هم با حالت بندی حل می‌کنیم :

  • فاصله ی دو مهره اول و آخر برابر با $k+1$ باشد : در این حالت بین دو مهره ی اول و آخر $k$ مهره وجود دارد. از میان این k مهره باید k-2 مهره را انتخاب کنیم . از طرفی انتخاب دو مهره ی اول و آخر که با هم $k+1$ فاصله دارند $n-k-1$ حالت دارد . پس تعداد حالات برابر خواهد بود با:$\binom{2}{k}×(n-k-1)$ .
  • فاصله ی دو مهره ی اول و آخر برابر با $k$ باشد : مثل حالت قبل عمل می‌کنیم . در این صورت تعداد حالات برابرست با : . $\binom{k-1}{1}×(n-k)$
  • فاصله ی دو مهره ی اول و آخر برابر با $1-k$ باشد: و باز هم مثل حالت قبل : . $\binom{k-2}{0}×(n-k+1)$

با جمع عبارات فوق تعداد کل حالات برابر $1+(n-k)×\frac{k+k^2}{2}-\frac{k^2-k}{2}$خواهد بود .


ابزار صفحه