المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۸:سوال ۴

سوال ۴

۱۰ عدد متمایز در اختیار داریم. یک بار این اعداد را به صورت صعودی مرتب می‌کنیم تا دنباله‌ی $\langle a_1, \ldots, a_{10} \rangle$ به دست آید. بار دیگر اعداد را به صورت نزولی مرتب می‌کنیم تا دنباله‌ی $\langle b_1, \ldots, b_{10} \rangle$ ساخته شود. برای هر $1 \le i \le 10$ فرض کنید $A_i = \{a_1, \ldots, a_i\}$ و $B_i = \{b_1, \ldots, b_i \}$ باشد. در بین ۱۰۰ مجموعه به فرم $A_i \cup B_j$ که $1 \le i,j \le 10$ چند مجموعه‌ی متمایز وجود دارد؟

  1. ۳۶
  2. ۳۷
  3. ۴۵
  4. ۴۶
  5. ۵۵

پاسخ

گزینه‌ی ۲ درست است.

در حالاتی که $i \ge j - 1$ است، $A_i \cup B_j$ شامل تمام اعداد می‌شود. در بقیه‌ی حالات مجموعه‌های متمایز ساخته می‌شود که $\binom{10}{2}-9$ حالت (برای انتخاب $i$ و $j$) دارند. پس پاسخ برابر $1 + \binom{10}{2}-9 = 37$ است.


ابزار صفحه