سوال ۹
فرض کنید $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$ تنها دو عدد هستند که زوج رقم ۱ دارند. پس پاسخ برابر ۲ است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
