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

</پاسخ>

  * [[سوال ۲|سوال بعد]]