المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

روی محور اعداد حقیقی ۱۳۹۲ نقطه‌ی رنگی متمایز داده شده است که هر یک با یکی از ۹۲ رنگ موجود رنگ شده‌اند. یک بازه را «مینیمال رنگی» می‌گوییم اگر همه‌ی رنگ‌ها را پوشش دهد (یعنی از هر رنگی حداقل یک نقطه داخل آن باشد) و هیچ زیربازه‌ای از این بازه، همه‌ی رنگ‌ها را پوشش ندهد. حداکثر تعداد بازه‌های مینیمال رنگی چند تا است؟

  1. ۹۲
  2. ۱۳۹۱
  3. ۱۳۰۱
  4. ۹۱
  5. ۱

پاسخ

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

اگر n نقطه داشته باشیم که با یکی از k رنگ، رنگ شده باشند، جواب n-k+1 خواهد شد. با توجه به تعریف بازه‌ی مینیمال رنگی، هیچ دو بازه‌ی مینمال رنگی نقاط انتهایی یکسان ندارند. بنابراین هر بازه‌ی رنگی را می‌توان با نقطه‌ی شروع آن به طور یکتا مشخص کرد. در ضمن نقطه‌ی شروع بازه‌ی مینیمال رنگی نمی‌تواند بین k-1 نقطه‌ی پایانی باشد چرا که هر بازه‌ی مینیمال رنگی حداقل باید شامل k نقطه باشد. در نتیجه تعداد چنین بازه‌هایی n-k+1 خواهد شد. مثالی که دقیقا این تعداد بازه‌ی مینیمال رنگی داشته باشد دنباله‌ی متناوب زیر است که هر رنگ با یکی از اعداد 1 تا k نمایش داده شده است:

$$1, 2, \ldots, k, 1, 2, \ldots, k, 1, 2, \ldots, k, \ldots $$


ابزار صفحه