المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوال ۸

سوال ۸

خط یک مترو اصفهان دارای ۱۱ ایستگاه با شماره‌های ۰، ۱، $\ldots$ و ۱۰ است. مترو از ایستگاه ۰ شروع کرده و در ایستگاه ۱۰ کار خود را تمام می‌کند. در یک روز خلوت زمستانی، مترو بدون مسافر شروع به حرکت کرده است. در هر یک از ایستگاه‌های ۰، ۱، $\ldots$ و ۹ دقیقن یک مسافر جدید وارد مترو می‌شود. پس از رسیدن به هر ایستگاه (به جز ایستگاه پایانی)، هر نفر مستقل از بقیه به احتمال $\frac{1}{2}$ پیاده می‌شود. توجه کنید هیچ کس در همان ایستگاهی که سوار شده، پیاده نمی‌شود! امید ریاضی تعداد کسانی که به ایستگاه پایانی (۱۰) می‌رسند، چیست؟

  1. ۴
  2. ۲
  3. $\frac{511}{256}$
  4. $\frac{1023}{512}$
  5. $\frac{9}{2}$

پاسخ

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

این مسئله نیاز به اطّلاعاتی در مورد متغیرهای تصادفی و امید ریاضی دارد. در صورتی که با این مفاهیم آشنا نیستید، قبل از خواندن راه حل، آن‌ها را مطالعه کنید (البته مسئله راه حل بدون استفده از اطّلاعات خاص هم دارد، امّا طولانی‌تر است).

به ازای هر فرد $i$ (فردی که از ایستگاه $i$ ام وارد می‌شود)، متغیّر تصادفی $I_i$ را تعریف می‌کنیم که برابر ۱ است، اگر فرد $i$ به ایستگاه پایانی برسد و در غیر این صورت برابر ۰ است. امید ریاضی $I_i$ برابر احتمال رسیدن فرد $i$ به ایستگاه پایانی یا همان $\frac{1}{2^{9-i}}$ می‌باشد. امید ریاضی جمع چند متغیر تصادفی برابر با جمع امید ریاضی تک تک آن‌هاست؛ پس امید ریاضی خواسته شده برابر است با: $$E(X) = E(\sum I_i) = \sum E(I_i) = \sum_{i=0}^9 \frac{1}{2^{9-i}} = 2 - \frac{1}{2^9} = \frac{1023}{512}$$


ابزار صفحه