سوال ۳

تخته شکلاتی به صورت یک جدولی $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}})$ می‌توانید ۴۰ امتیاز دریافت کنید.