Question #10058

prove that the any restaurant bill of $n,n>or=5 be paid exactly using only $2 and $5 bills

Expert's answer

Using an induction.

Base: n=5$ it's okay.

Claim: n=k statement is held.

Check: n=k+1

k+1=k-5+6=k-5+2+2+2 (to pay this bill we used 1 5$ bill less and 3 2$ bills more, than before)

If none 5$ bills were used, than k+1=k-4+5=k-2-2+5 (we use 2 2$ bills less and 1 5$ bill more)

So, anyway, we used only 2$ and 5$ bills.

Base: n=5$ it's okay.

Claim: n=k statement is held.

Check: n=k+1

k+1=k-5+6=k-5+2+2+2 (to pay this bill we used 1 5$ bill less and 3 2$ bills more, than before)

If none 5$ bills were used, than k+1=k-4+5=k-2-2+5 (we use 2 2$ bills less and 1 5$ bill more)

So, anyway, we used only 2$ and 5$ bills.

## Comments

## Leave a comment