====== سوالات ۲۸ تا ۳۰ ======

دستگاه عددساز در ابتدا عدد $x$ را که برابر با صفر است نمایش می‌دهد. 
این دستگاه از ما یک دنباله از اعداد ۰ و ۱ می‌گیرد و طی مراحل زیر عدد $x$ را تغییر می‌دهد:‌

با شروع از اولین عدد، به ازای هر عدد در دنباله:

  * اگر عدد برابر با ۰ بود، $x$ را ۴ برابر می‌کنیم.
  * اگر عدد برابر با ۱ بود، $x$ را برابر با $x+3$ قرار می‌دهیم.

یک دنباله از ۰ و ۱ را «معتبر» می‌نامیم اگر در آن هیچ سه عدد متوالی برابر با ۱ نباشند.

====== سوال ۲۸ ======

با استفاده از دستگاه عددساز و دنباله‌های معتبر به طول ۵ چند عدد مختلف می‌توان ساخت؟


  - ۲۴
  - ۳۱
  - ۱۶
  - ۲۸
  - ۱۳


<پاسخ>
 گزینه‌ی ۱ درست است.

راه حل در سوال بعدی توضیح داده شده است.
</پاسخ>

====== سوال ۲۹ ======

با استفاده از دستگاه عددساز و دنباله‌های معتبر به طول ۱۰ چند عدد مختلف می‌توان ساخت؟


  - ۲۷۴
  - ۵۰۴
  - ۹۲۷
  - ۲۸۸
  - ۱۷۸


<پاسخ>
 گزینه‌ی ۲ درست است.

نشان‌ می‌دهیم اگر عدد حاصل از دو دنباله‌ی $a$ و $b$ با طول برابر یکسان باشد، $a=b$.
آخرین ۰ دنباله را در نظر می‌گیریم. اگر بعد از آن ۱ای نیامده باشد رقم آخر $x$ در مبنای چهار برابر ۰ است. در غیر این صورت یا یکبار عدد ۱ بعد از آن آمده که در نتیجه رقم آخر $x$ در مبنای چهار، ۳ است و یا دوبار عدد ۱ آمده که رقم  آخر $x$ در مبنای چهار برابر با ۲ است. در هر صورت آخرین رقم $x$ هرچه باشد  یک یا دو یا سه عضو انتهای دنباله‌ی سازنده‌ی آن یکتا تعیین می‌شود. با حذف این عناصر از انتهای $a$ و $b$ و محاسبه‌ی مقدار $x$ قبل از آن‌ها دنباله‌ها کوچکتر می‌شوند و طبق فرض همچنان اعداد برابری تولید می‌کنند. با ادامه‌ی این روند پایان پذیر برابری $a=b$ ثابت می‌شود.
پس مسئله به مسئله‌ی شمردن تعداد رشته‌های معتبر به طول $n$ تبدیل می‌شود.

$F(n)$
را برابر با تعداد رشته‌های معتبر به طول $n$ در نظر می‌گیریم. می‌توان نشان داد:

$$F(n)=F(n-1)+F(n-2)+F(n-3)$$

$$F(1)=2, F(2)=4, F(3)=7, F(4)=13, F(5)=24, ... , F(10)=504$$
</پاسخ>

====== سوال ۳۰ ======

فرض کنید بتوانیم دنباله‌‌های معتبر به هر طول دل‌خواهی را به دستگاه عددساز بدهیم.
حداکثر چند عدد کوچک‌تر از ۲۰۴۸ می‌توانیم بسازیم؟


  - ۸۱
  - ۲۴۹
  - ۲۲۴
  - ۲۴۳
  - ۲۰۴۷


<پاسخ>
 گزینه‌ی ۴ درست است.

با کنار گذاشتن حالت $x=0$، می‌توانیم از ۰ های اول دنباله صرف‌نظر کنیم (چون $x$ را تغییر نمی‌دهند). 
پس دنباله با ۱ شروع می‌شود و حداکثر چهار ۰ بعد از آن داریم. زیرا در غیر این صورت عدد $x$ دست‌کم برابر با
$3\times4^5=3072$
می‌شود. با این حساب بیشترین عدد $x$ با دنباله‌ی
$[1,1,0,1,1,0,1,1,0,1,1,0,1,1]$
تولید می‌شود که برابر با ۲۰۴۶ است.
تعداد ۱های موجود بعد از هر ۰ در دنباله می‌تواند عددی بین صفر تا دو باشد و دنباله با یک یا دو عدد ۱ آغاز خواهد شد. پس اگر $i$تا ۰ در دنباله داشته باشیم
$2\times3^i$
حالت مختلف خواهیم داشت.تعداد ۰ها در دنباله پنج حالت دارد ($0\leq i \leq 4$)
در نتیجه پاسخ سوال برابر است با:
$$1+\sum_{i=0}^4 2\times3^i = 1+2\times(3^0+3^1+3^2+3^3+3^4) = 243$$
</پاسخ>

  * [[سوالات ۲۵ تا ۲۷|سوال قبل]]