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

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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

-_-

- 4 years, 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?

- 4 years, 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

- 4 years, 3 months ago

It is of course $11$! -_- (if x,y are non- negative)

- 4 years, 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)

- 4 years, 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.

- 4 years, 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)

- 4 years, 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?

- 4 years, 3 months ago

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

That is an impossible scenario isn't it?

- 4 years, 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?

- 4 years, 3 months ago

- 4 years, 3 months ago

So, you mean it's impossible to prove it?

- 4 years, 3 months ago

It's impossible to prove it because there is no maximum value. Please read the Wiki page.

- 4 years, 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.

- 4 years, 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!

- 4 years, 3 months ago

What is it lacking?

- 4 years, 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?

- 4 years, 3 months ago

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

- 4 years, 3 months ago

Are $x$ and $y$ non-negative integers?

- 4 years, 3 months ago

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

- 4 years, 3 months ago

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

- 4 years, 3 months ago

Why not? $15=7\times0+3\times5$

- 4 years, 3 months ago

Oh, sorry! I forgot about 0.

- 4 years, 3 months ago

Non-negative includes 0.

- 4 years, 3 months ago

@Sharky Kesa, @Daniel Liu, @Michael Mendrin sir, @Azhaghu Roopesh M sir can you post your own proofs?

- 4 years, 3 months ago

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

- 4 years, 3 months ago