×

# Inductive reasoning!

Prove that all numbers above 12 can be expressed in the form $$7x + 3y$$ by any method. Preferably by mathematical induction.

• $$x$$ may be equal to $$y$$ and,
• $$x$$ and $$y$$ are positive integers.

Note by Sravanth Chebrolu
1 year, 3 months ago

Sort by:

The answer is trivial by Postage Stamp Problem / Chicken McNugget Theorem. · 1 year, 3 months ago

Yeah! I had thought of this. But I was not that sure to post it :) · 1 year, 3 months ago

Same here! BTW, did you think of anyway to prove it? If yes do share it. · 1 year, 3 months ago

I am not able to understand what exactly you want us to prove now? · 1 year, 3 months ago

I want you to prove that all numbers above $$12$$ can be expressed in the form $$7x + 3y$$

-_- · 1 year, 3 months ago

Do you know what Chicken-Nugget theorem is? Isn't it has become obvious now? What do you think you need to prove now? @Sravanth Chebrolu

@Pi Han Goh Do we require more proof? It seems Chicken Nugget does all the work.

Oh Wait! Sravanth do you want us to prove Chicken Nugget theorem? · 1 year, 3 months ago

No! Okay, you say it's become obvious that no such minimum number exists. Well then, why don't you tell me maximum the number which cannot be expressed as $$3x+7y$$ using Chicken Nugget theorem; I am not much familiar with it. :P · 1 year, 3 months ago

It is of course $$11$$! -_- (if x,y are non- negative) · 1 year, 3 months ago

Then, it's by that theorem that we've proved that $$3x+7y$$ can be expressed by any number above $$12$$ isn't it?(Or, is it? maybe I'm mistaken) · 1 year, 3 months ago

Chicken-Mcnugget theorem states:

Let $$m$$ and $$n$$ be positive coprime integers. Then the greatest integer that cannot be written in the form $$am + bn$$ for nonnegative integers $$a$$ and $$b$$ (called the Frobenius number) is $$mn-m-n$$.

Here $$m,n=(7,3)$$ and substitution gives us answer as $$11$$. This is a universally accepted theorem. If you have any problem with this , do tell me. It seems you didn't know this theorem at all. · 1 year, 3 months ago

Not until today. Anyways, thanks for co-operating with me(of course thanks for teaching me a new theorem!) . I think I should leave now, bye!(I heard rumors that you're active on nights too! So, enjoy your learning. . . . :P) · 1 year, 3 months ago

Yes sir. I thought of it before posting this note. Actually the question was "You are in a world where, there are only denominations of $$7$$ and $$3$$. What is the minimum number, above which you can obtain all possible values?"

So, what do you think sir? Can't there be an inductive proof for this? · 1 year, 3 months ago

"What is the minimum number, above which you can obtain all possible values?"

That is an impossible scenario isn't it? · 1 year, 3 months ago

Yeah, I thought so sir. But taking a second look thought it's quite possible. When I tried by hit and trial I found that $$12$$ is such number, but I wasn't able to prove it. . . Can you please help me? · 1 year, 3 months ago

I've already given you the answer above. · 1 year, 3 months ago

So, you mean it's impossible to prove it? · 1 year, 3 months ago

It's impossible to prove it because there is no maximum value. Please read the Wiki page. · 1 year, 3 months ago

I think the most intuitive way to go about this is by expressing the $$10$$ numbers after $$12$$ (as a set, $$S=\{13,14,15,...,22\}$$). Once that is shown, the proof is essentially over, because we can just add $$10$$ to any number in $$S$$, which will let us form any $$n>12$$ as $$7x+3y$$, with $$x$$ and $$y$$ being non-negative integers.

Clearly, setting $$x=0$$ allows us to attain any multiple of $$3$$, which in $$S$$ will give us $$15,18,$$ and $$21$$. Similarly, we can set $$y=0$$ to attain any multiple of $$7$$, which in $$S$$ will give us $$14$$ and $$21$$. So, now we have the in-between cases of $$x,y \neq 0$$. We can pluck the right $$x$$ and $$y$$ rather easily for these. $13 = 7(1)+3(2)$ $16= 7(1)+3(3)$ $17 = 7(2)+3(1)$ $19=7(1)+3(4)$ $20=7(2)+3(2)$ $22=7(1)+3(5)$ So, now we have a corresponding set of pairs $$(x,y)$$ which give us each number in $$S$$, and we'll call this set $$S*=\{(x_{13},y_{13}),(x_{14},y_{14}), ... , (x_{22},y_{22})\}$$.

Now, any $$n>12$$ can be formed. Say we want $$26$$. Then we take the pair that gave us $$16$$ and we add one to both $$x$$ and $$y$$: $$7(1+1)+3(3+1)=26$$. So all we have done is add $$10$$ to our $$16$$. If we want to add $$40$$ to an element of $$S$$, we just add $$4$$ to each $$x,y$$ in the appropriate element of $$S*$$. In general, we can add any multiple of $$10$$ by simply adding $$n$$ to each $$x$$ and $$y$$ of the appropriate pair. Thus we can express any $$n>12$$ as $$7x+3y$$ for positive $$x$$ and $$y$$.

It's not the most elegant proof, but it works. I'd love to see a more elegant proof. · 1 year, 3 months ago

Well done sir! But, this indeed doesn't prove that all numbers can be surely expressed as $$3x+8y$$. Anyway it was a very good attempt sir! · 1 year, 3 months ago

What is it lacking? · 1 year, 3 months ago

There is no proof that combining the results will give surely give out all the numbers. But, that is not a big issue sir, you've done very well. Can you try it using induction? · 1 year, 3 months ago

Ah! Chicken McNugget Theorem! How could I forget. There you go. · 1 year, 3 months ago

@Sharky Kesa, @Daniel Liu, @Michael Mendrin sir, @Azhaghu Roopesh M sir can you post your own proofs? · 1 year, 3 months ago

Comment deleted Jul 03, 2015

Yes. They must be integers. · 1 year, 3 months ago

Are $$x$$ and $$y$$ non-negative integers? · 1 year, 3 months ago

Yeah. Thanks for asking! I've modified it. $$\huge\ddot\smile$$ · 1 year, 3 months ago

If they are, $$15$$ is not possible. Do you mean that they are integers (positive or negative)? · 1 year, 3 months ago

Non-negative includes 0. · 1 year, 3 months ago

Why not? $$15=7\times0+3\times5$$ · 1 year, 3 months ago

Oh, sorry! I forgot about 0. · 1 year, 3 months ago