Question

The Martian monetary system uses colored beads instead of coins. A blue bead is worth 3 Martian credits, and a red bead is worth 7 Martian credits. Thus, three blue beads are worth 9 credits, and a blue and red bead together are worth 10 credits, but no combination of blue and red beads is worth 11 credits. Using Induction, prove that for all n ≥ 12, there is some combination of blue and red beads that is worth n credits. Clearly state the type of Induction you have used to prove the problem

Answer 1

Answer:

"a" is showing the number of blue beads

"b" represents the number of red beads in a combination

let "n" show the number of credits.

We get the following equation:

n = 3a + 7b.

Now, we want to prove that for all n ≥ 12, there is some combination of blue and red beads that is worth n credits, there are a, b in N such that:

n = 3a + 7b

Hence we will prove this by induction.

Base Cases: n = 12.

Applying the formula clearly 12 = 3*4+7*0.

n = 13

Applying the formula clearly 13 = 3*2+7*1.

n = 14.

Applying the formula clearly 14 = 3*0+7*2.

Induction Step: Assume that for all 12<=k<n there are x, y in N such that

k = 3x + 7y. We will now prove that there are a, b in N such that n = 3a + 7b.

By the induction hypothesis we know that there are x, y in N such that n-3 = 3x + 7y.

Hence n = n - 3 + 3 = 3x + 7y + 3 = 3(x + 1) + 7y, so choosing a = x + 1

and b = y we see that n = 3a + 7b.

Therefore by induction, the claim is true for all n ≥ 12