المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۵:سوال ۱۱

سوال ۱۱

مجموعه‌ی $S=\lbrace1,2,...,7\rbrace$ داده شده است. دو تابع داریم:

$f(A)$ که مکمل زیرمجموعه‌ی $A$ و $g(A,B)$ که اشتراک $A$ و $B$ را می‌دهد.

یک کیسه داریم که همه‌ی زیرمجموعه‌های $S$ را درون آن ریخته‌ایم. می‌خواهیم تعدادی زیرمجموعه از کیسه بیرون آوریم تا با استفاده از آن‌ها و توابع بتوان تمام زیرمجموعه‌های $S$ را تولید کرد (برای تولید زیرمجموعه‌ها می‌توان از هر زیرمجموعه به تعداد دل‌خواه استفاده کرد).

فرض کنید $\lbrace1,2,5,6\rbrace$, $\lbrace2,5,3\rbrace$ و $\lbrace5 , 6\rbrace$ را از کیسه بیرون آورده‌ایم. حداقل چند زیرمجموعه‌ی دیگر از کیسه بیرون بکشیم تا مطمئن باشیم با آن‌ها می‌توان مسئله را حل کرد؟

  1. ۳
  2. ۶۲
  3. ۶۷
  4. ۱
  5. ۶۴

پاسخ

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

از اشتراک هر ۳ مجموعه به مجموعه‌ی $\lbrace 5 \rbrace$ می‌رسیم. از تفریق این مجموعه و مجموعه‌ی $\lbrace 5 , 6 \rbrace$ به $\lbrace 6 \rbrace$ می‌رسیم. از تفریق دو مجموعه‌ی اول به دو مجموعه‌ی $\lbrace 2 , 3 \rbrace$ , $\lbrace 1 , 2 \rbrace$ می‌رسیم که ما را به مجموعه‌های ۱ تا ۳ می‌رساند. نکته اینجاست که در هر مجموعه‌ای که در نظر بگیریم یا ۴ و ۷ هر دو نیامده‌اند یا هر دو آمده‌اند. بنابراین با هیچ تابعی بر حسب مجموعه‌های فعلی نمی‌توان به مجموعه‌هایی رسید که یکی از این دو را داشته باشد. در ضمن کافی است مجموعه‌ای داشته باشیم شامل یکی از این دو. با استفاده از عملیات تفریق و مجموعه‌های تک عضوی بدست آمده ابتدا به مجموعه‌ی تک عضوی ۴ یا ۷ می‌رسیم… سپس با استفاده از این توابع به هر زیرمجموعه‌ای خواستیم می‌رسیم. بنابراین این کار را تا زمانی می‌توان ادامه داد که به مجموعه‌ای برسیم که یکی از ۴ یا ۷ را داشته باشد. تعداد مجموعه‌هایی که یا هردوی ۴ و ۷ را دارند یا هیچکدام برابر با $2^6=64$ می‌باشد. بنابراین کافی است ۶۵ عضو داشته باشیم تا مساله حل شود. از آنجا که در ابتدا ۳ عضو داریم، ۶۲ جواب خواهد بود.


ابزار صفحه