$m$ آزمایشگر می‌خواهند ارتفاع لازم برای شکستن پا را حساب کنند. برای این کار از یک ساختمان $n$ طبقه بهره جسته‌اند. می‌دانیم از بین این $n$ طبقه، طبقه‌ای وجود دارد که اگر از پنجره‌ی آن طبقه یا طبقات بالاتر به پایین بپرند، پایشان می‌شکند و پریدن از طبقات پایین‌تر، هیچ آسیبی به آن‌ها نمی‌رساند. همچنین اگر پای کسی شکست، چلاق شده دیگر توانایی پریدن ندارد (از دور خارج می‌شود). می‌خواهیم این حداقل ارتفاع را تشخیص دهیم.

مثلا اگر $m=1$، کم‌ترین تعداد پریدن‌هایی که یافتن این ارتفاع را تضمین می‌کند، $n-1$ است. چون این تک نفر تا وقتی پایش نشکسته، باید به ترتیب از طبقات $n-1,…,2,1$‌بپرد.

1. الگوریتمی از مرتبه‌ی چند جمله‌ای بر حسب $m$ و $n$‌ ارائه دهید تا حداقل تعداد پریدن افراد برای مشخص شدن این ارتفاع را بیابید.
2. ثابت کنید اگر $m=2$، حداقل تعداد پریدن افراد برای مشخص شدن این ارتفاع زا $\theta(\sqrt{n})$ است.

• سوال بعد
• سوال قبل