المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

یک عدد دودویی ‎$n$‎ با ‎۱۳۷۹‎ رقم صفر و یک را در نظر بگیرید (ممکن است تعدادی از رقم‌های سمت چپ آن صفر باشد). با هر ‎«عمل»‎ یکی از ارقام این عدد را انتخاب می‌کنیم و آن را تغییر می‌دهیم ( صفر به یک و یک به صفر تبدیل می‌شود). حداقل تعداد عمل‌هایی که پس از آن عدد حاصل بر ‎۳‎ بخش‌پذیر می‌شود را در نظر بگیرید. این تعداد را عدد بخش‌پذیری ‎$n$‎ می‌نامیم. در میان اعداد دودویی ‎۱۳۷۹‎ رقمی، بیشینه‌ی ‎(ماکزیمم)‎ عدد بخش‌پذیری چند است؟

  1. ۱
  2. ۲
  3. ۳
  4. ۶۸۸
  5. ۱۳۷۹‎

پاسخ

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

اگر باقی‌مانده‌ی تقسیم عدد بر ۳ برابر ۱ باشد٬ آن‌گاه یکی از ارقام ۱ موجود در جایگاه‌های فرد را از ۱ به ۰ تبدیل می‌کنیم و اگر آن جایگاه‌ها ۰ باشد می‌توانیم یکی از ارقام ۰ موجود در جایگاه‌های زوج را از ۰ به ۱ تبدیل کنیم٬ که اگر چنین چیزی نیز ممکن نبود دو تا از ۰ های موجود در جایگاه ‌های ی فرد را از ۰ به ۱ تبدیل می‌کنیم. به همین شیوه ثابت می‌شود که اگر باقی‌مانده تقسیم عدد بر ۳ برابر ۲ باشد نیز بیشینه‌ی عدد بخش‌پذیری ۲ است.


ابزار صفحه