# help with induction

Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last
• May 23rd 2011, 10:30 AM
Sneaky
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.

If n is the amount of cents made from the two stamps, wouldn't the smallest m be 0 for all n?
• May 23rd 2011, 10:59 AM
MoeBlee
Quote:

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.
• May 23rd 2011, 11:04 AM
Sneaky
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.
• May 23rd 2011, 11:16 AM
Sneaky
When you say
Can't be 14 (no way to get 3j+8k=14).

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.
• May 23rd 2011, 11:17 AM
MoeBlee
Quote:

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

Doesn't matter.
• May 23rd 2011, 11:18 AM
Sneaky

Quote:

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

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.

• May 23rd 2011, 11:19 AM
MoeBlee
Quote:

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.
• May 23rd 2011, 11:20 AM
MoeBlee
Darn, forget my post I just posted here. I got mixed up myself.
• May 23rd 2011, 11:27 AM
MoeBlee
11 doesn't work. There is no j and k such that 3j+8k=13.
• May 23rd 2011, 11:32 AM
Sneaky
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?
• May 23rd 2011, 11:38 AM
Sneaky
So how would I go about solving this problem?
• May 23rd 2011, 12:08 PM
MoeBlee
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.
• May 23rd 2011, 12:09 PM
MoeBlee
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.
• May 23rd 2011, 01:35 PM
Deveno
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?
• May 23rd 2011, 01:36 PM
Sneaky
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?
Show 40 post(s) from this thread on one page
Page 1 of 4 1234 Last