تخته شکلاتی به صورت یک جدولی $2×n$ داریم که از $۲n$ تکه شکلات واحد متمایز ساخته شده است. این شکلات، بسته بندی نشده است و هدف، بسته بندی آن است. دو سبد داریم؛ سبد ۱ سبد شکلات های بسته بندی نشده و سبد ۲، سبد شکلات های بسته بندی شده است. در ابتدا شکلات $2×n$ ما در سبد ۱ قرار دارد.

در هر مرحله یکی از شکلات های سبد ۱ برداشته می شود، سپس یک سطر یا یک ستون آن به طور کامل از شکلات جدا شده و به عنوان یک بسته، در سبد قرار می گیرد. چنان چه از شکلات برداشته شده از سبد ۱ چیزی باقی بماند (یک یا دو تکه)، این تکه ها به سبد ۱ برگردانده می شوند.

مراحل تا زمانی که تمام شکلات ها بسته بندی شوند، ادامه می یابد. به دو حالت از بسته بندی متفاوت گوییم، اگر در انتها دو تکه شکلات واحد وجود داشته باشند که در یک بسته بندی، در یک بسته باشند و در بسته بندی دیگر، در یک بسته نباشند. تعداد حالت های مختلف بسته بندی را $f(n)$ می نامیم. برای مثال $f(2)=6$ و $f(3)=18$ است.

آ) ثابت کنید $f(n) \in O(n^3)$ است (۴۰ امتیاز)

ب) ثابت کنید $f(n) \in \Omega(2.5^n)$ است (۶۰ امتیاز)

نکته: در صورتی که نتوانستید قسمت (ب) را به صورت کامل حل کنید، در صورتی که نشان دهید $f(n) ∈ Ω(5^{\frac{n}{2}})$ می‌توانید ۴۰ امتیاز دریافت کنید.

• سوال قبل