سوال ۴۴

دنباله‌ی ‎ $0,1,1,0,0,0,1,0,1$ ‎ از اعداد صفر و یک را در نظر بگیرید. در هر مرحله یکی از دو عمل زیر را می‌توانیم انجام دهیم:

جای دو عنصر مجاور را با یک‌دیگر عوض کنیم.
سه عنصر متوالی را در نظر گرفته و مقدار هر سه را تغییر دهیم (از صفر به یک و از یک به صفر تبدیل کنیم).

می‌گوییم دنباله‌ی ‎ $A$ ‎ از دنباله‌ی ‎ $B$ ‎ کوچک‌تر است اگر به‌ازای هر رقم یک در ‎ $A$ ‎، رقم متناظر آن در ‎ $B$ ‎ هم برابر یک باشد.

آیا می‌توان با شروع از دنباله‌ی بالا و استفاده از اعمالی که گفته شد به دنباله‌ی ‎ $1,0,1,1,0,0,0,1,0$ ‎ رسید، به شرط این که دنباله‌هایی که در طول مسیر تولید می‌شوند، غیر قابل مقایسه باشند؟ (دو دنباله‌ی ‎ $A$ ‎ و ‎ $B$ ‎ قابل مقایسه‌اند اگر حداقل یکی از آن‌ها از دیگری کوچک‌تر باشد‎.‎)

پاسخ

مراحل کار به شکل زیر می‌باشد:

$0101 \quad \longrightarrow \quad 1010001 \underline{01} \quad \longrightarrow \quad 10100\underline{01}10 \\ 0101\underline{01}010 \quad \longrightarrow \quad 101\underline{01}0010 \quad \longrightarrow \quad 101100010$