المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۰:سوال ۵

سوال ۵

شنگدباو یک کوالای خوشحال دارد. او سه سکو دور یک دایره با فاصله‌های برابر قرار داده است که با شماره‌های ۱، ۲ و ۳ در جهت ساعت‌گرد شماره‌گذاری شده‌اند. در ابتدا کوالا روی سکوی ۱ قرار دارد. این کوالای خوشحال در هر دقیقه به احتمال $\frac{1}{2}$ به سکوی بعدی در جهت ساعت‌گرد می‌پرد، به احتمال $\frac{1}{4}$ ‌به سکوی بعدی در جهت پاد‌ساعت‌گرد می‌پرد و به احتمال $\frac{1}{4}$ سر جای خود می‌ماند. حالا شنگدباو با خود می‌اندیشد پس از ۱۳۹۹ دقیقه کوالا در کدام سکو به احتمال بیشتری می‌نشیند.

  1. احتمال نشستن روی سکوی ۲ از دو سکوی دیگر بیشتر است.
  2. احتمال نشستن روی سکوی ۱ از دو سکوی دیگر بیشتر است.
  3. احتمال نشستن روی سکوی ۳ از دو سکوی دیگر بیشتر است.
  4. احتمال نشستن در سکو‌های ۱ و ۳ برابر است و از سکوی ۲ بیشتر است.
  5. احتمال نشستن در سکو‌های ۱ و ۲ برابر است و از سکوی ۳ بیشتر است.

پاسخ

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

فرض کنید کوالا یک تاس عجیب دارد که هر بار عددی بین ۱ تا ۴ را با احتمال برابر نشان می‌دهد. او هر دقیقه این تاس را می‌اندازد و به اندازه‌ی عدد آن تاس، ساعتگرد روی سکوها حرکت می‌کند. این روش همان احتمال‌های مطرح شده در صورت سؤال را تولید می‌کند(؟). با این روش کوالا ۱۳۹۹ بار تاس می‌ریزد و نهایتا به اندازه‌ی مجموع اعداد تاس‌ها، ساعتگرد روی سکوها حرکت می‌کند. پس کافیست بین همه‌ی حالات مختلف تاس انداختن، ببینیم در بین مجموع اعداد تاس‌ها کدام باقی‌مانده‌ی بر ۳ بیشتر تولید می‌شود.

مسئله معادل می‌شود با اینکه بین همه‌ی اعداد ۱۳۹۹ رقمی با ارقام ۱ تا ۴، کدام باقی‌مانده‌ی ۳ بیشتر تولید شده است. حال برای عدد $n$، راست‌ترین رقمی که ۴ نیست را بگیرید. اگر این رقم را به ارقامی غیر از ۴ تغییر دهید، ۲عدد دیگر بدست می‌آید. این ۳ عدد را با هم در یک دسته بگذارید. با این روش همه‌ی اعداد جز عددی که همه‌ی ارقامش ۴ است دسته‌بندی می‌شوند. در هر دسته یکی بر ۳ بخش‌پذیر است، یکی باقی‌مانده‌ی ۱ دارد و دیگری باقی‌مانده‌ی ۲. پس پرتکرارترین باقی‌مانده، باقی‌مانده‌ی ۴۴۴۴…۴۴۴ بر ۳ است که برابر ۱ است. در نتیجه احتمال نشستن کوالا روی سکوی ۲ بیشتر از دو سکوی دیگر است.


ابزار صفحه