Sztabka srebra

Poszukiwacz srebra nie był w stanie zapłacić czynszu za marzec, na początku miesiąca. Posiadał jednak sztabkę czystego srebra o długości 31 cali. Postanowił więc dogadać się  z właścicielką mieszkania proponując umowę. Mógłby pociąć sztabkę na mniejsze kawałki. Pierwszego dnia marca dałby właścicielce jeden cal długości sztabki i każdego następnego dnia dawałby kolejne. Ona trzymała by te kawałki jako zabezpieczenie. Na koniec miesiąca poszukiwacz byłby w stanie zapłacić czynsz a właścicielka zwróciłaby mu jego sztabkę w kawałkach.

Marzec ma 31 dni, dlatego jeden sposób to pocięcie sztabki na 31 kawałków każdy o długości 1 cala. Poszukiwacz chciałby jednak ograniczyć do minimum ilość niezbędnych cięć sztabki (ilość kawałków na które należy pociąć sztabkę). Na przykład może on dać właścicielce kawałek o długości 1 cala jednego dnia, kolejny 1 cal długości drugiego dnia, a trzeciego dnia mógłby zabrać od właścicielki te dwa dane jej wcześniej kawałki dając jej w zamian kawałek srebra o długości 3 cali, itd.

Taka forma wymiany kawałków srebra miedzy właścicielką a poszukiwaczem umożliwi ograniczenie ilości cięć sztabki srebra. Zadanie polega na określeniu najmniejsze ilości kawałków na które należy pociąć sztabkę srebra, aby zagwarantować przekazywanie każdego dnia marca kolejnych cali sztabki srebra.