یک ماشین در اختیار داریم که هر رشتهی kتایی از صفر و یک مثل x1,x2,...,xk را به یک رشتهی (k−1)تایی به صورت (x1⊕x2),(x2⊕x3),…,(xk−1⊕xk) تبدیل میکند. (منظور از x⊕y عمل XOR دو عدد x و y است و مقدار آن تنها وقتی یک است که دقیقا یکی از دو عدد x و y یک باشد.) تعداد nهای از ۱ تا ۱۳۹۲ را بیابید که برای هر رشته nتایی دلخواه مثل x1,x2,...,xn اگر این رشته را به ماشین بدهیم و خروجی را باز به ماشین بدهیم و اینکار را آن قدر تکرار کنیم تا در نهایت یک عدد مثل t به دست آید، آن گاه داشته باشیم: t=x1⊕x2⊕x3⊕⋯⊕xn.
پاسخ
گزینهی ۳ درست است.
عدد n خاصیت فوق را دارد اگر و تنها اگر n=2k.