سوال ۱۸

عملگر $\&$ دو عدد در مبنا‌ی دو را به عنوان ورودی دریافت می‌کند و یک عدد به عنوان خروجی تولید می‌کند. هر رقمِ خروجی، فقط زمانی برابر با ۱ می‌شود که آن رقم در هر دو عدد ورودی برابر ۱ باشد. برای مثال: $$ 6=(110)_2,\ 3=(011)_2 \;\Longrightarrow\; 6 \mathbin{\&} 3 = (010)_2 = 2 $$ دستگاهی داریم که برای هر عدد طبیعی ورودی $i$، الگوریتم زیر را اجرا می‌کند:

  1. متغیر $j$ برابر ۰ قرار داده می‌شود.
  2. متغیر ans برابر ۰ قرار داده می‌شود.
  3. اگر مقدار $i \mathbin{\&} j$ برابر $j$ باشد، مقدار ans یک واحد افزایش می‌یابد.
  4. اگر مقدار $i$ و $j$ برابر باشد، مقدار ans یادداشت می‌شود و الگوریتم خاتمه می‌یابد.
  5. مقدار $j$ یک واحد افزایش می‌یابد و الگوریتم به مرحله‌ی ۳ بازمی‌گردد.

برای مثال، اگر عدد ۲ را به دستگاه ورودی بدهیم، الگوریتم با یادداشت عدد ۲ خاتمه می‌یابد. اگر اعداد $1,2,\ldots,63$ را به ترتیب به دستگاه ورودی بدهیم، مجموع اعداد یادداشت شده چقدر خواهد بود؟

  1. ۱۵۳۸
  2. ۵۵۲
  3. ۱۰۲۴
  4. ۷۲۸
  5. ۶۸۰

پاسخ

گزینه‌ی ۴ درست است.

پاسخ مسئله برابر است با تعداد زوج مرتب‌های $i$ و $j$ به طوری که مجموعه‌ی رقم‌های ۱ عدد $j$ زیرمجموعه‌ی مجموعه‌ی رقم‌های ۱ عدد $i$ باشد. فرض کنید می‌خواهیم $i$ و $j$ را مشخص کنیم. به ازای هر $k$، سه حالت مجاز برای رقم $k$ام اعداد $i$ و $j$ وجود دارد:

  • هر دو ۱ باشند.
  • هر دو ۰ باشند.
  • رقم $k$‌ام $i$ برابر ۱ و رقم $k$ام $j$ برابر ۰ باشد.

همچنین هر کدام از $i$ و $j$ در مبنای ۲ حداکثر ۶ رقم دارند (اعداد کوچکتر از $2^6 = 64$ حداکثر ۶ رقمی‌اند.) اما می‌دانیم $i$ عددی طبیعی است و لذا زوج مرتب ($j = 0$ ،$i = 0$)‌ معتبر نیست. در نتیجه، در مجموع تعداد زوج مرتب‌های معتبر برای $i$ و $j$ برابر است با: ${3 ^ 6 - 1 = 728}$