المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۲

فرض کنید ‎$S\subseteq\{1,2,\ldots,8\}$‎ باشد. برای یک زیر مجموعه‌ی ‎$S$ از اعداد طبیعی تعریف می‌کنیم ‎$S^*=\{x+1|x\in S\}$‎. اگر تعداد ‎$S$،‎هایی که ‎$S\cup S^*=\{1,2,\ldots,9\}$‎ برابر ‎$n$‎ باشد، باقی‌مانده‌ی ‎$n$‎ بر ‎۵‎ کدام است؟

  1. ۰
  2. ۱
  3. ۲
  4. ۳
  5. ۴

پاسخ

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

$S$ باید هر دو عضو ۱ و ۸ را داشته باشد. از بین اعداد ۶٬۵٬۴٬۳٬۲ و ۷ تعدادی می‌توانند در $S$ نباشند٬ اگر این تعداد برابر ۰ باشد به $\binom{6}{0}$؛یعنی ۱ طریق ممکن است. اگر این تعداد بربر ۱ باشد به $\binom{6}{1}$؛ یعنی ۶ طریق ممکن است. اگر تعداد مورد نظر ۲ باشد به $\binom{6}{0}-5$؛ یعنی ۱۰ طریق ممکن است و بالاخره اگر تعداد اشاره شده بربر ۳ باشد به ۴ طریق ممکن است. یاد‌آوری می‌شود که از هر دو عضو متوالی حداقل یکی در $S$ موجود است. بنابراین تعداد کل حالات برابر ۲۱ می‌باشد.


ابزار صفحه