زیرمجموعه‌ها

روش ساختاری: ابتدا مجموعه‌ی $\{1,2,…,100\}$ را به زیرمجموعه‌ی $\{3,4\}،\{1,2\}$،… و $\{99,100\}$ تقسیم می‌کنیم. اجتماع هر دو تا از این زیرمجموعه‌ها، یک زیرمجموعه‌ی ۴ تایی به ما می‌دهد که هیچ دوتایی از این زیرمجموعه‌ها با هم بیش از ۲ اشتراک ندارند. تعداد این زیرمجموعه‌ها، برابر با $\binom{50}{2}=1225$ است.

از طرف دیگر می‌توانیم دوتایی‌های $\{5,7\}،\{2,4\}،\{1,3\}$،… و $\{98,100\}$ را در نظر بگیریم که این دوتایی‌ها نیز به ما ۱۲۲۵ زیرمجموعه‌ی چهارتایی می‌دهد که ۲۵ تای آن‌ها با ۱۲۲۵ تای اولی مشترک است. همین طور اگر دوتایی‌های $\{6,7\}،\{5,8\}،\{2,3\}،\{1,4\}$،… و $\{97,98\}$ را در نظر بگیریم، ۱۲۲۵ زیرمجموعه‌ی دیگر به ما می‌دهد که ۲۵ تای آن تکراری است. به سادگی دیده می‌شود که هیچ دوتایی از مجموعه‌های این سه دسته بیش از دو اشتراک با هم ندارند. تعداد این زیرمجموعه‌ها برابر ۳۶۲۵ است که از ۱۳۷۵ بیش‌تر است.

روش وجودی: هر زیرمجموعه‌ی ۴ تایی که در نظر بگیریم، $4\times 96$ زیرمجموعه‌ی ۴ تایی دیگر وجود دارند که با آن ۳ اشتراک دارند. بنابراین اگر شروع به انتخاب زیرمجموعه‌های ۴ تایی کنیم، با انتخاب هر زیرمجموعه، $1+4\times96=385$ مجموعه از مجموعه‌هایی که می‌توانیم انتخاب کنیم حذف می‌شود. بنابراین در مجموع می‌توانیم حداقل $\frac{1}{385}\binom{100}{4}>1375$ زیرمجموعه‌ی ۴ تایی پیدا کنیم که دارای شرایط مسئله باشند.