المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۴:سوال ۴

سوال ۴

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

  1. ۲۳۹
  2. ۴۰۸
  3. ۲۵۰
  4. ۱۶۹
  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$.


ابزار صفحه