تخته شکلاتی به صورت یک جدولی $2×n$ داریم که از $۲n$ تکه شکلات واحد متمایز ساخته شده است. این شکلات، بسته بندی نشده است و هدف، بسته بندی آن است. دو سبد داریم؛ سبد ۱ سبد شکلاتهای بسته بندی نشده و سبد ۲، سبد شکلاتهای بسته بندی شده است. در ابتدا شکلات $2×n$ ما در سبد ۱ قرار دارد.
در هر مرحلهیکی از شکلاتهای سبد ۱ برداشته میشود، سپس یک سطر یا یک ستون آن به طور کامل از شکلات جدا شده و به عنوان یک بسته، در سبد قرار میگیرد. چنان چه از شکلات برداشته شده از سبد ۱ چیزی باقی بماند (یک یا دو تکه)، این تکه ها به سبد ۱ برگردانده میشوند.
مراحل تا زمانی که تمام شکلات ها بسته بندی شوند، ادامه مییابد. به دو حالت از بسته بندی متفاوت گوییم، اگر در انتها دو تکه شکلات واحد وجود داشته باشند که در یک بسته بندی، در یک بسته باشند و در بسته بندی دیگر، در یک بسته نباشند. تعداد حالتهای مختلف بسته بندی را $f(n)$ می نامیم. برای مثال $f(2)=6$ و $f(3)=18$ است.
آ) ثابت کنید $f(n) \in O(3^n)$ است (۴۰ امتیاز)
ب) ثابت کنید $f(n) \in \Omega(2.5^n)$ است (۶۰ امتیاز)
نکته: در صورتی که نتوانستید قسمت (ب) را به صورت کامل حل کنید، در صورتی که نشان دهید $f(n) ∈ Ω(5^{\frac{n}{2}})$ میتوانید ۴۰ امتیاز دریافت کنید.
راهنماییهای بخش الف
راهنمایی
ابتدا فکر کنید شکل قطعات بستهبندی شده در شکلات اولیه به چه صورت است.
راهنمایی
هر بسته بندی از یک تکهی افقی از سطر اول، یک تکهی افقی از سطر دوم، یا یک ستون عمودی تشکیل شده است.
راهنمایی
فرض کنید در یک بستهبندی نهایی، مجموعهی $S \in \{1, 2, \dots, n\}$ ستونهایی باشد که در بستهبندی نهایی آمدهاند. مستطیلهای بین این ستونها به چه صورت بستهبندی شده است؟
راهنمایی
چون در این مستطیلها، هیچ ستونی به شکل کامل در بستهبندی نیامده، پس برش اول آنها را به دو سطر تبدیل کرده و یکی از این دو سطر را بستهبندی کرده است.
راهنمایی
اگر این مسطیل $a\times b$ باشد، حداکثر $2^{b-1}$ حالت مختلف برای بستهبندی آن وجود خواهد داشت.
راهنمایی
بر اساس تعداد اعضای $S$، یک عبارت غیر صریح برای محاسبهی حداکثر تعداد بستهبندیها از روی راهنمایی بالا بسازید.
راهنمایی
عبارت غیر صریح راهنمایی فوق: \[ \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} \]
راهنمایی
از بسط دوجملهای برای یافتن مقدار صریح این عبارت استفاده کنید.
راهنمایی
\[ \sum_{k=0}^{n} \binom{n}{k} 2^{n-k} = (1+2)^n = 3^n \]
راهنماییهای بخش ب
راهنمایی
سعی کنید خانوادهای بزرگ از مثالهای بستهبندی ارائه دهید تا حکم ثابت شود.
راهنمایی
سعی کنید رابطه بازگشتیای برای شمارش بخشی از بستهبندیهای مطلوب پیدا کنید.
راهنمایی
تعداد دستهبندیها را برای شکلاتهای $2\times 1$، $2 \times 2$، $2 \times 3$ و $2 \times 4$ حساب کنید.
راهنمایی
به کمک محاسبات بخش قبل، در رابطه بازگشتی بر کجا بودن ستون اولی که به عنوان یک تکهی جدا بستهبندی شده حالتبندی کنید.
راهنمایی
تنها حالاتی را در نظر بگیرید که اولین ستون بستهبندی شده، یکی از ۵ ستون اول باشد.
راهنمایی
اگر $B_n$ را رابطه بازگشتی به تعریف راهنماییهای بالا بگیریم، داریم $B_n = B_{n-1}+B_{n-2}+3B_{n-3}+7B_{n-4}+13B_{n-5}$
راهنمایی
به استقرا ثابت کنید $B_n \ge c (\frac{5}{2})^n$ و یک $c$ مطلوب بیابید.
راهنمایی
چون $f(n) \ge B_n$ پس حکم ثابت میشود.