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


به جایگشت $p_1, p_2, ..., p_n$ از اعداد $1$ تا $n$ زیبا گوییم هرگاه به ازای هر $1 \leq i \leq n-1$ داشته باشیم: $p_i \leq p_{i+1} + 3$. به ازای $n=9$، باقی‌مانده‌ی تقسیم تعداد جایگشت‌های زیبا بر $5$ چند است؟


  - $0$
  - $1$
  - $2$
  - $3$
  - $4$ 



<پاسخ>
گزینه (۲) درست است.


به ازای $n=4$ تمام 24 جایگشت ممکن زیبا هستند. حال به ازای $n \geq 5$ با استفاده از تناظر، از هر جایگشت زیبای $n-1$ تایی، 4 جایگشت زیبا و متمایز $n$ تایی می سازیم. کافی است تا عدد $n$ را در جایگشت دلخواهی به طول $n-1$ درج کنیم. عدد $n$ میتواند در انتهای جایگشت مذکور و یا پیش از اعداد $n-1$، $n-2$ و یا $n-3$ قرار داده شود پس 4 مکان برای درج آن داریم. از طرفی به ازای هر جایگشت دلخواه $n-1$ تایی، با حذف $n$ از دقیقا 4 جایگشت $n$ تایی به آن جایگشت میرسیم. پس اگر $f(n)$ را تعداد جایگشت های زیبای $n$ تایی تعریف کنیم، داریم:
$$f(4) = 24$$
و برای $n \geq 5$ :
$$f(n) = 4f(n-1)$$

پس $f(9)$ برابر $24 \times 4^5$ است که به پیمانه 5 برابر 1 می‌شود.


</پاسخ>
  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]