Thread: help with induction

Find the smallest number m such that postage of exactly n cents can be made using only 3-cent and 8-cent stamps for all n>=m. Prove your claim using simple and complete induction.

I am confused about this question.
If n is the amount of cents made from the two stamps, wouldn't the smallest m be 0 for all n?

Originally Posted by Sneaky

wouldn't the smallest m be 0

No. How you gonna make 1 cent postage with only 3 and 8 cent stamps?

Be clear of the problem. On first glance, I take the problem to be:

Find the least natural number m such that
for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k.

I was also wondering if this question implies that 0 amounts of a stamp can be used?

Also can you explain your reasoning and this question more, for some reason I am not understanding what the question is asking.

When you say
Can't be 14 (no way to get 3j+8k=14).

Then what about:
3(2)+8(1)=14


And wouldn't m be 11, because the smallest n would be 11 since 1 of 3-cent stamp and 1 of 8-cent stamp, this is assuming you can't have 0 amounts of a stamp.

Originally Posted by Sneaky

I was also wondering if this question implies that 0 amounts of a stamp can be used?

Doesn't matter.

what about:

Originally Posted by Sneaky

When you say
Can't be 14 (no way to get 3j+8k=14).

Then what about:
3(2)+8(1)=14


And wouldn't m be 11, because the smallest n would be 11 since 1 of 3-cent stamp and 1 of 8-cent stamp, this is assuming you can't have 0 amounts of a stamp.

Originally Posted by Sneaky

When you say
Can't be 14 (no way to get 3j+8k=14).

I was wrong. I edited it out.

Darn, forget my post I just posted here. I got mixed up myself.

11 doesn't work. There is no j and k such that 3j+8k=13.

ohh so what this question is asking is that:

for all n >= to a certain number, m, there is a perfect combination of 3 and 8 cent stamps?

So how would I go about solving this problem?

What the question is asking is this:

Find the least natural number m such that for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k. And prove that the m you found is indeed the the least natural number m such that for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k.

One way is to go through the natural numbers eliminating them one by one as they fail to be such an m. Then when you get to one that seems to work, prove that it does.

suppose we could make 3 consecutive integers in such a fashion: m, m+1, and m+2.

adding a 3-cent stamp to each configuration would then give m+3, m+4, and m+5.

can you see that we can use induction to show we can make all integers ≥ m this way?

what are the smallest 3 consecutive integers we can make?

i think i know it


14 = 2(3)+1(8)
15 = 5(3)+0(8)
16 = 0(3)+2(8)
17 = 3(3)+1(8)
18 = 6(3)+0(8)
19 = 1(3)+2(8)
20 = 4(3)+1(8)
21 = 7(3)+0(8)
22 = 2(3)+2(8)
23 = 5(3)+1(8)
24 = 8(3)+0(8)
25 = 3(3)+2(8)
26 = 6(3)+1(8)
(i also see a pattern where the multiplier for 8 is 1,0,2,1,0,2... and for 3 its, +3,-5,+3, +3,-5,+3, +3,-5,+3, +3,-5,+3)

with a combination of 3 and 8 cent stamps to get one more, you can either remove a 8-cent stamp and put in 3 3-cent stamps or remove 5 3-cent stamps and put in 2 8-cent stamps. Therefore the smallest number is 14.

Is this the right way to get 14, or do I have to show some formal way, since here i am just assuming it?




so
if i set it up like
3j+8k = n
then
3j'+8k'=n+1
then two cases:

case 1:
if k>=1
remove a 8-cent stamp and put in 3 3-cent stamps
so
k'=k-1
j'=j+3
then k' and j' are in N
and
3j'+8k'=n+1

case 2:
if k=0

3j>=14
j>=14/3
j>=5

remove 5 3-cent stamps and put in 2 8-cent stamps
so
k'=k+2
j'=j-5
then k' and j' are in N
and
3j'+8k'=n+1

Is this is basic informal correct method?