سوال ۴

دنباله‌ی $n$تایی $a_1, a_2, \cdots a_n$ داده شده است به طوری که هر عضو این دنباله به صورت تصادفی از بین اعداد $0, 1, \cdots, n^6$ انتخاب شده است. مقدار $S_{i,j}$ را برابر جمع اعداد $a_i, a_{i+1}, \cdots, a_j$ قرار دهید. حال می‌خواهیم به جای هر $a_i$ یک مقدار نامنفی جدیدی قرار دهیم که:

• اوّلاً مقدار جدید حداکثر نصف مقدار قبلی باشد
• ثانیاً به ازای هر $i<j$ و $k<l$، که قبلاً داشتیم $S_{i,j} \leq S_{k,l}$، به ازای مقادیر جدید $a_i$ها نیز همین نامساوی را داشته باشیم.

در زیر می‌خواهیم به کمک شما روشی ارائه دهیم که به احتمال خوبی این کار را برای ما انجام می‌دهد.

1. ثابت کنید اگر همه‌ی $a_i$ها زوج باشند، حتماً این کار شدنی است.
2. اگر از هر $a_i$ که فرد است یک واحد کم کنیم به مقادیر جدیدی برای $a_i$ها می‌رسیم که همه‌ی آن‌ها زوج‌اند. اما ممکن است جهت بعضی از نامساوی‌های $S_{i,j} \leq S_{k,l}$ عوض شود. ثابت کنید به ازای هر $i,j,k,l$ احتمال عوض شدن جهت نامساوی $S_{i,j} \leq S_{k,l}$ حداکثر $2 \over n^5$ است.
3. با استفاده از قسمت دوم، ثابت کنید اگر از همه‌ی $a_i$های فرد یک واحد کم کنیم، احتمال اینکه جهت حتی یکی از نامساوی‌ها عوض شود کمتر از $2 \over n$ است. در نتیجه در این روش با احتمال حداقل $1 - {2 \over n}$ می‌توانیم بدون عوض شدن جهت نامساوی‌ها همه‌ی اعداد را زوج کنیم سپس با استفاده از قسمت اول به نتیجه‌ی مطلوب می‌رسیم.