المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۶

مجموعه‌ی $S$ «دوستانه» است اگر برای هر $xϵS$ حداقل یکی از $x+1$ و $x-1$ هم در $S$ باشد. مثلاً {۱,۲,۴۹۹,۵۰۰} دوستانه است. چه تعداد مجموعه‌ی دوستانه با ۵ عضو از اعداد ۱ تا ۱۰۰ داریم؟

  1. ۴۶۵۶
  2. ۹۲۰۸
  3. ۹۲۱۶
  4. ۱۰۰۰۰
  5. ۱۸۳۳۶

پاسخ

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

یکی از سه حالت زیر پیش می‌آید:

۱)هر پنج عضو متوالی باشند که تعداد این مجموعه‌ها برابر ۹۶ به‌دست می‌آید.

۲) دو عضو کوچک آن متوالی و نیز سه عضو بزرگ آن نیز متوالی باشند ولی عضو دوم آن با عضو سومش متوالی نباشند که دراین صورت مجموعه‌ای از ۱ تا ۱۰۰ به شکل زیر افراز خواهد شد:

$$\underbrace{ ........ }_{x} \times \times \underbrace{ ........ }_{y} \times \times \times \underbrace{ ........ }_{z}$$

تعداد افراز‌های فوق با تعداد جواب‌های معادله $x+y+z=95$ با شرایط $y \geq 1،z \geq 0$ و $x \geq 0$ برابر است که تعداد جواب‌های چنین معادله‌ای برابر $ \binom{96}{2}$ یعنی ۴۵۶۰ می‌باشد.

۳) سه عضو کوچک آن متوالی ونیز دو عضو بزرگ آن نیز متوالی باشند ولی عضو سوم آن با عضو چهارمش متوالی نباشد که در این صورت نیز تعداد جواب‌ها برابر $ \binom{96}{2}$ یا ۴۵۶۰ به دست می‌آید.


ابزار صفحه