سوال ۱۰

گزینه (۵) درست است.

ابتدا ثابت می‌کنیم الگوریتم بهینه این است که در هر مرحله تا جای ممکن باکتری‌ها درون لانه‌ها بروند و تکثیر شوند و باکتری‌های باقی‌مانده لانه بسازند. فرض کنید این الگوریتم بهینه نباشد. الگوریتم بهینه را در نظر بگیرید و آن را $A$ بنامید. مرحله‌ای مانند $L$ در $A$ وجود دارد که در آن لانه‌ی خالی وجود دارد و باکتری‌ای مانند $B$ اقدام به ساختن لانه کرده است. دو حالت داریم:

1. اگر در ادامه‌ی الگوریتم $A$ در هیچ مرحله‌ای از تمام لانه‌ها استفاده نشد، باکتری $B$ می‌توانست در مرحله‌ی $L$ به لانه‌ی خالی رفته و تکثیر شود و در انتها تعداد بیش‌تری باکتری داشتیم که تناقض است.
2. اگر در ادامه‌ی الگوریتم $A$ در مرحله‌ای از تمام لانه‌ها استفاده شد، نخستین مرحله‌ی این‌چنینی را در نظر گرفته و $L'$ بنامید. باکتری $B$ می‌توانست در مرحله‌ی $L$ به یک لانه‌ی خالی رفته و تکثیر شود و در مرحله‌ی $L'$ لانه بسازد. در این صورت تعداد لانه‌ها و باکتری‌ها پس از $L'$ از حالت قبل کم‌تر نیست. حال دوباره اگر مرحله‌ای مانند $L$ وجود داشت مانند روش گفته شده الگوریتم را تغییر می‌دهیم و در انتها به الگوریتم خودمان می‌رسیم.

پس در هر صورت الگوریتم ما بهینه است. حال اگر طبق الگوریتم ما عمل کنیم، در هر مرحله تعداد باکتری‌ها به اندازه‌ی تعداد لانه‌ها زیاد و تعداد لانه‌ها برابر با تعدادی باکتری‌های مرحله‌ی قبل می‌شود. پس اگر تعداد باکتری‌ها در مرحله‌ی $n$ ام را $a_n$ بگیریم، داریم: $$a_n = a_{n-1}+a_{n-2}$$ با توجّه به این که $a_0=1$ و $a_1=2$ پاسخ برابر $a_7=34$ خواهد بود.