سوال ۱۲

یک ماشین در اختیار داریم که هر رشته‌ی $k$تایی از صفر و یک مثل $x_1, x_2, ..., x_k$ را به یک رشته‌ی $(k-1)$تایی به صورت $(x_1 \oplus x_2), (x_2 \oplus x_3), \ldots, (x_{k-1} \oplus x_{k})$ تبدیل می‌کند. (منظور از $x \oplus y$ عمل XOR دو عدد $x$ و $y$ است و مقدار آن تنها وقتی یک است که دقیقا یکی از دو عدد $x$ و $y$ یک باشد.) تعداد $n$های از ۱ تا ۱۳۹۲ را بیابید که برای هر رشته $n$تایی دل‌خواه مثل $x_1, x_2, ..., x_n$ اگر این رشته را به ماشین بدهیم و خروجی را باز به ماشین بدهیم و این‌کار را آن قدر تکرار کنیم تا در نهایت یک عدد مثل $t$ به دست آید، آن گاه داشته باشیم: $t=x_1\oplus x_2 \oplus x_3 \oplus \cdots \oplus x_n$.

  1. ۱
  2. ۱۰
  3. ۱۱
  4. ۱۰۲۴
  5. ۱۰۲۵

پاسخ

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

عدد $n$ خاصیت فوق را دارد اگر و تنها اگر $n = 2 ^ k$.