Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۸

تعداد زیرمجموعه‌های {1,2,,10} که مجموع اعضای آن بر ۸ بخش‌پذیر چندتاست؟

  1. ۱۲۵
  2. ۱۲۶
  3. ۱۲۷
  4. ۱۲۸
  5. ۱۲۹

پاسخ

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

معلوم است که با جمع کردن تعدادی از اعداد {4,2,1} همه اعداد از ۱ تا ۷ را به شکل زیر می‌توان تولید کرد:

1:1

2:2

3:1+2

4:4

5:1+4

6:2+4

7:1+2+4

حال باید توجه کرد که اگر زیرمجموعه دلخواهی از {3,5,6,7,8,9,10}A= را در نظر بگیریم٬ بستگی به این که مجموع اعضای آن زیرمجموعه در تقسیم بر ۸ چه باقی‌مانده‌ای داشته باشد٬ می‌توان زیرمجموعه‌ای از مجموعه {4,2,1} به آن اضافه کرد تا حاصل بر ۸ بخش‌پذیر است٬ آن‌گاه به ازای هر زیر مجموعه دلخواهی از مجموعه A که تعداد آن‌ها 27 یعنی ۱۲۸ است یک و فقط یک زیر مجموعه به صورت مطلوب یافت خواهد شد.


ابزار صفحه