====== رنگ‌آمیزی ======



آرایه $a_1, a_2,\dots , a_n$ شامل $n$ عدد صحیح **متمایز** است. عدد رنگی این آرایه کوچکترین عدد طبیعی مثل $C$ است که بتوان با $C$ رنگ، مجموعه اعداد صحیح را رنگ کرد طوری که شرط زیر برقرار باشد:

برای هر $i$ و $j$ که $1 \leq i < j \leq n$ و هر $x$ صحیح دلخواه، رنگ دو عدد $a_i + x$ و $a_j + x$ متفاوت باشد.

می‌خواهیم با تعدادی عملیات کاری کنیم که عدد رنگی آرایه کمتر یا مساوی $n$ شود. در هر عملیات می‌توانیم یکی از دو کار زیر را انجام دهیم.
  *  یکی از اعضای آرایه را به علاوه ۱ کنیم.
  * یکی از اعضای آرایه را منهای ۱ کنیم.

ثابت کنید با کمتر یا مساوی 
$\lfloor \frac{n^2}{4} \rfloor$
 عملیات می‌توانیم به خواسته‌مان برسیم. دقت کنید در طی عملیات‌ها ممکن است بعضی از اعضای آرایه برابر شوند، اما در انتها تمامی اعداد باید **متمایز** باشند. \\
در صورتی که ثابت کنید با کمتر یا مساوی 
$\lfloor \frac{n^2}{2} \rfloor$
 عملیات نیز می‌توانیم به خواسته‌مان برسیم، **۲۵ امتیاز** دریافت می‌کنید.




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