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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

n تا عدد ۱ روی تخته سیاه نوشته است. در هر مرحله دو عدد a و b را از زوی تخته پاک می‌کنیم و به جای آن‌ها دو بار عدد a+b را می‌نویسیم. بعد از چند مرحله٬ اعداد به nتا عدد n تبدیل شده‌اند.

n کدام یک از اعداد زیر می‌تواند باشد؟

۱)۱۵ ۲)۱۶ ۳)۹

  1. ۱ و ۳
  2. ۲ و ۳
  3. فقط ۳
  4. فقط ۲
  5. ۱ و ۲ و ۳

پاسخ

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

شیوه‌ی ساخته شدن n عدد n از روی n عدد ۱ را در نظر می‌گیریم. با عمل کردن به شیوه‌ی عکس به n عدد ۱ می‌رسیم. به این منظور n عدد n را دو به دو در نظر گرفته و اعداد تولید کننده‌ي آن‌ها را می‌نویسیم. اگر n فرد باشد یک عدد n باقی‌ مانده و هرگز از آن ۱ تبدیل نخواهد شد. پس شرط لازم برای رسیدن به مطلوب آن است که n زوج باشد. برای n=16 شیوه‌ی زیر را عمل می‌کنیم:

  • ابتدا ۱۶ عدد را دوبه‌دو در نظر گرفته و آن‌ها را به ۱۶ عدد ۲ و سپس آن‌ها را ۱۶ عدد ۴ و سپس آن‌ها را به ۱۶ عدد ۸ و در نهایت با دسته‌بندی آن اعداد در ۸ زوج دوتایی آن‌ها را به ۱۶ عدد ۱۶ تبدیل می‌کنیم.

ابزار صفحه