سوال ۱۱
دو مجموعه‌ی ناتهی $A$ و $B$ نسبت به هم اول‌اند اگر و تنها اگر هر عضو مجموعه‌ی $A$ نسبت به هر عضو مجموعه‌ی $B$ اول باشد (دو عدد نسبت به هم اول‌اند اگر و تنها اگر ب.م.م شان یک باشد). فرشید و فرشاد هر کدام یک زیرمجموعه‌ی ناتهی از $\{ 1, 2, ..., 9 \}$ انتخاب می‌کنند. احتمال این که مجموعه‌های فرشید و فرشاد نسبت به هم اول باشند چقدر است؟
- $\frac{723}{37303}$
- $\frac{5060}{1+255 \times 2^{10}}$
- $\frac{5061}{255 \times 2^{10}}$
- $\frac{2530}{255 \times 2^9}$
- $\frac{6084}{1+255 \times 2^{10}}$
پاسخ
گزینه (۱) درست است.
عدد ۱ می‌تواند در هر دو مجموعه باشد (۴ حالت). هر کدام از اعداد ۵ و ۷ می‌توانند حداکثر در یک مجموعه باشند (هر کدام ۳ حالت دارند).
اعداد ۲ و ۴ و ۸ حداکثر در یک مجموعه می‌توانند عضو باشند. در نتیجه ۱۵ حالت دارند.
اعداد ۳ و ۹ حداکثر در یک مجموعه می‌توانند عضو باشند. در نتیجه ۷ حالت دارند.
عدد ۶ تنها در حالتی می‌تواند در مجموعه‌ای عضو باشد که توان‌های ۲ و ۳ در دو مجموعه‌ی مختلف نباشند (در ۴۲ حالت در دو مجموعه‌ی مختلف هستند). در یک حالت (حالتی که توان‌های ۲ و ۳ عضو نباشند) نیز ۳ انتخاب برای عدد ۶ داریم.
در نتیجه برای انتخاب مضارب ۲ و ۳، $42 + 2 \times 62 + 1 \times 3 = 169$ روش وجود دارد.
در نتیجه مجموعا تعداد حالات ممکن ۶۰۸۴ می‌شود. ولی حالاتی که یکی از این مجموعه‌ها یا هر دو تهی باشند را باید حذف کنیم که تعداد آن‌ها $511 + 511 + 1= 1023$ تاست. در نتیجه ۵۰۶۱ حالت مختلف داریم که پس از تقسیم کردن بر کل حالات و ساده‌سازی به جواب $\frac{723}{37303}$ می‌رسیم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
