سؤال ۱۵

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

۱۰
۱۱
۱۲
۱۳
۱۴

پاسخ

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

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

$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$