====== سؤال ۲۴ ======

اعداد ۰ تا ۱۲۷ را به ترتیب پشت سر هم نوشته‌ایم. حالا بین هر دو عدد $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$


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

<WRAP :en>
$F(4k-1)=0$

 
$F(4k)=4k$


$F(4k+1)=1$


$F(4k+2)=4k+3$
</WRAP>

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

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


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



</پاسخ>
  * [[سوال ۲۵|سوال بعد]]
  * [[سوال ۲۳|سوال قبل]]