پرسش سختی نیست تنها باید دست به کار شوید. اما پیش از پاسخ‌دادن یک گله از طراح پرسش دارم که صورت پرسش را کمی گنگ نوشته‌است. اگر تنها یک واژه به پرسش بیفزاید خواننده زمانش روی کشف معنای جمله‌ٔ مبهم ایشان تلف نمی‌شود و در واقع تکیه بر حدس از معنای جملات طراح آزمون منصف بودن نتیجهٔ آزمون را زیر پرسش می‌برد!
متن درست پرسش: بیشترین تعداد زیرمجموعه از \{a,b,c,d,e,f\} که دو به دو دست کم در دو عضو مشترک باشند چه مقدار است؟
(به نظر من واژهٔ «بیشترین» بسیار مهم است و گر نه از نظر منطقی پاسخ پرسش یکتا نخواهد گردید!)
پاسخ:
نخست ذهن من به پوشش زیرمجموعه‌ها رفت شما اگر زیرمجموعهٔ شش عضوی را بردارید هیچ‌زمانی ضرر در این مسأله نمی‌کنید چون با همهٔ مجموعه‌ها اشتراکش خودشان می‌شود. اگر زیرمجموعه‌های پنج‌عضوی را نیز به آن بیفزایید اشتراک هر دو زیرمجموعهٔ پنج عضوی از یک مجموعهٔ شش عضوی حداکثر چقدر کوچک می‌تواند باشد؟ هر یک تنها یک عضو از کل مجموعه را ندارند و در بدشانس‌ترین حالت این دو عضو متفاوت باشند آنگاه اشتراکشان هنوز چهرا عضو را تضمین شده دارد که بیشتر از دو عضو است. اکنون بیاییم چهارعضوی‌ها را نیز بیفزاییم. یک چهار عضوی و یک پنج‌عضوی در بدترین حالت اشتراکشان سه عضوی خواهد بود (با همان روش استدلالی که برای اشتراک دو تا پنج عضوی حرف زدیم)، دو تا پچهارعضوی نیز در بدترین حالت اشتراکشان دو عضو دارد. پس تا اینجا همهٔ ۶ و ۵ و ۴ عضوی‌ها هیچ مشکلی برایمان ندارند ولی اگر یک ۳ عضوی برداریم، چون همهٔ چهارعضوی‌ها را قرار داده‌ایم و می‌توان چهارعضوی‌ای یافت که با این سه‌عضوی اشتراکش یک عضو شود پس دیگر باید روندمان را متوقف کنیم. پس تا اینجا یک گردایه برداشتیم که دو به دو اشتراکشان بیشتر یا مساوی ۲ عضو داشت. تعداد زیرمجموعه‌های داخل این گردایه برابر است با؛
\binom{6}{6}+\binom{6}{5}+\binom{6}{4}=1+6+15=22
مطمئنا مجموعهٔ تهی و زیرمجموعه‌های تک‌عضوی را در گردایه‌مان نمی‌توانیم داشته باشیم و گرنه حداکثر یک مجموعه در گردایه حق دارد قرار بگیرد که دو به دو اعضای گردایه در دو عضو مشترک باشند (در واقع بنا به انتفای مقدم اگر تعداد زیرمجموعه‌هایی که برداشته‌ایم کمتر از دو باشد فرض شرط برقرار نیست و نیازی به بررسی برقراری حکم شرط نداریم و شرط به گونهٔ بدیهی برقرار می‌شود).
پس تا اینجا یک عدد ممکن است.
برای اینکه گردایه‌ای با بیش از یک عضو داشته باشیم که شرط برایش برقرار باشد باید تهی و تک‌عضوی‌ها را فراموش کنیم. نخستین انتخاب پس از فکر کردن به تهی و تک‌عضوی، دوعضوی‌ها هستند. پس بیایید یک دوعضوی برداریم. اما چون برای هر دو زیرمجموعهٔ انتخاب شده باید اشتراکشان دست کم دو عضو داشته باشد و این مجموعه را نیز برداشته‌ایم پس باید همهٔ زیرمجموعه‌های انتخاب‌شدهٔ دیگر نیز دقیقا دو عضو این زیرمجموعه را داشته باشند و در مورد داشتن ۴ عضو دیگر فعلا چیزی نمی‌دانیم پس اگر گردایه‌مان حتی یک زیرمجموعهٔ دو عضوی داشته باشد (که به آسانی می‌توانید ببینید به خاطر شرط نمی‌شود هیچ دو عضوی دیگر برداریم) در بهترین حالت به تعداد زیرمجموعه‌هایی که دو عضو ثابت را دارند عضو خواهد داشت، در این مسأله یعنی؛
\binom{2}{2}\times 2^{6-2}=1\times 16=16
دقت کنید که این کران دقیق و تیز نیست و ممکن است کران از ۱۶ هم پائین‌تر باشد ولی تا همین‌جا که آمدیم باید متوجه شوید که نیاز به ادمه و دقیق کردن کران ندارم زیرا که پیش‌تر یک گردایه با ۲۲ عضو داشتیم پس این کران هر چه باشد به خوبی ۲۲ نمی‌شود.
حالتی که هیچ زیرمجموعهٔ دو یا کمتر عضوی برنداشته‌ایم و یک سه عضوی برداشته‌ایم. در این حالت باید هر زیرمجموعهٔ دیگری که برمی‌داریم دو تا از این سه عضو را حتما داشته باشد و از سه عضو دیگر هر چه می‌خواهد بردارد اما به خاطر اینکه دو عضوی و کمتر نباید داشته باشیم تهی را باید از کل حالت‌های انتخاب یک زیرمجموعه از این سه عضو کم کنیم پس در این حالت در بهترین حالت بیشترین تعداد زیرمجموعه که می‌توانیم برگزینیم برابر خواهد بود با:
\binom{3}{2}\times (2^{6-3}-1)=3\times 7=21
اینجا نیز نیاز به ادامه و دقیق کردن کرانمان نداریم چون هر چه باشد کوچکتر یا مساوی ۲۱ خواهد بود و هم‌اکنون گردایهٔ ۲۲ عضوی به چشم دیده‌ایم و نیاز به سختی برای یافتن کران این حالت که ممکن است کمتر از ۲۱ شود نداریم.
اکنون حالتی که هیچ مجموعهٔ با کمتر از ۳ عضو برنداشته‌ایم. اما این حالت دقیقا زیرگردایه‌ای از گردایهٔ نخستینمان است و در بهترین حالت همهٔ زیرمجموعه‌های با بیشتر از سه عضو را می‌تواند داشته باشد که ثابت کردیم این امکان وجود دارد و تعدادشان ۲۲ است.
پس پاسخ ۲۲ است.
گزینهٔ جیم.
