====== سوال ۳۲ ======


تعداد زیرمجموعه‌های لااقل ۲ عضوی مجموعه‌ی $\{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$$


</پاسخ>
  * [[سوال ۳۳|سوال بعد]]
  * [[سوال ۳۱|سوال قبل]]