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

در ابتدا یک باکتری و یک لانه داریم. در هر مرحله هر باکتری می‌تواند یکی از دو کار زیر را انجام دهد:
  * یک لانه بسازد.
  * درون یک لانه‌ی خالی برود و تکثیر شود؛ یعنی به دو باکتری تبدیل شود.
توجّه کنید در یک مرحله، در هر لانه حداکثر یک باکتری می‌تواند قرار بگیرد و تکثیر شود. پس از هفت مرحله، بیشینه‌ی ممکن تعداد باکتری‌ها چیست؟
  - ۲۹
  - ۲۶
  - ۳۲
  - ۳۶
  - ۳۴


<پاسخ>
گزینه (۵) درست است.


ابتدا ثابت می‌کنیم الگوریتم بهینه این است که در هر مرحله تا جای ممکن  باکتری‌ها درون لانه‌ها بروند و تکثیر شوند و باکتری‌های باقی‌مانده لانه بسازند. فرض کنید این الگوریتم بهینه نباشد. الگوریتم بهینه را در نظر بگیرید و آن را $A$ بنامید. مرحله‌ای مانند $L$ در $A$ وجود دارد که  در آن لانه‌ی خالی وجود دارد و باکتری‌ای مانند $B$ اقدام به ساختن لانه کرده است. دو حالت داریم:
  - اگر در ادامه‌ی الگوریتم $A$ در هیچ مرحله‌ای از تمام لانه‌ها استفاده نشد، باکتری $B$ می‌توانست در مرحله‌ی $L$ به لانه‌ی خالی رفته و تکثیر شود و در انتها تعداد بیش‌تری باکتری داشتیم که تناقض است.
  - اگر در ادامه‌ی الگوریتم $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$
خواهد بود.


</پاسخ>
  * [[سوال ۹|سوال قبل]]
  * [[سوال ۱۱|سوال بعد]]