Waste less time on Facebook — follow Brilliant.
×

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, 6 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

The answer is trivial by Postage Stamp Problem / Chicken McNugget Theorem. Pi Han Goh · 1 year, 6 months ago

Log in to reply

@Pi Han Goh Yeah! I had thought of this. But I was not that sure to post it :) Nihar Mahajan · 1 year, 6 months ago

Log in to reply

@Nihar Mahajan Same here! BTW, did you think of anyway to prove it? If yes do share it. Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu I am not able to understand what exactly you want us to prove now? Nihar Mahajan · 1 year, 6 months ago

Log in to reply

@Nihar Mahajan I want you to prove that all numbers above \(12\) can be expressed in the form \(7x + 3y\)

-_- Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu 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? Nihar Mahajan · 1 year, 6 months ago

Log in to reply

@Nihar Mahajan 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 Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu It is of course \(11\)! -_- (if x,y are non- negative) Nihar Mahajan · 1 year, 6 months ago

Log in to reply

@Nihar Mahajan 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) Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu 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. Nihar Mahajan · 1 year, 6 months ago

Log in to reply

@Nihar Mahajan 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) Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Pi Han Goh 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? Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

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

That is an impossible scenario isn't it? Pi Han Goh · 1 year, 6 months ago

Log in to reply

@Pi Han Goh 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? Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu I've already given you the answer above. Pi Han Goh · 1 year, 6 months ago

Log in to reply

@Pi Han Goh So, you mean it's impossible to prove it? Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu It's impossible to prove it because there is no maximum value. Please read the Wiki page. Pi Han Goh · 1 year, 6 months ago

Log in to reply

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. Ryan Tamburrino · 1 year, 6 months ago

Log in to reply

@Ryan Tamburrino 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! Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu What is it lacking? Ryan Tamburrino · 1 year, 6 months ago

Log in to reply

@Ryan Tamburrino 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? Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu Ah! Chicken McNugget Theorem! How could I forget. There you go. Ryan Tamburrino · 1 year, 6 months ago

Log in to reply

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

Log in to reply

Comment deleted Jul 03, 2015

Log in to reply

@Andrei Golovanov Yes. They must be integers. Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

Are \(x\) and \(y\) non-negative integers? Ryan Tamburrino · 1 year, 6 months ago

Log in to reply

@Ryan Tamburrino Yeah. Thanks for asking! I've modified it. \(\huge\ddot\smile\) Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu If they are, \(15\) is not possible. Do you mean that they are integers (positive or negative)? Andrei Golovanov · 1 year, 6 months ago

Log in to reply

@Andrei Golovanov Non-negative includes 0. Ryan Tamburrino · 1 year, 6 months ago

Log in to reply

@Andrei Golovanov Why not? \(15=7\times0+3\times5\) Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

@Sravanth Chebrolu Oh, sorry! I forgot about 0. Andrei Golovanov · 1 year, 6 months ago

Log in to reply

@Calvin Lin sir and @Nihar Mahajan. Can you post your proofs? Please. . . Sravanth Chebrolu · 1 year, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...