Paying everything

The trick to paying the least number of coins for a natural number payment $p$ is to pay with the higher value coins first. For example, if $p=\$57$ , we pay with $\left(\left \lfloor \frac {\$57}{\$10} \right \rfloor = \right) 5 \times \$10$ coins first. The remainder $\$7$ , we pay with $\left(\left \lfloor \frac {\$7}{\$5} \right \rfloor = \right) 1 \times \$5$ coin first and then the remainder with $1 \times \$2$ coin. Or $p=\$57 = 5(\$10) + 1(\$5) + 1(\$2)$ . Any other ways of paying for $\$57$ will require more coins.

Now define the combination of coins for the least number of coins to be $c \left(n_{\$10}, n_{\$5}, n_{\$2}, n_{\$1}\right)$ , for example $c(\$57) = (5,1,1,0)$ . With this in mind, it is obvious that:

$\begin{array} {lll} c(\$1) = (0,0,0,1) & \implies c(\$(10n+1)) = (n,0,0,1) & \small \blue{\text{where }n \in \mathbb N} \\ c(\$2) = (0,0,1,0) & \implies c(\$(10n+2)) = (n,0,1,0) \\ c(\$3) = (0,0,1,1) & \implies c(\$(10n+3)) = (n,0,1,1) \\ c(\$4) = (0,0,2,0) & \implies c(\$(10n+4)) = (n,0,2,0) \\ c(\$5) = (0,1,0,0) & \implies c(\$(10n+5)) = (n,1,0,0) \\ c(\$6) = (0,1,0,1) & \implies c(\$(10n+6)) = (n,1,0,1) \\ c(\$7) = (0,1,1,0) & \implies c(\$(10n+7)) = (n,1,1,0) \\ c(\$8) = (0,1,1,1) & \implies c(\$(10n+8)) = (n,1,1,1) \\ c(\$9) = (0,1,2,0) & \implies c(\$(10n+9)) = (n,1,2,0) \end{array}$

And $c(\$10n) = (n,0,0,0)$ . To pay for $\$1$ to $\$99$ , we need $\left(\max(n_{\$10}) = \right) 9 \times \$10$ coins, $\left(\max(n_{\$5}) = \right) 1 \times \$5$ coin, $\left(\max(n_{\$2}) = \right) 2 \times \$2$ coins, and $\left(\max(n_{\$1})=\right) 1 \times \$1$ coin. But when we add up $9(\$10)+1(\$5)+2(\$2)+1(\$1) = \$100$ . Therefore, to pay for $\$1$ to $\$100$ without a change we only need $\boxed{13}$ coins, nine $\$10$ , one $\$5$ , two $\$2$ , and $\$1$ .

To buy the gift of cost $1, $2, $3, $4 Sam must have either 1 $1 coin and 2 $2 coins or 2 $1 coins and 1 $2 coins. First choice is better because if taken all together it will sum up to 5 which can be used to decrease the number of $5 coins by 1.

Now we see that if we are able to sum up to any multiple of 5, then we can get any whole number using 1 $1 coin and 2 $2 coins. Now we don't need any more $1 coin and $2 coins.

Now we have to get multiple of 5 using $10 coins and $5 coins. Obviously these coins will give multiple of 5 but it should as much to get sum of 95. To get least amount of coin we use more of $10 coins and least of $5 coins.

95 = 9 $10 coins + 1 $5 coin. This combination has least number of coins. Hence Sam must have 1 $1 coin, 2 $2 coins, 1 $5 coin and 9 $10 coins with a total of 13 coins.