Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۸

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

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

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

n۳۰ و n۴۰ کدام هستند؟

  1. n۴۰=۰ ٫ n۳۰=۲
  2. n۴۰=۱ ٫ n۳۰=۱
  3. n۴۰=۱ ٫ n۳۰=۰
  4. n۴۰=۰ ٫ n۳۰=۰
  5. n۴۰=۰ ٫ n۳۰=۱

پاسخ

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

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

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

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


ابزار صفحه