المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۲۴

۱۰ سکه دور دایره‌ای چیده شده‌اند که یک‌درمیان شیر (H) و خط (T) هستند. در هر مرحله می‌توانیم هر سه تا سکه پشت سر هم را که HTH یا THT باشند انتخاب کنیم و هر سه را برگردانیم. با تکرار این کار، حداکثر چه تعداد H می‌توانیم داشته باشیم؟

  1. ۵
  2. ۶
  3. ۷
  4. ۸
  5. ۹

پاسخ

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

اولا واضح است که تعداد $H$ها نمی‌تواند برابر ۱۰ باشد٬ زیرا آخرین تغییر هم شامل $H$ است و هم شامل $T$.

ثانیا اگر تصور کنیم که تعداد $H$ ها برابر ۹ باشد٬ مراحل انجام شده را از انتها به ابتدا مرتب می‌کنیم($H$ را با $\circ$ و $T$ را با $ \bullet$ نمایش می‌دهیم):

چون در هر مرحله سه‌تایی قابل تعویض منحصربه‌فرد می‌باشد٬ بنابراین نهایت کار مشخص است و هرگز سکه‌ها به صورت یک در میان $H$ و $T$ نخواهند شد.

و اما مراحل تولید ۸ تا $H$ به شکل زیر می‌باشد:


ابزار صفحه