====== سوال ۴ ======

یک جدول $2^n\times 2^n$ داریم که می‌دانیم یک $n$-پاره در درون آن مخفی شده است. یک $n$-پاره یک شکل به هم‌پیوسته با $n$ مربع می‌باشد. نمونه‌ای از یک $8$-پاره در زیر آمده است. دقت کنید که هر مربع $n$-پاره باید با حداقل یکی دیگر از مربع‌های $n$-پاره ضلع مشترک داشته باشد.

{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۱:الگوریتم‌ها:table.png?300 |}}
می‌خواهیم این $n$-پاره را پیدا کنیم، اما تنها می‌توانیم سوالاتی به این شکل بپرسیم: یک زیر مربع را انتخاب کنیم و بپرسیم که آیا یکی از مربع‌های $n$-پاره درون این زیرمربع هست یا نه. الگوریتمی ارائه دهید که با $Ο(n)$ سوال این چندپاره را بیابد.

  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]