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