a bit of greedy: UVa 10670 - Work Reduction

Problem Statement:
UVa 10670 - Work Reduction

Summary:
We want to transform an integer N into integer M. Then we are given 2 operations:
1. \( N \mapsto N-1\), with cost \(A\)
2. \( N \mapsto \frac{N}{2} \) (round down), with cost \(B\)
What is the lowest cost?

Solution:
Naturally there is a greedy scheme to follow:
1. If we can divide by 2, take \(min \{ A \lceil \frac{N}{2} \rceil, B \} \)
2. If cannot, use operation 1 for the remaining steps

Proof?

I was exploring on the maths for a bit, for the case \(N = 2^k\) and \(2^{k-2} < M < 2^{k-1}\), I get this results...

Suppose we do a few operation 1 (\(x\) times) and then do operation 2. We will end up with \(2^k \mapsto 2^k-x \mapsto \lfloor \frac{2^k-x}{2} \rfloor\). Meanwhile, if we follow greedy scheme, we have \(2^k \mapsto 2^{k-1}\) instead.  I will call the former "deviation" from greedy scheme. Then I observe that greedy scheme actually stays ahead of the deviation. If I take \(  \lfloor \frac{2^k-x}{2} \rfloor \) as the "rendezvous" point, we have 2 costs:
By deviation: \(C' = xA + min \{ A \lceil \frac{2^k-x}{2} \rceil, B \} \)
By greedy scheme: \(C = min \{ 2^{k-1}A, B \} + x'A\)  where \(2^{k-1}-x' = \lfloor \frac{2^k-x}{2} \rfloor \)
Now, if \(x\) even, we have \(x' = \frac{x}{2}\), while when \(x\) is odd, we have \(x' = \frac{x+1}{2}\). Hence we can say \(x' \geq \frac{x}{2}\), and also \(x \geq x' \) for all \(x \geq 1\).
We have to check the following cases:

Case 1: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A > B\)
Then \( C' = xA + B \geq x'A + B = C \). Hence greedy scheme is at least equal, and at best cost less than the deviation.

Case 2: if \( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A > B\)
\(C' = xA + \lceil \frac{2^k-x}{2} \rceil A = xA + (2^k - x - 2^{k-1}+x')A\)
\(C' = x'A + A2^{k-1} > x'A + B = C\) again!

Case 3: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A < B\)
This is impossible by the love of God

Case 4: if\( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A < B\)
then C = C' by simple algebra.

Yay then I can say that the greedy scheme actually stays ahead once there is a deviation from the scheme as we can always reach the state at at worst equal cost to the one resulting from the deviation :D

But for the case in general.. no idea yet

Now.. that's why people always ponder upon the paradox of why such a simple greedy algorithm can actually be so complicated.. A facade of all facades