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.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold

- bulleted - list

bulleted

list

1. numbered 2. list

numbered

list

Note: you must add a full line of space before and after lists for them to show up correctly

@Sravanth C.
–
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
–
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

@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)

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
–
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)

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?

@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?

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
–
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?

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:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

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

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

$12$ can be expressed in the form $7x + 3y$

I want you to prove that all numbers above-_-

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?@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?

Log in to reply

$3x+7y$ using Chicken Nugget theorem; I am not much familiar with it. :P

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 asLog in to reply

$11$! -_- (if x,y are non- negative)

It is of courseLog in to reply

$3x+7y$ can be expressed by any number above $12$ isn't it?(Or, is it? maybe I'm mistaken)

Then, it's by that theorem that we've proved thatLog in to reply

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.

Log in to reply

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$ 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?

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?

Log in to reply

$12$ is such number, but I wasn't able to prove it. . . Can you please help me?

Yeah, I thought so sir. But taking a second look thought it's quite possible. When I tried by hit and trial I found thatLog in to reply

Log in to reply

Log in to reply

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.

Log in to reply

Well done sir! But, this indeed doesn't prove that all numbers can be

surelyexpressed as $3x+8y$. Anyway it was a very good attempt sir!Log in to reply

What is it lacking?

Log in to reply

Log in to reply

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

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

Log in to reply

Log in to reply

$15=7\times0+3\times5$

Why not?Log in to reply

Log in to reply