ماشین عجیب

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

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

سوال بعد

المپدیا

ابزار کاربر

ابزار سایت

ماشین عجیب

ابزار صفحه