سوال ۱۴

در ابتدا عدد $x=0$ را داریم. در هر مرحله می‌توانیم عدد $x$ را به یکی از دو عدد $\lfloor\frac{x}{2}\rfloor$ یا $4x+2$ تبدیل کنیم. با استفاده از این حرکات چه تعداد از اعضای مجموعه $A = \{77, 511, 210, 170, 238\}$ را می‌توان ساخت؟

  1. $0$
  2. $1$
  3. $2$
  4. $3$
  5. $4$

پاسخ

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

تنها اعداد ۵۱۱، ۱۷۰ و ۲۳۸ قابل تولید هستند.

این ماشین اعدادی را تولید می‌کند که در نمایش مبنای ۲ شان هیچ‌گاه دو رقم ۰ متوالی نداشته باشند. برای اثبات این موضوع کافی است تا نمایش مبنای ۲ ورودی‌ها و خروجی‌های ماشین را در نظر گرفته و روی تعداد بیت‌های عدد $x$ استقرا بزنیم. پس کافی است تا نمایش مبنای ۲ اعضای مجموعه $A$ را در نظر گرفته و پاسخ را بیابیم.