سوال ۱۳
تعدادی از دانشآموزان یک مدرسه در اردوی یک هفته‌ای شرکت کردند. در هر روز ۳ نفر از دانشآموزان مسئولیت تهیه‌ی غذا را بر عهده داشتند. پس از پایان اردو معلوم شد که هیچ دو نفری از دانشآموزان بیش از یک بار با هم مسئول تهیه‌ی غذا نبوده‌اند. اگر $n$ تعداد دانشآموزان شرکت‌کننده در اردو باشد٬ آنگاه:
- $n=21$
- $n=7$
- $n \geq 7$
- $n < 9$
- $n \geq 9$
پاسخ
گزینه (۳) درست است.
مسئله درست کردن هفت مجموعه‌ی سه عضوی از اشیا $...،a_2،a_1$ و $a_n$، می‌باشد به طوری که هیچ دو مجموعه‌ای بیش زا یک عضو مشترک نداشته باشند. حداقل $n$ می‌تواند ۷ باشد٬ زیرا اگر $n$ برابر با ۶ باشد از شش عضو متمایز یکی از آنان حداقل در ۴ مجموعه تکرار شده است(زیرا اگر چنین نباشد حداکثر عضوها $6\times3$ یعنی ۱۸ عضو خواهد بود در صورتی که ۷ مجموعه روی هم ۲۱ عضو دارند.) این ۴ مجموعه را $A_3،A_2،A_1$ و $A_4$ و عضو مشترک را $a_1$ در نظر می‌گیریم. اگر این چهار مجموعه علاوه بر $a_1$ به ترتیب شامل $a_5،a_4،a_2$ باشند چون در $a_1$ مشترک هستند پس هیچ دو مجموعه‌ای از این ۴ مجموعه غیر از $a_1$ عضو مشترک دیگری نباید داشته باشند در صورتی که تنها عضو باقی‌مانده $a_6$ می‌باشد و ناچارا عضوهای سوم سه مجموعه از ۴ مجموعه عضوهای تکراری خواهند پذیرفت که تناقض است.
ثابت می‌کنیم اگر $a=7$ باشد این کار عملی است. نمونه‌ای از مجموعه‌های مطلوب عبارت‌اند از:
$A_1=\{a_1,a_2,a_3\} \quad\quad\quad\quad\quad A_2=\{a_1,a_4,a_5\} \quad\quad\quad\quad\quad A_3=\{a_1,a_6,a_7\} \\ A_4=\{a_2,a_4,a_6\} \quad\quad\quad\quad\quad A_5=\{a_2,a_5,a_7\} \quad\quad\quad\quad\quad A_6=\{a_3,a_4,a_7\} \\ A_7=\{a_3,a_5,a_6\}$
پس $n \geq 7$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
