There's the famous "Poison and Mouse" problem that uses the binary search approach to solve. Here's another optimisation problem.
QUESTION : Consider a bacteria that grows by $1$ unit at night and splits into half its size (for even sizes) during the daytime if it wishes. During the daytime, it may split more than once as well- for example, a size $20$ bacteria can either result into $(10,10)$ bacteria during the daytime or it may also result into $(10,5,5)$ or $(5,5,5,5)$ as per its will. It may choose not to split during the day in fact, i.e, a size 20 bacteria may remain as a $20$ sized bacteria throughout the day. For an $n$-sized bacteria, find the minimum time required to break into bacteria each of size $1$ and find the total number of such unit bacteria at the end given that the n-sized bacteria starts in the morning of January 1.
Now, I am trying to minimise the value but how do I know if this is the minimum time required? How do we determine that? What I have thought is to let the n-sized bacteria can increase by 1 at night, if it's odd, else, divide into $r$ bacteria of $k$ size each, where $k$ is odd (assuming $n=k \cdot 2^r$). Now, $k<n$ and we know the minimum time required by $k$, so, we can just do that. Now, I'm assuming that it's some form of recursion or induction if there's any closed form of what I said. I'm not really sure if that's the minimum time required or not. I'm just guessing that it might be the minimum time. But how do we prove that some algorithm will actually be the minimum?