المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

  1. $0$
  2. $\dfrac{1}{n!}$
  3. $1$
  4. $\dfrac{1}{n}$
  5. $\dfrac{1}{2}$

پاسخ

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

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

‫احتمال وقوع این دنباله‬ بیشتر از $$(1/N^2 \times 1/2) ^ {(N^2)}$$ است. پس احتمال اینکه در یک $$N^2$$ متوالی این جایگشت مرتّب نشود حداکثر برابر است با $$1 - (1/N^2 \times 1/2) ^ {(N^2)}$$ پس احتمال اینکه پس از t مرحله ی $$N^2$$ تایی از جابجایی ها مرتب نشده باشد حداکثر برابر است با: $$(1 - (1/N^2 \times 1/2) ^ {(N^2)}) ^ t$$ که با میل کردن $t$ به بینهایت این مقدار نیز به صفر میل می‌کند. پس احتمال مرتب‌شدن جایگشت در نهایت برابر 1 است و علیرضا به احتمال 1 برنده می‌شود.


ابزار صفحه