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