یک جدول ‎$n\times n$‎ داریم که ‎$k$‎ خانه‌ی آن رنگ شده است. می‌خواهیم چند خانه‌ی دیگر را رنگ کنیم تا خانه‌های رنگ شده یک ناحیه‌ی همبند بسازند.

1. ثابت کنید همیشه می‌توان این کار را انجام داد به‌طوری که در انتها تعداد خانه‌های رنگ شده، از ‎$O(n * \sqrt{k})$‎ باشد.
2. ثابت کنید که به ازای هر ‎$k$‎ می‌توان طوری ‎$k$‎ خانه از یک جدول ‎$n\times n$‎ را رنگ کرد که اگر بخواهیم با رنگ کردن چند خانه‌ی جدید، آن‌ها را همبند کنیم، در انتها از ‎$\Omega(n * \sqrt{k})$‎ خانه‌ی رنگ شده خواهیم داشت. ‎

• سوال بعد