Processing math: 93%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۱۷

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

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

پاسخ

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

اگر دنباله داده شده را به‌صورت a1,a2,a3,...,an تصور کنیم آن‌گاه دنباله b,b1,b2,...,bn را به شکل زیر تعریف می‌کنیم:

{b0=0bi=a1+a2+...+ai

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

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

اگر bk و bl در تقسیم بر ۵ باقی‌مانده یکسان داشته باشند٬ آن‌گاه bkbl مضرب ۵ بوده و معلوم خواهد شد که زیر دنباله al+1,al+2,...,ak مضرب ۵ است. بنابراین کافی است زوج biهایی را پیدا کنیم که در تقسیم بر ۵ باقی‌مانده یکسانی دارند. biها متناسب با باقی‌مانده بر ۵ به پنج دسته زیر افراز می‌شوند:

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


ابزار صفحه