المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

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

  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 $$


ابزار صفحه