====== سوال ۴ ======

دنباله‌ی ‎$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$‎ها نیز همین نامساوی را داشته باشیم. 

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

  - ثابت کنید اگر همه‌ی ‎$a_i$‎ها زوج باشند، حتماً این کار شدنی است. 
  - اگر از هر ‎$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$‎ است. 
  - با استفاده از قسمت دوم، ثابت کنید اگر از همه‌ی ‎$a_i$‎های فرد یک واحد کم کنیم، احتمال اینکه جهت حتی یکی از نامساوی‌ها عوض شود کمتر از ‎$2 \over n$‎ است. در نتیجه در این روش با احتمال حداقل ‎$1‎ - ‎{2 \over n}$‎ می‌توانیم بدون عوض شدن جهت نامساوی‌ها همه‌ی اعداد را زوج کنیم سپس با استفاده از قسمت اول به نتیجه‌ی مطلوب می‌رسیم. 

  * [[سوال ۳|سوال قبل]]