سوال ۴

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

  1. $0$
  2. $1$
  3. $2$
  4. $3$
  5. $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 می‌شود.