Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۱

دو مجموعه‌ی ناتهی A و B نسبت به هم اول‌اند اگر و تنها اگر هر عضو مجموعه‌ی A نسبت به هر عضو مجموعه‌ی B اول باشد (دو عدد نسبت به هم اول‌اند اگر و تنها اگر ب.م.م شان یک باشد). فرشید و فرشاد هر کدام یک زیرمجموعه‌ی ناتهی از {1,2,...,9} انتخاب می‌کنند. احتمال این که مجموعه‌های فرشید و فرشاد نسبت به هم اول باشند چقدر است؟

  1. 72337303
  2. 50601+255×210
  3. 5061255×210
  4. 2530255×29
  5. 60841+255×210

پاسخ

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

عدد ۱ می‌تواند در هر دو مجموعه باشد (۴ حالت). هر کدام از اعداد ۵ و ۷ می‌توانند حداکثر در یک مجموعه باشند (هر کدام ۳ حالت دارند).

اعداد ۲ و ۴ و ۸ حداکثر در یک مجموعه می‌توانند عضو باشند. در نتیجه ۱۵ حالت دارند.

اعداد ۳ و ۹ حداکثر در یک مجموعه می‌توانند عضو باشند. در نتیجه ۷ حالت دارند.

عدد ۶ تنها در حالتی می‌تواند در مجموعه‌ای عضو باشد که توان‌های ۲ و ۳ در دو مجموعه‌ی مختلف نباشند (در ۴۲ حالت در دو مجموعه‌ی مختلف هستند). در یک حالت (حالتی که توان‌های ۲ و ۳ عضو نباشند) نیز ۳ انتخاب برای عدد ۶ داریم.

در نتیجه برای انتخاب مضارب ۲ و ۳، 42+2×62+1×3=169 روش وجود دارد.

در نتیجه مجموعا تعداد حالات ممکن ۶۰۸۴ می‌شود. ولی حالاتی که یکی از این مجموعه‌ها یا هر دو تهی باشند را باید حذف کنیم که تعداد آن‌ها 511+511+1=1023 تاست. در نتیجه ۵۰۶۱ حالت مختلف داریم که پس از تقسیم کردن بر کل حالات و ساده‌سازی به جواب 72337303 می‌رسیم.


ابزار صفحه