Processing math: 84%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

پارمیس و نازلی هر کدام در خانه‌ای از یک جدول 9×9 قرار دارند. پارمیس در پایین‌ترین و چپ‌ترین خانه و نازلی در بالاترین و راست‌ترین خانه از جدول قرار دارد. هر روز صبح، پارمیس یک سکه می‌اندازد که با احتمالِ برابر، شیر یا خط می‌آید. اگر سکه شیر آمد، پارمیس از جایی که قرار دارد، یک خانه به‌سمت بالا می‌رود و نازلی نیز از جایی که قرار دارد، یک خانه به‌سمت پایین حرکت می‌کند. اگر سکه خط آمد، پارمیس یک خانه به‌سمت راست، و نازلی یک خانه به‌سمت چپ می‌رود. سپس، هر دوی آن‌ها در خانه‌ای از جدول که در آن قرار دارند، شب را صبح می‌کنند. این روند تا زمانی ادامه می‌یابد که پارمیس یا نازلی از جدول خارج شوند. احتمال این که نازلی و پارمیس شبی را با هم، در خانه‌ی یکسانی از جدول سپری کنند، چه‌قدر است؟

  1. 0
  2. 4901287
  3. 643532768
  4. 35128
  5. 63256

پاسخ

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

با کمی بررسی می‌توان دید که همواره خانه‌ای که نازلی و پارمیس در آن قرار دارند، نسبت به هم قرینه‌ی مرکزی است. پس، تنها حالتی که می‌توانند هم‌دیگر را در یک خانه ملاقات کنند، این است که هر دو در خانه‌ی مرکزی جدول شب را سپری کنند. بنابراین، برای حل سؤال کافیست تا احتمال اینکه پارمیس شبی را در خانه‌ی مرکزی سپری کند، محاسبه کنیم.

برای این کار، 8 حرکت ابتدایی را در نظر می‌گیریم. در این 8 حرکت، هر بار یا خط می‌آید و یا شیر، پس تعداد کل حالت‌های حرکت پارمیس در 8 روز اول برابر است با:

28=256.

تعداد حالاتی که پارمیس در 8 حرکت اول به خانه‌ی مرکزی برسد، برابر است با تعداد مسیرهایی در جدول که از خانه‌ی پایین چپ آغاز و به خانه‌ی مرکزی ختم می‌شوند. تعداد این مسیرها برابر است با:

\binom {8} {4} = 70.

در نتیجه، احتمال اینکه پارمیس و نازلی شبی را در خانه‌ی مرکزی صبح کنند، برابر است با:

\frac {70} {256} = \frac {35} {128}.


ابزار صفحه