المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

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

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

راهنمایی

ابتدا مثال‌های ساده را در نظر گیرید که تعداد‌ ‌توپ‌های آبی را بیشینه کند.

راهنمایی

در راستای راهنمایی قبل، مثالی با ۱۳ توپ آبی بیابید.

راهنمایی

برای اثبات بیشینه بودن عدد ۱۳، لحاظ کنید برای هر پنج‌ توپ متوالی نیاز به حداقل سه توپ قرمز است و هر توپ قرمز را حداقل پنج بار در این راه می‌شماریم.

راهنمایی

در راستای راهنمایی قبل، نیاز به حداقل $\frac{3 * 34}{5}$ توپ قرمز داریم که این مقدار بیشتر از ۲۰ است.

پاسخ

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

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

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


ابزار صفحه