المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۸

تعداد زیرمجموعه‌های {$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$ که تعداد آن‌ها $2^7$ یعنی ۱۲۸ است یک و فقط یک زیر مجموعه به صورت مطلوب یافت خواهد شد.


ابزار صفحه