====== سوال ۴ ======

سلطان در ابتدا عدد ۰ را روی تخته نوشته است. در هر مرحله اگر عدد $x$ روی تخته نوشته شده باشد، او می‌تواند آن را با یکی از اعداد $\lfloor{}\frac{x}{3}\rfloor$، $3x$ و $9x+5$ جای‌گزین کند. به ازای چند تا از اعداد ۰ تا ۵۰۰، سلطان می‌تواند پس از تعداد متناهی گام، به آن عدد برسد؟


  - ۲۳۹
  - ۴۰۸
  - ۲۵۰
  - ۱۶۹
  - ۶۴

<پاسخ>

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

شرط لازم برای رسیدن به یک عدد این است که در نمایش آن عدد در مبنای ۳، تمام ارقام ۲ سمت راست یک رقم ۱ باشند. زیرا تنها راه تولید رقم ۲ استفاده از عمل $9x+5$ است که این خاصیت را دارد. دو عمل دیگر نیز یا یک صفر در سمت راست عدد قرار می‌دهند و یا سمت راست‌ترین رقم آن را حذف می‌کنند. حال فرض کنید $a_n$ تعداد  رشته‌های $n$بیتی در مبنای ۳ باشد که این خاصیت را دارند. این رشته‌ها را به دو دسته تقسیم می‌کنیم. دسته‌ی اول آن‌هایی که با ۰ شروع می‌شوند و دسته‌ی دوم آن‌هایی که با  ۱ .  بدیهی است که تعداد رشته‌های دسته‌ی اول برابر $a_{n-1}$ است. علاوه بر این رشته‌های دسته‌ی دوم اگر رقم‌ دومشان ۲ باشد تعدادشان برابر $a_{n-2}$  است و یا در غیر این صورت تعدادشان $a_{n-1}$ است. پس در کل داریم $a_n = 2a_{n-1} + a_{n-2}$ . برای $n=2$ هم داریم:‌ $a_2 = 5$ . 
به راحتی می‌توان مشاهده کرد تمام اعداد ۶ رقمی که در این خاصیت صدق می‌کنند، کمتر از ۵۰۰ می‌باشند پس تعداد این اعداد برابر است با $a_6 =169$.



</پاسخ>

  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]