المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۱۹

سوال ۱۹

از دو عدد دودویی ‎$A$‎ و ‎$B$‎، عدد دودویی ‎$C=A\oplus B$‎ را به این صورت به‌دست می‌آوریم: اگر رقم‌های ‎$i$ام ‎$A$‎ و ‎$B$‎ یکسان باشند، رقم ‎$i$ام ‎$C$‎ برابر صفر و در غیر این صورت برابر ‎۱‎ است (در سمت چپ هر عدد به اندازه‌ی کافی می‌توان رقم صفر اضافه کرد). مثلاً ‎$00100\oplus 110=00010$‎. حال بر روی عدد دودویی ‎$x$‎ عمل زیر را انجام می‌دهیم: ‎$x$‎ را به دو قسمت دل‌خواه ‎$x_1$‎ و ‎$x_2$‎ تقسیم می‌کنیم و ‎$x$‎ را برابر ‎$x_1\oplus x_2$‎ قرار می‌دهیم. مثلاً اگر ‎$x=11000100$‎، بر اساس یک حالت از تقسیم ‎$x$‎ داریم: ‎$x_1=110$‎ و ‎$x_2=00100$‎. یک عدد دودویی را ‎«جالب»‎ می‌گوییم اگر بتوان با تکرار عمل بالا آن را به ‎۱‎ تبدیل کرد. چند عدد دودویی به طول ‎۱۰ «جالب»‎ است؟ (رقم‌های سمت چپ یک عدد دودویی می‌تواند صفر باشد‎.‎)

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

پاسخ

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

شرط لازم و کافی برای آن که به عدد ۱ برسیم آن است که تعداد ۱ های عدد اولیه فرد باشد که تعداد این اعداد برابر با $\binom{10}{1}+\binom{10}{3}+...+\binom{10}{9}$؛ یعنی $2^9$ می‌باشد.


ابزار صفحه