سوال ۶
علی از طرف عموی برنامه‌نویسش یک دستورالعمل «آرایه‌ساز» و یک آرایه‌ی ۸ خانه‌ای هدیه گرفته است. این دستورالعمل به صورت زیر کار می‌کند:
- درون همه‌ی خانه‌های آرایه عدد ۰ را بنویس.
- مقدار $i$ را برابر با ۰ قرار بده.
- مقدار $i$ را $i + 1$ قرار بده.
- $i$ خانه‌ی متوالی در آرایه را به صورت تصادفی انتخاب کن. به اعداد درون همه‌ی این $i$ خانه یک واحد اضافه کن.
- اگر $i$ کوچکتر از ۸ است به مرحله‌ی ۳ بازگرد.
- پایان.
این دستورالعمل یک آرایه‌ی ۸ عضوی را به‌صورت تصادفی می‌سازد. از آن‌جا که علی این روزها به «جایگشت» علاقه‌مند شده است، فقط وقتی خوشحال می‌شود که دستورالعمل جایگشتی از اعداد ۱ تا ۸ خروجی بدهد. علی به چه احتمالی خوشحال می‌شود؟
- $\frac{2^7}{8!}$
- $\frac{1}{8}$
- $\frac{2^8}{8!}$
- $\frac{2^7}{7!}$
- $\frac{1}{2}$
پاسخ
گزینه (۱) درست است.
هر مرحله یک بازه از آرایه با عدد ۱ جمع بسته می‌شوند. هر یک از این بازه‌ها را با طولشان نام گذاری می‌کنیم.
بازه $x$ درون بازه‌ی $y$ هست اگر اجتماع‌خانه‌هایی که می‌پوشانند برابر با خانه‌های بازه $y$ باشد.
به استقرا می‌توان ثابت کرد اگر مطابق الگوریتم بازه‌های ۱ تا $n$ را با هم جمع کنیم و دنباله‌ی نهایی جایگشت باشد، به ازای هر جفت بازه، بازه‌ی کوچکتر درون بازه‌ی بزرگتر است(؟).
چون اضافه کردن بازه‌ها مستقل از هم انجام می‌شود می‌توان ترتیب اعمال بازه‌ها رو برعکس کرد. با توجه به اینکه هر بازه باید داخل بازه‌های بزرگتر از خود باشد، به ازای هر بازه با طول کمتر از ۸ تنها ۲ حالت می‌تواند به حالت معتبر ختم شود. پس تعداد حالت‌های معتبر $2^7$ است. تعداد کل حالات نیز $8!$ است. چون بازه به طول $i$ می‌تواند در $8-i+1$ حالت مختلف به آرایه اضافه شود.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
