Inductive reasoning!

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

  • xx may be equal to yy and,
  • xx and yy are positive integers.

Note by Sravanth Chebrolu
4 years, 3 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

The answer is trivial by Postage Stamp Problem / Chicken McNugget Theorem.

Pi Han Goh - 4 years, 3 months ago

Log in to reply

Yeah! I had thought of this. But I was not that sure to post it :)

Nihar Mahajan - 4 years, 3 months ago

Log in to reply

Same here! BTW, did you think of anyway to prove it? If yes do share it.

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu I am not able to understand what exactly you want us to prove now?

Nihar Mahajan - 4 years, 3 months ago

Log in to reply

@Nihar Mahajan I want you to prove that all numbers above 1212 can be expressed in the form 7x+3y7x + 3y

-_-

Sravanth Chebrolu - 4 years, 3 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 - 4 years, 3 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+7y3x+7y using Chicken Nugget theorem; I am not much familiar with it. :P

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu It is of course 1111! -_- (if x,y are non- negative)

Nihar Mahajan - 4 years, 3 months ago

Log in to reply

@Nihar Mahajan Then, it's by that theorem that we've proved that 3x+7y3x+7y can be expressed by any number above 1212 isn't it?(Or, is it? maybe I'm mistaken)

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu Chicken-Mcnugget theorem states:

Let mm and nn be positive coprime integers. Then the greatest integer that cannot be written in the form am+bnam + bn for nonnegative integers aa and bb (called the Frobenius number) is mnmnmn-m-n.

Here m,n=(7,3)m,n=(7,3) and substitution gives us answer as 1111. 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 - 4 years, 3 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 - 4 years, 3 months ago

Log in to reply

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\$7 and $3\$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 - 4 years, 3 months ago

Log in to reply

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

That is an impossible scenario isn't it?

Pi Han Goh - 4 years, 3 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 1212 is such number, but I wasn't able to prove it. . . Can you please help me?

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu I've already given you the answer above.

Pi Han Goh - 4 years, 3 months ago

Log in to reply

@Pi Han Goh So, you mean it's impossible to prove it?

Sravanth Chebrolu - 4 years, 3 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 - 4 years, 3 months ago

Log in to reply

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

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

Now, any n>12n>12 can be formed. Say we want 2626. Then we take the pair that gave us 1616 and we add one to both xx and yy: 7(1+1)+3(3+1)=267(1+1)+3(3+1)=26. So all we have done is add 1010 to our 1616. If we want to add 4040 to an element of SS, we just add 44 to each x,yx,y in the appropriate element of SS*. In general, we can add any multiple of 1010 by simply adding nn to each xx and yy of the appropriate pair. Thus we can express any n>12n>12 as 7x+3y7x+3y for positive xx and yy.

It's not the most elegant proof, but it works. I'd love to see a more elegant proof.

Ryan Tamburrino - 4 years, 3 months ago

Log in to reply

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

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

What is it lacking?

Ryan Tamburrino - 4 years, 3 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 - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu Ah! Chicken McNugget Theorem! How could I forget. There you go.

Ryan Tamburrino - 4 years, 3 months ago

Log in to reply

Are xx and yy non-negative integers?

Ryan Tamburrino - 4 years, 3 months ago

Log in to reply

Yeah. Thanks for asking! I've modified it. ¨\huge\ddot\smile

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

If they are, 1515 is not possible. Do you mean that they are integers (positive or negative)?

Andrei Golovanov - 4 years, 3 months ago

Log in to reply

@Andrei Golovanov Why not? 15=7×0+3×515=7\times0+3\times5

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

@Sravanth Chebrolu Oh, sorry! I forgot about 0.

Andrei Golovanov - 4 years, 3 months ago

Log in to reply

@Andrei Golovanov Non-negative includes 0.

Ryan Tamburrino - 4 years, 3 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 - 4 years, 3 months ago

Log in to reply

@Calvin Lin sir and @Nihar Mahajan. Can you post your proofs? Please. . .

Sravanth Chebrolu - 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...