Lemma:If $n$ is a positive integer, then $n$ cents in change using quarters, dimes, nickels, and pennies using the fewest coins possible has at most two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels, and pennies cannot exceed 24 cents.
I am trying to understand this proof and tried to prove it by contradiction following the book's proof , but I am unable to fully understand the gist behind the proof.
Proof by Contradiction: the negation of conditional statement is: if $p \wedge \sim q$. We need to show that $\sim(p\rightarrow q) \equiv (p \wedge \sim q)$ is true otherwise original assumption is true.
In this proof:
- $p$: in this proof is statement "$n$ is a positive integer".
- $q$: $n$ cents in change using quarters, dimes, nickels, and pennies using the fewest coins possible has at most two dimes, at most one nickel, at most four pennies, and cannot have two dimes and a nickel. The amount of change in dimes, nickels, and pennies cannot exceed 24 cents.
Now, the proof proceeds as follow: We note that if we had three dimes we could replace them with a quarter and a nickel, if we had two nickels we could replace them with a dime, if we had five pennies we could replace them with a nickel, and if we had two dimes and a nickel we could replace them with a quarter. Because we can have at most two dimes, one nickel, and four pennies, but we cannot have two
dimes and a nickel, it follows that 24 cents is the most money we can have in dimes, nickels,
and pennies when we make change using the fewest number of coins for $n$ cents.
We assume in the proof that we can have more coins of each denomination (quarter, nickel, etc.), then we can get change with fewer coins. So the proof proceeds and then reached to conclusion that, "because we can have at most …", which I don't understand given that we assumed we have more of each denomination.
Can you please rephrase the proof or correct my understanding of it in simple words?
Best Answer
If you change $p$ to "$n$ cents has been changed into quarters, dimes, nickels, and pennies using the fewest coins possible," and $q$ to "at most two dimes, at most one nickel, at most four pennies have been used, and two dime and a nickel have not been used," I think you'll see it.