سوالات المپیاد:مرحله ی دوم:دوره ی ۲۶:سوال ۱۴
سوال ۱۴
در ابتدا عدد $x=0$ را داریم. در هر مرحله می‌توانیم عدد $x$ را به یکی از دو عدد $\lfloor\frac{x}{2}\rfloor$ یا $4x+2$ تبدیل کنیم. با استفاده از این حرکات چه تعداد از اعضای مجموعه $A = \{77, 511, 210, 170, 238\}$ را می‌توان ساخت؟
- $0$
- $1$
- $2$
- $3$
- $4$
پاسخ
گزینه (۴) درست است.
تنها اعداد ۵۱۱، ۱۷۰ و ۲۳۸ قابل تولید هستند.
این ماشین اعدادی را تولید می‌کند که در نمایش مبنای ۲ شان هیچ‌گاه دو رقم ۰ متوالی نداشته باشند. برای اثبات این موضوع کافی است تا نمایش مبنای ۲ ورودی‌ها و خروجی‌های ماشین را در نظر گرفته و روی تعداد بیت‌های عدد $x$ استقرا بزنیم. پس کافی است تا نمایش مبنای ۲ اعضای مجموعه $A$ را در نظر گرفته و پاسخ را بیابیم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
