استاد شیفو میخواهد یک برنامهی تمرینیِ 12 ساعته برای تقویت عضلات دست و پا طراحی کند. این برنامه بهصورت دنبالهای از بلوکهای تمرینی است. هر بلوک تمرینی، یا مربوط به ورزش دست است یا ورزش پا، و مدت زمان آن نیز بر حسب ساعت، عددی طبیعی است. مثلا یک بلوک تمرینی میتواند از 3 ساعت تمرین پا تشکیل شده باشد. استاد شیفو به این نتیجه رسیده است که یک برنامهی تمرینی مناسب، دارای شرایط زیر است:
شکل زیر نمونهای از یک برنامهی تمرینی با شرایط مذکور را نشان میدهد. چند برنامهی تمرینیِ 12 ساعته وجود دارد که از نظر استاد شیفو مناسب باشد؟ دو برنامهی تمرینی، متمایز محسوب میشوند اگر زمانی (در طولِ 12 ساعت) وجود داشته باشد که در یک برنامه، برای آن زمان، ورزشِ دست تعیین شده باشد، و در برنامهی دیگر، برای آن زمان، ورزشِ پا تعیین شده باشد.
پاسخ
گزینه (۳) درست است.
برای حل این مسئله، f(n) را بهعنوان تعداد روشهای ساخت یک برنامهی تمرینی n ساعته تعریف میکنیم. با حالتبندی روی مجموع طول دو بلوک تمرینی اول به بازگشتی زیر میرسیم:
f(n)=n∑k=2f(n−k)⋅⌊k2⌋
چرا که اگر مجموع طول دو بازهی اول k باشد، از آنجایی که بلوک اول باید بزرگتر یا مساوی بلوک دوم باشد، ⌊k2⌋ حالت برای مشخص کردن طولشان وجود دارد. باقی برنامهی تمرینی نیز دارای f(n−k) حالت است.
بهطور مشابه میدانیم:
f(n−1)=n−1∑k=2f(n−1−k)⋅⌊k2⌋
بنابراین میتوانیم بنویسیم:
f(n)=f(n−1)+f(n−2)+f(n−4)+f(n−6)+f(n−8)+…
اگر با استفاده از این ارتباط f(n−2) را بنویسیم، داریم:
f(n−2)=f(n−3)+f(n−4)+f(n−6)+f(n−8)+…
پس به نتیجه میرسیم که:
f(n)=f(n−1)+2f(n−2)−f(n−3)
و همچنین داریم:
f(1)=0,f(2)=1,f(3)=1
با استفاده از رابطهی بازگشتی به دست آمده، f(12) را به شکل زیر محاسبه میکنیم:
f=0,1,1,3,4,9,14,28,47,89,155,286.
بنابراین تعداد برنامههای تمرینی 12 ساعته که متناسب با شرایط مورد نظر استاد شیفو است، همان 286 میباشد.