سوال ۱۰

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

برای حل این مسئله، $f(n)$ را به‌عنوان تعداد روش‌های ساخت یک برنامه‌ی تمرینی $n$ ساعته تعریف می‌کنیم. با حالت‌بندی روی مجموع طول دو بلوک تمرینی اول به بازگشتی زیر می‌رسیم:

$$f(n) = \sum_{k=2}^{n} f(n-k) \cdot \left\lfloor \frac{k}{2} \right\rfloor$$

چرا که اگر مجموع طول دو بازه‌ی اول $k$ باشد، از آنجایی که بلوک اول باید بزرگ‌تر یا مساوی بلوک دوم باشد، $\left\lfloor \frac{k}{2} \right\rfloor$ حالت برای مشخص کردن طولشان وجود دارد. باقی برنامه‌ی تمرینی نیز دارای $f(n-k)$ حالت است.

به‌طور مشابه می‌دانیم:

$$f(n-1) = \sum_{k=2}^{n-1} f(n-1-k) \cdot \left\lfloor \frac{k}{2} \right\rfloor$$

بنابراین می‌توانیم بنویسیم:

$$f(n) = f(n-1) + f(n-2) + f(n-4) + f(n-6) + f(n-8) + \ldots$$

اگر با استفاده از این ارتباط $f(n-2)$ را بنویسیم، داریم:

$$f(n-2) = f(n-3) + f(n-4) + f(n-6) + f(n-8) + \ldots$$

پس به نتیجه می‌رسیم که:

$$f(n) = f(n-1) + 2f(n-2) - f(n-3)$$

و همچنین داریم:

$$f(1) = 0, \quad f(2) = 1, \quad f(3) = 1$$

با استفاده از رابطه‌ی بازگشتی به دست آمده، $f(12)$ را به شکل زیر محاسبه می‌کنیم:

$$f = 0, 1, 1, 3, 4, 9, 14, 28, 47, 89, 155, 286.$$

بنابراین تعداد برنامه‌های تمرینی $12$ ساعته که متناسب با شرایط مورد نظر استاد شیفو است، همان $286$ می‌باشد.