Exercise 2: Why the Failure Happens at the First Choice — Possible Solution
====================================================================

WHY THE FIRST CHOICE IS WHERE THE DAMAGE HAPPENS
------------------------------
Greedy's algorithm never reconsiders a choice once it's made - each
coin taken permanently reduces the remaining amount, and every later
decision is only ever made in response to whatever remainder is left
over from earlier choices. For amount=6 with denominations {1,3,4},
the very first decision (take the 4) is what PRODUCES the specific
remainder (2) that turns out to be expensive to finish (needing two
separate 1-coins, since 2 cannot be formed from a single coin in this
denomination set). Every subsequent choice in this chapter's own trace
(1, then 1) is actually locally correct GIVEN that remainder - the
algorithm isn't making bad decisions later on, it's correctly finishing
off a remainder that was already a bad one to be left with. The
failure is fully determined by the first step, because that step is
what committed the algorithm to the specific sub-problem (making
change for 2) that has no efficient solution.

WHAT WOULD NEED TO BE TRUE TO PREVENT THIS KIND OF FAILURE
------------------------------
This kind of failure happens because taking the single largest coin
that fits can leave a remainder that is disproportionately expensive
to complete using the remaining coins. For this to never happen, the
denomination set would need the property that greedily removing the
largest available coin always leaves a remainder that can still be
completed just as efficiently as any other combination could have -
informally, each denomination needs to be "well spaced" relative to
the others (this chapter noted standard currency systems like US
coins happen to have this property, without proving why in general).
The {1,3,4} set specifically lacks this property because there is a
"gap" - after removing a 4, a remainder of exactly 2 has no direct coin
and no combination smaller than two separate unit coins, whereas a
denomination set without such gaps (like {1,3,4} replaced with, say,
{1,2,4}) wouldn't create the same trap.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation identifies specifically why the first choice - not a
later one - is causally responsible for the failure (because it
determines which remainder every subsequent, locally-correct choice
has to work with), and gives an honest, chapter-consistent answer to
the second part (a structural, "no expensive gaps" property) without
overclaiming a rigorous formal proof, which this chapter explicitly
deferred to a more advanced algorithms course.