المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

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

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

راهنمایی

اگر وزن یک شتر مشخص باشد، وزن شتری که پشت آن قرار دارد چه مقادیری می‌تواند داشته باشد؟

راهنمایی

اگر وزن شتری که در ابتدای صف قرار دارد مشخص باشد، وزن کدام شتر‌ها به طور یکتا تعیین می‌شود؟

پاسخ

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

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

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

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

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

ابزار صفحه