فرض کنید $n,[x_1,y_1 ],[x_2,y_2 ],⋯,[x_n,y_n]$ بازه‌ روی محور اعداد حقیقی باشند. می‌خواهیم این بازه‌ها را با تعدادی رنگ که هر رنگ با یک عدد طبیعی شناخته می‌شود، رنگ‌آمیزی کنیم.

در یک رنگ‌آمیزی، $f(x)$ را برابر بزرگترین رنگ بازه‌ها بین بازه‌هایی که شامل نقطه‌ی $x$ می‌شوند، تعریف می‌کنیم. بدیهی است که $f(x)$ فقط برای نقاطی که حداقل درون یک بازه قرار دارند تعریف می‌شود. به‌یک رنگ‌آمیزی زیبا می‌گوییم، اگر برای هر نقطه مثل $x$ روی محور اعداد حقیقی که حداقل درون یک بازه قرار دارد، دقیقا یک بازه با رنگ $f(x)$ شامل نقطه‌ی $x$ شود.

ما در ابتدا همه‌ی بازه‌ها را در اختیار نداریم و بازه‌ها یکی یکی در اختیار ما قرار می‌گیرند. به محض آنکه‌یک بازه را دریافت کردیم باید یک رنگ به آن اختصاص دهیم و مجاز به تغییر آن در آینده نیستیم. از روش زیر برای رنگ‌آمیزی بازه‌ها استفاده می‌کنیم:

فرض کنید بازه $v$ را دریافت کرده باشیم. رنگ‌های ۱,۲,۳,⋯را به ترتیب از کوچک به بزرگ امتحان می‌کنیم تا به اولین رنگی برسیم که اگر آن رنگ را به بازه‌ی $v$ اختصاص بدهیم، رنگ‌آمیزی زیبا بماند. (با توجه به محدود بودن تعداد بازه‌ها، چنین رنگی حتما وجود دارد.( بازه‌ی $v$ را با آن رنگ، رنگ می‌کنیم و به سراغ بازه‌ی بعد می‌رویم و تا آخرین بازه همین روند را انجام می‌دهیم.

الف) فرض کنید $i$امین بازه‌ای که دریافت می‌کنیم $[x_i,y_i]$ باشد و در ضمن بدانیم $x_1\lt x_2 \lt ⋯ \lt x_n$ و $y_1 \lt y_2\lt ⋯ \lt y_n$. نشان دهید بعد از دریافت $n$ بازه، تعداد رنگ‌های استفاده شده، از $log_2{n + 1}$ تجاوز نمی‌کند.

ب) با فرض آنکه بازه‌ها دلخواه باشند و با یک ترتیب دلخواه بازه‌ها را دریافت کنیم، نشان دهید بعد از دریافت n$$ بازه، تعداد رنگ‌های استفاده شده، از $۳\sqrt{n}$ تجاوز نمی‌کند.