فرض کنید ‎$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}‎$ تجاوز نمی‌کند.

• سوال قبل