سوال ۱۲

دو دنباله‌ی ۱۰ تایی $A$ و $B$ از ارقام ۰ و ۱ داده شده‌اند. در هر حرکت می‌توانیم وضعیت ارقام $A$ را از سمت چپ تا جای دلخواهی عوض کنیم (یعنی هر رقم ۰ را به ۱ و هر رقم ۱ را به ۰ تبدیل کنیم.) اگر ۱۰۱۱۱۰۰۱۰۰ = $A$ و ۰۰۱۱۰۱۰۰۱۰ = $B$ باشد٬ حداقل چند حرکت لازم است تا $A$ به $B$ تبدیل شود؟

۵
۶
۱۰
۱۱
نمی‌توان از $A$ به $B$ رسید.

پاسخ

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

اولین رقم از سمت راست $A$ که با معادلش در $B$ متفاوت باشد را $i$ می‌نامیم. در هر مرحله٬ از اولین رقم از سمت چپ $A$ شروع کرده و تا رقم $i$ تمام ارقام را تعویض می‌کنیم که بعد از ۵ مرحله به شکل زیر به دنباله $B$ خواهیم رسید.

$A_0= \underline{101110010}0 \longrightarrow A_1= \underline{0100011}010 \longrightarrow A_2= \underline{101110}0010 \longrightarrow$

$A_3= \underline{0100}010010 \longrightarrow A_4= \underline{1}011010010 \longrightarrow A_5=0011010010=B$