المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

دور یک دایره، ۳۴ توپ چیده شده است که برخی از آن‌ها قرمز و بقیه آبی هستند. از هر پنج توپ متوالی، دست کم سه توپ رنگ قرمز دارند. بیشینه‌ی ممکن تعداد توپ‌های آبی چیست؟

  1. ۱۶
  2. ۱۲
  3. ۱۴
  4. ۱۳
  5. ۱۵

پاسخ

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

ابتدا ثابت می‌کنیم پاسخ از ۱۳ بیش‌تر نیست. اگر توپ آبی نداشته باشیم که حکم برقرار است. پس یک توپ آبی در نظر بگیرید و با شروع از آن، توپ‌ها را به دسته‌های پنج‌تایی متوالی تقسیم کنید. چهار توپ نیز در انتها باقی می‌ماند که در دسته‌ای قرار نمی‌گیرند. در هر کدام از دسته‌ها حداکثر دو توپ آبی وجود دارد. حال چهار توپ باقی‌مانده را به همراه توپ آبی آغازین در یک دسته‌ی پنج‌تایی بگذارید. نتیجه می‌شود که چهار توپ گفته شده حداکثر یک توپ آبی دارند. پس در کل حداکثر $6\times2+1$ توپ آبی داریم.

حال روشی برای ۱۳ توپ ارائه می‌دهیم. توپ‌ها را به شکل زیر به ترتیب دور دایره بگذارید ($b$ نماد آبی و $r$ نماد قرمز است): $$bbrrrbbrrrbbrrrbbrrrbbrrrbbrrrbrrr$$


ابزار صفحه