دستگاه برش «الواربر» ابزاری برای برش الوارهای چوبی است. این دستگاه به عنوان ورودی تعدادی الوار هم اندازه‌ي $۱\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$ داریم). در نتیجه ۸ مرحله لازم است.