سوال ۳۲
تعداد زیرمجموعههای لااقل ۲ عضوی مجموعهی $\{1,2,...,20\}$ که مجموع هر دو عضو متمایز آنها٬ از ۲۰ بزرگتر باشد٬ چندتا است؟
۳۰۴۹
۳۰۷۰
۴۰۹۴
۴۰۹۵
۲۰۴۸
پاسخ
گزینه (؟) درست است.
کوچکترین عضو زیر مجموعهی مطلوب را $i$ مینامیم که دو حالت پیش میآید:
$1 \leq i \leq 9$. در این حالت هیچ یک از اعضای $i+2،i+1$،…،$20-i$ نمیتوانند در آن زیر مجموعه باشند و اما هر یک از اعضای $20-i+2،20-i+1$،…،$20$ دو حالت در آن زیرمجموعه میتوانند داشته باشند٬ عضو بودن در آن زیرمجموعه و یا عضو نبودن آن (حالتی که هیچ یک از آن اعضا عضو زیر مجموعهي مورد نظر نباشند را نمیشماریم زیرا در این صورت زیر مجموعهی مورد نظر فقط شامل $i$ بوده و یک عضوی است). بنابراین در این حالت تعداد زیرمجموعههای مورد نظر برابر $2^i-1$ می باشد.
$1 \leq i \leq 19$. در این حالت همهی اعضا بزرگتر از $i$ دو حالت در آن زیر مجموعه میتوانند داشته باشند٬ عضو بودن در آن زیرمجموعه و یا عضو نبودن آن (حالتی که هیچ یک از آن اعضا عضو زیر مجموعهی مورد نظر نباشند را نمیشماریم). بنابراین در این حالت تعداد زیرمجموعههای مطلوب برابر $2^{20-i}-1$ خواهد شد.
با در نظر گرفتن دو حالت فوق تعداد کل زیرمجموعههای مطلوب به شکل زیر پیدا خواهد شد:
$$?=[(2^1-1)+(2^2-1)+…+(2^9-1)]+[(2^{10}-1)+(2^9-1)+…+(2^1-1)] \\ =2^{10}+2(2^1+2^2+…+2^9)-19=2^{10}+2(2^{10}-2)-19$$