المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۳۲

سوال ۳۲

تعداد زیرمجموعه‌های لااقل ۲ عضوی مجموعه‌ی $\{1,2,...,20\}$ که مجموع هر دو عضو متمایز آن‌ها٬ از ۲۰ بزرگ‌تر باشد٬ چندتا است؟

  1. ۳۰۴۹
  2. ۳۰۷۰
  3. ۴۰۹۴
  4. ۴۰۹۵
  5. ۲۰۴۸

پاسخ

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

کوچک‌‌ترین عضو زیر مجموعه‌ی مطلوب را $i$ می‌نامیم که دو حالت پیش می‌آید:

  1. $1 \leq i \leq 9$‎. در این حالت هیچ یک از اعضای $i+2،i+1$،…،$20-i$ نمی‌توانند در آن زیر مجموعه باشند و اما هر یک از اعضای $20-i+2،20-i+1$،…،$20$ دو حالت در آن زیرمجموعه می‌توانند داشته باشند٬ عضو بودن در آن زیرمجموعه و یا عضو نبودن آن (حالتی که هیچ یک از آن اعضا عضو زیر مجموعه‌ي مورد نظر نباشند را نمی‌شماریم زیرا در این صورت زیر مجموعه‌ی مورد نظر فقط شامل $i$ بوده و یک عضوی است). بنابراین در این حالت تعداد زیرمجموعه‌های مورد نظر برابر $2^i-1$ می باشد.
  2. $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$$


ابزار صفحه