المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

۱۵ شتر در یک صف پشت سرهم ایستاده اند. می دانیم که وزن هر شتر عددی طبیعی از ۱ تا ۱۵ است و ممکن است وزن دو شتر یکسان باشد. هر شتر مجموع وزن خود و دو برابر وزن نفر جلویی اش را حساب می کند به جز نفر اول صف که شتری در جلویش نیست. در کمال تعجب شترها متوجه می شوند که همه ی ۱۴ عدد محاسبه شده بر ۱۵ بخش پذیر است. وزن این ۱۵ شتر چند حالت مختلف می تواند داشته باشد؟

  1. $۱۵!$
  2. $۲^{۱۴}$
  3. ۱۵
  4. ۲۲۵
  5. $۱۵^ ۲ - ۱$

پاسخ

گزینه‌ی ۳ درست است.

ادعا می‌کنیم در صورتی که وزن شتر اول مشخص شود، وزن بقیه‌ی شترها به صورت یکتا تعیین می‌شود. برای اثبات این ادعا باید وزن هر شتر را از روی وزن شتر جلوی آن به‌دست آوریم.

فرض کنید که وزن شتر جلویی $i$ باشد. اگر $i$ فرد باشد وزن شتر باید$\frac{15-i}{2}$ و در غیر این صورت باید$\frac{30-i}{2}$باشد.

در نتیجه تعداد کل حالات ۱۵ تاست.

  • نکته: می‌توان همین روند را برای شتر آخر نیز نوشت. سعی کنید وزن شتر $(i-1)$ام را براساس وزن شتر $i$ام به‌دست آورید.

ابزار صفحه