Question

3. Suppose that a store offers gift certificates in denominations of 25 dollars and 40 dollars. Determine the possible total amounts you can form using these gift certificates. Prove your answer using strong, induction

Answer 1

Solution:

The amounts seem semi-random:

$25 certificates $40 certificates Total

1                                  0                                  $25

0                                  1                                  $40

2                                  0                                 $50

1                                  1                                  $65

3                                  0                                 $75

0                                  2                                 $80

2                                  1                                 $90

4                                  0                                 $100

1                                  2                                 $105

3                                  1                                 $115

0                                  3                                  $120

5                                  0                                 $125

2                                  2                                 $130

4                                  1                                 $140

1                                  3                                 $145

6                                  0                                 $150

3                                  2                                 $155

0                                  4                                 $160

Horribly enough, that was the base of the induction. We've now exhibited every

possible amount under $160 either up to 6 $25 certificates, or 1 $40 certificates

and up to 4 $25 certificates, or 2 $40 certificates and up to 3 $25 certificates, or 3

$40 certificates and up to 1 $25 certificates, or 4 $40 certificates.

We now claim that every amount divisible by $5 above $140 is available. We'll

use strong induction, on a proposition like this: P(n) is the proposition that the

above amounts and every amount divisible by $5 from $140 up to $140 + $5n can

be formed from the gift certificates. Suppose it's true for all the numbers up to

some n (assumed to be greater than 4, since we proved P(0); P(1); P(2); P(3) and

P(5)above). Since P(n_5) is true, we can add a $25 gift certificates to the method

of making$140 _ $25 + $5n guaranteed by P(n _ 5), and thus create $140 + $5n,

proving P(n). Thus,by strong induction, we can form $25, $40, $50, $65, $75, $80,

$90,$100, $105, $115, $120, $125, $130, and every multiple of $5 from $140 on.

Invalid

0