ماشین عجیب
سعید دارای ماشین عجیبی است که دارای ۱۰۰۰ خانه حافظه می‌باشد. به هر خانه حافظه یک بیت گفته می‌شود و بیت i$$ام را با $M[i]$ نشان می‌دهیم. هر بیت حافظه یکی از دو مقدار ۰ و ۱ را در خود ذخیره می‌کند.
متاسفانه مقادیر ذخیره شده در حافظه ماشین قابل رویت نیست. تنها می‌دانیم اعداد ذخیره شده در بیت‌های ۸۰۱ تا ۹۰۰ برابر ۰ و اعداد ذخیره شده در بیت‌های ۹۰۱ تا ۱۰۰۰ برابر ۱ هستند.
این ماشین عجیب تنها توانایی اجرای دستورات زیر را دارد:
- $ M[i]= M[i_1 ]∧ M[i_2 ]⋯∧ M[i_k] $: با اجرای این دستور در صورتی که اعداد ذخیره شده در بیت‌های $i_1$ام، $i_2$ام و ⋯ و $i_k$ام برابر ۱ باشند مقدار $M[i]$ یک و در غیر این صورت صفر خواهد شد.
- $M[i]= M[i_1 ]∨ M[i_2 ]⋯∨ M[i_k]$ : با اجرای این دستور در صورتی که اعداد ذخیره شده در بیت‌های $i_1$ام، $i_2$ام و ⋯ و $i_k$ام برابر ۰ باشند مقدار $M[i]$ صفر و در غیر این صورت یک خواهد شد.
- $M[i]= M[i_1 ]⊕ M[i_2 ]⋯⊕ M[i_k]$: با اجرای این دستور در صورتی که تعداد یک‌های ذخیره شده در بیت‌های $i_1$ام، $i_2$ام و ⋯ و $i_k$ام فرد باشد مقدار$M[i]$ یک و در غیر این صورت صفر خواهد شد.
در واقع این سه دستور به ترتیب or٬and و xor منطقی می‌باشند. بدیهی است که بلافاصله بعد از این که سعید به دستگاه دستور می‌دهد، دستگاه دستور را اجرا می‌کند. توجه کنید اندیس‌های $i$,$i_1$,⋯,$i_k$ حداقل ۱ و حداکثر ۱۰۰۰ می‌باشند و $k$ نیز حداقل ۱ و حداکثر ۱۰۰۰ می‌باشد.
در کنار دستورات فوق، این ماشین عجیب به سوال زیر هم پاسخ می‌دهد.
- آیا هنوز اعداد ذخیره شده در بیت‌های ۸۰۱ام تا ۹۰۰ام برابر با ۰ و اعداد ذخیره شده در بیت‌های ۹۰۱ام تا ۱۰۰۰ام برابر با ۱ است؟
جواب ماشین به این سوال بله یا خیر خواهد بود.
سعید می خواهد در مورد عدد $x = ۸ \times M[۱] + ۴ \times M[۲] + ۲ \times M[۳] + M[۴]$ اطلاعاتی کسب کند. او دوست دارد این اطلاعات را با اجرای کمترین تعداد دستور و تنها یک بار سوال پرسیدن کسب کند. به او کمک کنید تا اطلاعات زیر را بدست اورد.
توجه: در هر قسمت ابتدا دستورات خود را نوشته و سپس آن را در چند سطر توضیح دهید. در هر قسمت باید از کمترین تعداد دستور ممکن استفاده کنید، اما نیازی به اثبات کمینه بودن تعداد دستورات نیست . دقت کنید در هر قسمت فقط یک‌بار می‌توانید سوال بپرسید.
الف) آیا $x$ بزرگتر از ۵ است؟
ب) آیا $x$ توانی از ۲ است؟ (دقت کنید که ۱ توانی از ۲ است).
پ) آیا $x$ بر ۳ بخش‌پذیر است؟
پاسخ
دقت کنید $x$ یک عدد بین $1$ تا $15$ است.
الف)
به ازای همه‌ی $x$های بزرگتر $5$ عبارت
$M[1] ∨ ( M[2] ∧ M[3] ) $
برابر با یک و به ازای همه‌ی $x$های کوچکتر مساوی با $5$ این عبارت برابر با صفر است.
پس دستور‌ها را به این صورت می‌نویسیم:
- $ M[10] = M[2] ∧ M[3] $
- $ M[801] = M[1] ∨ M[10] $
حال با پرسیدن سوال از ماشین اگر با جواب خیر مواجه شدیم $x$ بزرگتر از $5$ و در غیر این صورت $x$ کوچکتر مساوی با $5$ است.
ب)
توان دو بودن $x$ معادل با وجود دقیقاً یک بیت $1$ بین
$M[1]$، $M[2]$، $M[3]$ و $M[4]$
است.
پس باید xor این $4$ بیت یک بوده و نیز اگر جفت‌های $M[1]$ و $M[2]$ یا $M[3]$ و $M[4]$ را در نظر بگیریم هیچ کدام از جفت‌ها نباید کاملاً یک باشند.
پس برای توان دو بودن $x$ عبارت
$ ( M[1] ⊕ M[2] ⊕ M[3] ⊕ M[4] )$ $∧$ $! ( ( M[1] ∧ M[2] ) ∨ ( M[3] ∧ M[4] ) ) $
باید برابر با یک باشد و نیز اگر این عبارت صفر باشد آنگاه $x$ توان دو نیست.
دقت کنید که $!X$ همان not است که یک را به صفر و صفر را به یک تبدیل می‌کنید. یعنی همان $X ⊕ 1$.
پس دستور‌ها را به این شکل می‌نویسیم:
- $M[10] = M[1] ⊕ M[2] ⊕ M[3] ⊕ M[4]$
- $M[11] = M[1] ∧ M[2] $
- $M[12] = M[3] ∧ M[4] $
- $M[12] = M[11] ∨ M[12]$
- $M[12] = M[12] ⊕ M[1000]$
- $M[901] = M[12] ∧ M[10] $
حال از ماشین سوال می‌پرسیم. اگر جواب ماشین بله بود $x$ توان دو است وگرنه $x$ توان دو نیست.
پ)
هر $x$ را به صورت یک رشته دودویی $4$ رقمی در نظر می‌گیریم. یعنی $x$ برابر است با:
$ \overline{ M[1]M[2]M[3]M[4] } $
با توجه به این نمایش دودویی، همه‌ی $x$های مضرب $3$ به صورت زیر هستند:
$0000$, $0011$, $0110$, $1001$, $1100$, $1111$
با کمی مشاهده متوجه می‌شویم که تعداد بیت‌های یک این اعداد زوج بوده و نیز فقط $1010$ و $0101$ هستند که تعداد بیت‌های یک آنها زوج است ولی مضرب $3$ نیستند. حال عبارت زیر را در نظر بگیرید:
$M[1] ⊕ M[2] ⊕ M[3] ⊕ M[4]$ $⊕$ $( (M[1]⊕M[2]) ∧ (M[2]⊕M[3]) ∧ (M[3]⊕M[4]) )$
این عبارت برای مضارب $3$ برابر با صفر و برای اعداد غیر بخش پذیر بر $3$ برابر با یک است. پس دستور‌های مورد نیاز برابرند با:
- $M[10] = M[1]⊕M[2] $
- $M[11] = M[2]⊕M[3] $
- $M[12] = M[3]⊕M[4] $
- $M[13] = M[10] ∧ M[11] ∧ M[12] $
- $M[801] = M[1] ⊕ M[2] ⊕ M[3] ⊕ M[4] ⊕ M[13]$
جواب قسمت پ برابر است با جواب سوال ما از ماشین.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
