المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۴۴

سوال ۴۴

دنباله‌ی ‎$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$$


ابزار صفحه