ماشین عجیب

سعید دارای ماشین عجیبی است که دارای ‎۱۰۰۰‎ خانه حافظه می‌باشد. به هر خانه حافظه یک ‎بیت‎ گفته می‌شود و بیت ‎i$‎$ام را با ‎$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]$

جواب قسمت پ برابر است با جواب سوال ما از ماشین.