المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۱۷

سؤال ۱۷

منظور از یک زیر دنباله تعدادی عدد پشت سر هم از یک دنباله است. مثلاً (۲,۳,۴) زیر دنباله‌ی (۱,۲,۳,۴,۵) هست ولی (۱,۴,۵) زیر دنباله‌ی آن نیست. هم‌چنین یک زیر دنباله مضرب پنج است اگر جمع اعضای آن مضرب پنج باشد. مثلاً (۵) یا (۱,۲,۳,۴) زیر دنباله‌های مضرب ۵ از (۱,۲,۳,۴,۵) هستند ولی (۱,۲,۳) مضرب ۵ نیست. تعداد زیر دنباله‌های ناتهی مضرب ۵ دنباله‌ی (۲,۰,۰,۳,۰,۱,۳,۱,۱,۳,۸,۱,۱,۱,۱,۱) چه قدر است؟

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

پاسخ

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

اگر دنباله داده شده را به‌صورت $a_1,a_2,a_3,...,a_n$ تصور کنیم آن‌گاه دنباله $b,b_1,b_2,...,b_n$ را به شکل زیر تعریف می‌کنیم:

\[ \left\{ \begin{array}{l l} b_0=0 \\ b_i=a_1+a_2+...+a_i \end{array} \right. \]

بنابراین دنباله جدید به شکل زیر به‌دست خواهد آمد:

$$0,2,2,2,5,5,6,9,10,11,14,22,23,24,25,26,27$$

اگر $b_k$ و $b_l$ در تقسیم بر ۵ باقی‌مانده یکسان داشته باشند٬ آن‌گاه $b_k-b_l$ مضرب ۵ بوده و معلوم خواهد شد که زیر دنباله $a_{l+1},a_{l+2},...,a_k$ مضرب ۵ است. بنابراین کافی است زوج $b_i$هایی را پیدا کنیم که در تقسیم بر ۵ باقی‌مانده یکسانی دارند. $b_i$ها متناسب با باقی‌مانده بر ۵ به پنج دسته زیر افراز می‌شوند:

$0:0,5,5,10,25$

$1:6,11,26$

$2:2,2,2,22,27$

$3:23$

$4:9,14,24$

به ازای انتخاب هر دو عضو از یک دسته به یک زیر دنباله مضرب ۵ خواهیم رسید٬ بنابراین:

$$\binom{5}{2}+\binom{3}{2}+\binom{5}{2}+\binom{3}{2}=26$$


ابزار صفحه