المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

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

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

۱)۱۵ $\quad$ $\quad$ ۲)۱۶ $\quad$ $\quad$ ۳)۹

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

پاسخ

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

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

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

ابزار صفحه