Question: You hire a man to work in your yard for $n$ days, where $n$ is a positive integer. You wish to pay him in gold. You have one gold bar with $n$ parts—like a chocolate bar. You wish to pay him one gold part per day. If you may snap the bar at anywhere, what is the smallest number of pieces that you should snap into so that on successive days he may use what you paid him previously to make change? If it cannot be done, find such set of $n.$
The classic puzzle is for $n=7$ where we snap the bar into $3$ parts with $1,2,4$ respectively.
It turns out that if $n = 2^m-1$ for some integer $m,$ then we can always snap the bar into $m$ parts with $2^0, 2^1, 2^2,...,2^m$ respectively to pay the man.
I am not sure about other $n$ though.
For other numbers, the minimum number of pieces he can break the gold bar into is $$\lceil \log_2(n + 1) \rceil$$ To show that we at least this many, note that the highest number we can get with $m$ pieces (of any size) is $2^m - 1$. To show that this many pieces work, consider the pieces of lengths $$1, 2, 4, \dots, 2^{\lfloor \log_2(n + 1) \rfloor - 1}, n - 2^{\lfloor \log_2(n + 1) \rfloor}$$ (I.e. We split up the bar into powers of two and then look at what is left.)