تعداد زیرمجموعههای {$1,2,…,10$} که مجموع اعضای آن بر ۸ بخشپذیر چندتاست؟
پاسخ
گزینه (۴) درست است.
معلوم است که با جمع کردن تعدادی از اعداد {$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$ یعنی ۱۲۸ است یک و فقط یک زیر مجموعه به صورت مطلوب یافت خواهد شد.