Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

یک جایشگت نزولی از اعداد 1 تا n داریم. در هر گام دو عدد متمایز به صورت تصادفی انتخاب شده و به احتمال 12 جای آن‌ها عوض می‌شود. اگر پس از چند گام این جایگشت مرتّب شود (یعنی اعداد به ترتیب صعودی در جایگشت قرار بگیرند)، علیرضا می‌برد و در غیر این صورت سپهر برنده‌ی بازی است (تعداد گام‌ها محدودیتی ندارد). به چه احتمالی علیرضا برنده می‌شود؟

  1. 0
  2. 1n!
  3. 1
  4. 1n
  5. 12

پاسخ

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

‫به ازای یک جایگشت اولیه، یک دنباله از جابجایی‌ها که جایگشت را مرتب می‌کند در نظر بگیرید.

‫احتمال وقوع این دنباله‬ بیشتر از (1/N2×1/2)(N2) است. پس احتمال اینکه در یک N2 متوالی این جایگشت مرتّب نشود حداکثر برابر است با 1(1/N2×1/2)(N2) پس احتمال اینکه پس از t مرحله ی N2 تایی از جابجایی ها مرتب نشده باشد حداکثر برابر است با: (1(1/N2×1/2)(N2))t که با میل کردن t به بینهایت این مقدار نیز به صفر میل می‌کند. پس احتمال مرتب‌شدن جایگشت در نهایت برابر 1 است و علیرضا به احتمال 1 برنده می‌شود.


ابزار صفحه