المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۹:سوال ۱۸

سوال ۱۸

دو عدد ۱ روی تخته سیاه نوشته شده است. شما می‌توانید یکی از سه کار زیر را بر روی این اعداد انجام دهید.

  • عملیات «دو برابر» : یکی از اعداد روی تخته سیاه را پاک کنید و دو برابر آن را بنویسید.
  • عملیات «سه برابر» : یکی از اعداد روی تخته سیاه را پاک کنید و سه برابر آن را بنویسید.
  • عملیات «جمع» : دو تا از اعداد روی تخته سیاه را پاک کنید و جمع آن‌ها را بنویسید.

هدف این است که با کم‌ترین تعداد استفاده از عملیات «سه برابر»٬ عدد $x$ روی تخته‌سیاه نوشته شود. این کم‌ترین تعداد را $n_x$ می‌نامیم. برای مثال٬ $n_۳ = ۰$ خواهد بود. چون بدون استفاده از عملیات «سه برابر» می‌توان عدد ۳ را با یک‌ بار استفاده از عملیات «دو برابر» و یک‌ بار استفاده از عملیات «جمع» نوشت.

$n_{۳۰}$ و $n_{۴۰}$ کدام هستند؟

  1. $n_{۴۰} = ۰$ ٫ $n_{۳۰} = ۲$
  2. $n_{۴۰} = ۱$ ٫ $n_{۳۰} = ۱$
  3. $n_{۴۰} = ۱$ ٫ $n_{۳۰} = ۰$
  4. $n_{۴۰} = ۰$ ٫ $n_{۳۰} = ۰$
  5. $n_{۴۰} = ۰$ ٫ $n_{۳۰} = ۱$

پاسخ

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

در صورتی که از عمل سه‌برابر استفاده نکنیم در نهایت دو عدد خواهیم داشت که توانی از ۲ هستند. پس تنها اعدادی را می‌توانیم بسازیم که در بسط مبنای ۲ی خود حداکثر دو رقم یک داشته باشند. پس $n_{40}=0$.

باتوجه به اینکه عدد ۳۰ در بسط مبنای ۲ی خود ۴ رقم یک دارد پس حداقل یک‌بار باید از عملیات سه‌برابر استفاده کند.

مثال: ابتدا اعداد ۸ و ۲ را می‌سازیم و آن‌ها را با هم جمع می‌کنیم. حال عدد ۱۰ را با عملیات سه‌برابر به ۳۰ تبدیل می‌کنیم.


ابزار صفحه