دستگاه برش «الواربر» ابزاری برای برش الوارهای چوبی است. این دستگاه به عنوان ورودی تعدادی الوار هم اندازه‌ی $۱\times n$ و یک عدد $k$ (کوچکتر از $n$ و بزرگتر از صفر) را می‌گیرد. سپس به طور همزمان و با یک برش عظیم هرکدام از الوارها را به دو تکه با اندازه‌های $۱\times k$ و $۱ \times (n-k)$ تبدیل می‌کند. برای مثال می‌توانیم به این دستگاه سه الوار $۱ \times ۵ $ بدهیم تا در یک حرکت آن ها را به سه تکه‌ی $۱ \times ۱ $ و سه تکه‌ی $۱ \times ۴ $ تبدیل کند.
سهراب یک الوار چوبی $۱ \times ۱۰۰ $ به عنوان کادوی تولد از رستم هدیه گرفته است! او می‌خواهد با کمترین تعداد دفعه استفاده از دستگاه٬ این الوار طویل را به ۱۰۰ تکه‌ی ٰ$۱ \times ۱ $ تبدیل کند. کمترین تعداد دفعه استفاده از دستگاه برای این منظور چند است؟
دقت کنید که همه‌ی الوارهای ورودی به دستگاه در یک مرحله٬ باید با هم هم‌اندازه باشند.
پاسخ
گزینه‌ی «۲» درست است.
$100*1 \rightarrow 50*2\rightarrow 25*4 \rightarrow 12*4 + 13*4 \rightarrow 12*8 +1*4\rightarrow 6*16+1*4\rightarrow 3*32+1*4 \rightarrow$
$2*32+1*36 \rightarrow 1*100$
($x*y$ یعنی $x$ چوب به طول $y$ داریم). در نتیجه ۸ مرحله لازم است.