المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۷

تعداد رشته‌های ۱۰ تایی از ارقام را بیابید که در هر یک از آن رشته‌ها هر رقم برابر با تعداد رقم‌های صفر مجاورش باشد.

  1. ۱۰
  2. ۱۴
  3. ۱۶
  4. ۲۰
  5. ۲۲

راهنمایی

روی تعداد صفرها حالت‌بندی کنید.

راهنمایی

فرض کنید می‌دانیم عدد مورد نظر $k$ رقم صفر دارد. صفر‌ها را ثابت در نظر بگیرید و سعی کنید رقم‌های یک را میان آن‌ها قرار دهید.

پاسخ

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

چند لم برای سادگی در زیر آمده است که اثبات آنها دشوار نیست.

  • لم ۱: هر رقم صفر یا یک یا دو است.
  • لم ۲: دو صفر مجاور نداریم.
  • لم ۳: مجاور رقم ۲ حتما صفر است.
  • لم ۴: بین هر ۳ رقم متوالی حداقل یکی صفر است.
  • لم ۵: اگر جایگاه صفرها با خاصیت لم ۲ و ۴ مشخص شود، بقیه‌ی ارقام به طور یکتا به دست می آید.
  • لم ۵: به ۱۶ طریق می‌توان جایگاه صفرها را بنا بر لم ۲ و ۴ مشخص کرد.

پس پاسخ ۱۶ است.


ابزار صفحه