0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you. Can you explain the because part? Why we can only have at most 24 cents of dimes, nickels and pennies? Can you rephrase in your own words what the proof is trying to convey? $\endgroup$
    – Avv
    Commented Jan 25, 2021 at 20:51
  • 1
    $\begingroup$ @Avra Everything else would be in quarters. $\endgroup$
    – saulspatz
    Commented Jan 26, 2021 at 1:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .