سوال ۴

دنباله‌ی ‎$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$‎ یک مقدار نامنفی جدیدی قرار دهیم که:

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

  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}$‎ می‌توانیم بدون عوض شدن جهت نامساوی‌ها همه‌ی اعداد را زوج کنیم سپس با استفاده از قسمت اول به نتیجه‌ی مطلوب می‌رسیم.