سوال ۱۰

در ابتدا یک باکتری و یک لانه داریم. در هر مرحله هر باکتری می‌تواند یکی از دو کار زیر را انجام دهد:

توجّه کنید در یک مرحله، در هر لانه حداکثر یک باکتری می‌تواند قرار بگیرد و تکثیر شود. پس از هفت مرحله، بیشینه‌ی ممکن تعداد باکتری‌ها چیست؟

  1. ۲۹
  2. ۲۶
  3. ۳۲
  4. ۳۶
  5. ۳۴

پاسخ

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

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