Problem:
Let $c_1,c_2,...,c_n$ be a (sorted) sequence of coins such that for all $1\leq k<n$ it holds that $\frac{c_{k+1}}{c_k}\in\mathbb{N}$ and $\frac{c_{k+1}}{c_k}>1$.
Devise a greedy method algorithm for a cash register that, given some $x\in\mathbb{N}$, returns a change of $x$ cents to the customer using a minimal amount of coins.
Algorithm
$S=\emptyset$
while (x>0)
2.1. $k=max\{c_i | (1\leq i\leq n)\land (c_i\leq x)\}$
2.2. $x=x-k$
2.3. $S\cup \{k\}$
return $S$
I'm trying to prove the greedy choice property (GCP) of this algorithm but I'm stuck. What I have so far is:
GCP: $\forall x\in\mathbb{N}, 1\leq k<n: (c_k\leq x<c_k+1)\Rightarrow$ (An optimal solution must include $c_k$)
*Edit
Using the proof sketch suggested by @David Clyde as a basis, I was able to prove the GCP. I'm sharing my proof for anyone who might come across this post in the future and require a more rigorous explanation.
I'll start from your attempted proof's setup and notation. I claim that it's possible to sum up to exactly $c_k$ using coins in $B$. That will give the contradiction you need, since you could produce a better solution by swapping those other coins for one $c_k$ coin.
To prove my claim, we can create a new set $S$ by repeatedly adding the largest $c_j$ from $B$ with $1 \le j \le k-1$ that hasn't been added yet. After each step, we check whether the total value of $S$ equals $c_k$.
It's impossible for us to "overshoot the target": if we add a coin $c_j$ then the current total of $S$ must be a multiple of $c_j$ because all larger coin values are multiples of $c_j$. We're guaranteed to make it to the target eventually: in your setup, we specifically assumed that the sum of all smaller coins is $\ge c_k$. So the only remaining option is that this process eventually produces a set $S \subseteq B$ where $S$ sums to exactly $c_k$, which finishes the proof as explained above.