سؤال ۲۴

اعداد ۰ تا ۱۲۷ را به ترتیب پشت سر هم نوشته‌ایم. حالا بین هر دو عدد $XOR$ (یا $\oplus$ ) آن دو را می‌نویسیم. سپس اعداد اولیه را پاک می‌کنیم. این کار را آن‌قدر تکرار می‌کنیم تا تنها یک عدد باقی بماند. آن عدد چند است؟

$C= A \oplus B$ را به این صورت تعریف می‌کنیم: اگر $a_i$ ٬ $b_i$ و $c_i$ به ترتیب رقم‌های $i$ ام (از سمت راست) $A$ ، $B$ و $C$ در مبنای دو باشند، در این صورت $c_i = \begin{cases} 0 & \text{$a_i = b_i$}\\ 1 & \text{$a_i \neq b_i$} \end{cases}$ . مثلاً $5 \oplus 7 = (101)_2 \oplus (111)_2 = 2$ .

۰
۱۲۷
۱
۶۴
۶۳

پاسخ

گزینه (۱) درست است.

$F(i)$ را برابر با برایند $XOR$ تمام اعداد قبل از $i$ و خود $i$ تعریف می‌کنیم. معلوم است که $...،F(4)=4،F(3)=0،F(2)=3،f(1)=1$

تساوی‌های زیر به شیوه استقرای ریاضی به راحتی قابل اثبات هستند:

$F(4k-1)=0$

$F(4k)=4k$

$F(4k+1)=1$

$F(4k+2)=4k+3$

به عنوان مثال برای اثبات درستی $F(4k-1)=0$ به شیوه زیر عمل می‌کنیم:

$F(4k-1)=(4k-1) \oplus F(4k-2)=(4k-1) \oplus (4k-1)=0$

چون ۱۲۷ به شکل $4k-1$ می‌باشد٬ بنابراین $F(127)=0$ .

المپدیا

ابزار کاربر

ابزار سایت

سؤال ۲۴

ابزار صفحه