المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

یک دنباله‌ی ۷ عنصری از اعداد ۱ و ۱- را «موفق» می‌گوییم اگر نتوان هیچ زیر دنباله ای از عناصر متوالی آن (شامل حداقل دو عنصر) را یافت که مجموع اعداد آن زیردنباله منفی بشود. به عنوان مثال دنباله‌ي <۱٫۱-۱٫۱٫۱٫۱٫-۱٫> موفق است ولی دنباله‌ي <۱٫۱٫۱٫۱-۱٫۱٫-۱٫> موفق نیست چرا که زیر دنباله‌ي شامل عناصر دوم تا چهارم (از سمت چپ) در آن مجموعی برابر ۱- دارد که منفی است.

تعداد دنباله های ۷ عنصره‌ي موفق چندتاست؟

  1. ۱۹
  2. ۱۳
  3. ۲۴
  4. ۲۱
  5. ۱۶

پاسخ

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

فاصله‌ی بین دو 1- حداقل باید دو باشد . یعنی دو 1- در نزدیک ترین حالت به شکل 1- 1 1 1- در کنار هم قرار دارد.حالات مختلف را می شماریم:

الف.در دنباله سه 1- داشته باشیم : تنها حالت 1- 1 1 1- 1 1 1- است.

ب.در دنباله دو 1- داشته باشیم :

  • فاصله ی دو 1-، دو باشد :

1 1 1 1- 1 1 1- و 1 1 1- 1 1 1- 1 و 1 1- 1 1 1- 1 1 و 1- 1 1 1- 1 1 1

  • فاصله ی دو 1-، سه باشد:

1 1 1- 1 1 1 1- و 1 1- 1 1 1 1- 1 و 1- 1 1 1 1- 1 1

  • فاصله ی دو 1- ، چهار باشد :

1- 1 1 1 1 1- 1 و 1 1- 1 1 1 1 1-

  • فاصله ی دو 1- ، پنج باشد :

1- 1 1 1 1 1 1-

ج. در دنباله یک 1- داشته باشیم : 1- در هر جای دنباله می تواند باشد پس 7 حالت داریم .

د. در دنباله 1- نداشته باشیم : تنها حالت 1 1 1 1 1 1 1 است.

پس در کل 19 حالت داریم .


ابزار صفحه