سؤال ۱۵

دنباله‌ی $A= <a_1,...,a_n>$ جای گشتی از اعداد ۱ تا $n$ است به‌طوری‌ که برای $1 \le i \le {n-1}$ یا $a_i= a_{i+1} + ۵$ یا $a_i= a_{i+1} -۸$ بزرگ‌ترین مقدار $n$ چند است؟

  1. ۱۰
  2. ۱۱
  3. ۱۲
  4. ۱۳
  5. ۱۴

پاسخ

گزینه (۵) درست است.

اعداد قبل و بعد از اعداد ۱ تا ۸ به صورت منحصربه‌فرد به شکل زیر یافت می‌شوند:

$$6 \longrightarrow 1 \longrightarrow 9 \\ 7 \longrightarrow 2 \longrightarrow 10 \\ 8 \longrightarrow 3 \longrightarrow 11 \\ 9 \longrightarrow 4 \longrightarrow 12 \\ 10 \longrightarrow 5 \longrightarrow 13 \\ 11 \longrightarrow 6 \longrightarrow 1 \\ 12 \longrightarrow 7 \longrightarrow 2 \\ 13 \longrightarrow 8 \longrightarrow 3$$

معلوم است که در این صورت دور بسته‌ای به شکل مقابل یافت می‌شود:

حلقه مقابل باید از یک نقطه بریده شود که اگر این عمل بین ۱ و ۶ باشد٬ آن‌گاه عدد ۱۴ می‌تواند بعد از ۶ وارد شود که در این صورت به جای‌گشت زیر خواهیم رسید:

$$1-9-4-12-7-2-10-5-13-8-3-11-6-14$$

و اگر آن حلقه بین ۱ و ۹ بریده شود باز عدد ۱۴ می‌تواند قبل از عدد ۹ وارد شود که در این صورت نیز به جای‌گشتی خواهیم رسید که به شکل زیر می‌باشد:

$$14-9-4-12-7-2-10-5-13-8-3-11-6-1$$