====== سوال ۱ ======

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

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

  * [[سوال ۲|سوال بعد]]