====== سوال ۹ ======

فرض کنید $a$ یک بیت دل‌خواه (۰ یا ۱) باشد. منظور از $\bar{a}$ برابر با $1-a$ است. حال فرض کنید یک رشته‌ای دودویی داریم. در هر مرحله می‌توان یکی از دو عمل زیر را انجام داد:

  * یک بیت مانند $b$ در رشته را در نظر بگیریم و در دو طرف آن $\bar{b}$ بنویسیم. برای مثال از رشته‌ی  $\left<0, {۱}, 1\right>$ و با انتخاب بیت وسط می‌توان به رشته‌ی $\left<0, {0, 1, 0}, 1\right>$ رسید.
  * دو بیت متوالی مانند $ab$ را در نظر بگیریم و به جای آن‌ها $\bar{a}\bar{b}$ بنویسیم. برای مثال از رشته‌ی $\left<0, {1, 1}\right>$ و با انتخاب دو بیت سمت راست می‌توان به رشته‌ی $\left<0, {0, 0}\right>$ رسید.


اگر ابتدا رشته‌ی دودویی 
$\left<0\right>$ را داشته باشیم، با استفاده از دو عمل فوق نمایش دودویی چند عدد صحیح از ۲۱ تا ۲۶ را می‌توانیم بسازیم؟ 
توجه کنید که قرار گرفتن رقم‌های ۰ در ابتدای نمایش اشکال ندارد. برای مثال اگر به رشته‌ی 
$\left<0, 0, 1, 1, 0, 1\right>$
برسیم، در واقع عدد ۱۳ را ساخته‌ایم.


  - ۰
  - ۱
  - ۲
  - ۳
  - ۴
<راهنمایی>
ثابت کنید یک عدد قابل ساختن است اگر و تنها اگر تعداد بیت های ۱ اش زوج باشد.

</راهنمایی>

<پاسخ>
 گزینه‌ی ۳ درست است.

ثابت می‌کنیم یک عدد قابل ساختن است، اگر و تنها اگر در نمایش دودویی آن زوج رقم ۱ وجود داشته باشد. با انجام این دو نوع عمل، زوجیت تعداد ارقام ۱ تغییری نمی‌کند. کافی است ثابت کنیم هر عدد که نمایش دودویی آن زوج رقم ۱ دارد، قابل ساختن است. فرض کنید عدد $n$ چنین باشد و $2p$ رقم ۱ و $q$ رقم ۰ در نمایش دودویی آن موجود باشد. با تبدیل ۰ به ۰۱۱ به شکل زیر می‌توان به رشته‌ی $011\ldots 1$ که $2p$ رقم ۱ دارد، رسید:
$$0 \rightarrow 101 \rightarrow 011 \rightarrow 10111 \rightarrow 01111 \rightarrow \ldots $$
حال با تبدیل ۰ به ۰۰۰ به شکل زیر می‌توان به رشته‌ی $00\ldots 011\ldots 1$ رسید که $2p$ رقم ۱ و بیش‌تر از $q$ رقم ۰ دارد:
$$011\ldots 1 \rightarrow 10111\ldots 1 \rightarrow 11011\ldots 1 \rightarrow 00011\ldots 1 \rightarrow \ldots $$
حال با تبدیل ۰۱ به ۱۰ می‌توان هر ۰ را آن‌قدر به سمت راست انتقال داد تا به جای مورد نظر برسد و به این ترتیب عدد $n$ ساخته می‌شود.

در نمایش دودویی اعداد $21, 22, \ldots , 26$ تنها دو عدد هستند که زوج رقم ۱ دارند. پس پاسخ برابر ۲ است.
</پاسخ>

  * [[سوال ۱۰|سوال بعد]]
  * [[سوال ۸|سوال قبل]]