====== سوال ۱۱ ======

یک عدد صحیح نامنفی را **زیبا** می‌نامیم اگر هم مضربِ $3$ باشد و هم در نمایش دودوییِ آن، دو رقمِ یکِ متوالی وجود نداشته باشد. مثلا عددِ $9$ زیبا است چون هم مضربی از $3$ است و هم در نمایش دودویی آن ($1001$)، هیچ دو رقم یکی مجاور نیستند. چند عدد زیبا در بازه‌ی ${[0, 1023]}$ (شامل خود $0$ و $1023$) وجود دارد؟

  - $48$
  - $54$
  - $38$
  - $46$
  - $30$

<پاسخ>

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

تعداد اعداد $n$ بیتی ($0$ تا $2^n - 1$) که زیبا هستند را $f(n)$ می‌نامیم. برای یافتن این تعداد، از رابطه‌ای بازگشتی استفاده می‌کنیم.

برای محاسبه‌ی تعداد اعداد زیبای $n$ بیتی، ابتدا $n-2$ بیت اول را طوری مقداردهی می‌کنیم که دو بیت پشت سر هم $1$ نداشته باشند، سپس $2$ بیت آخر را طوری مقداردهی می‌کنیم که عدد حاصل به $3$ بخش‌پذیر باشد. باقی‌مانده‌ی دو بیت آخر به $3$، با مشخص شدن سایر $n-2$ بیت تعیین می‌شود.

  - اگر باقی‌مانده‌ی آن‌ها می‌بایست $0$ می‌بود، این دو بیت باید $00$ باشند (اگر $11$ باشند دو بیت یک پشت سر هم داریم).
  - اگر باقی‌مانده‌ی آن‌ها می‌بایست $1$ می‌بود، این دو بیت باید $01$ باشند.
  - اگر باقی‌مانده‌ی آن‌ها می‌بایست $2$ می‌بود، این دو بیت باید $10$ باشند.

در این حالت اگر بیت قبلی $1$ باشد، عدد حاصل زیبا نیست و باید تعداد این حالات را با استفاده از اصل متمم کم کنیم. در این حالت 4 بیت آخر عدد به شکل $0110$ است که چون باقی‌مانده بر $3$ی آن صفر است، $n-4$ بیت قبلی تشکیل یک عدد زیبا می‌دهند. پس تعداد این حالات برابر با $f(n-4)$ است.

اگر تعداد روش‌هایی که می‌توان $n$ بیت را با صفر و یک مقداردهی کرد که دو بیت پشت سر هم $1$ نداشته باشد، را $g(n)$ بنامیم، برای به دست آوردن مقدار $g(n)$، کافی است مقدار بیت آخر را مشخص کنیم. اگر برابر با $0$ باشد، بقیه‌ی بیت‌ها به $g(n - 1)$ حالت و اگر برابر با $1$ باشد، بیت بعدی باید برابر با $0$ و بقیه‌ی بیت‌ها به $g(n - 2)$ حالت انتخاب شوند. بنابراین می‌توان نوشت:

$$ g(n) = g(n - 1) + g(n - 2) $$

با شرایط اولیه: $g(0) = 1$ و $g(1) = 2$.

این رابطه برابر است با:

$$ g(n) = Fib(n + 1) $$

با $Fib(0) = Fib(1) = 1$.

حال برای به دست آوردن $f(n)$ طبق بررسی‌های بالا داریم:

$$ f(n) = g(n - 2) - f(n - 4) = Fib(n - 1) - f(n - 4) $$

با شرایط اولیه:

$$ f(0) = f(1) = f(2) = 1, \quad f(3) = 2 $$

و برای مقادیر بیشتر:

$$ f(4) = 2, \quad f(5) = 4, \quad f(6) = 7, \quad f(7) = 11, \quad f(8) = 19, \quad f(9) = 30, \quad f(10) = 48 $$

در نتیجه، از آن‌جا که $1023 = 2^{10} - 1$، پاسخ مسئله برابر با $f(10) = 48$ است.

</پاسخ>

  * [[سوال ۱۲|سوال بعد]]
  * [[سوال ۱۰|سوال قبل]]