Finding all possible values

How many values can $7a+13b$ take, if $a,b\in\mathbb{Z}_{\geq 0} \text{ and } 0 \leq a+b \leq 100$ ?

Try to generalize. How many values can $m\cdot a+n\cdot b$ take, if $a,b\in\mathbb{Z}_{\geq 0},\text{ }m,n\in\mathbb{Z} \text{ and } 0 \leq a+b \leq k$ , for some $k\in\mathbb{N}$ ?

#NumberTheory #MathProblem #Math

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.

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
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"

Math	Appears 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}$

Comments

This is a very interesting problem, and it's not immediately clear how to proceed, or what the answer is.

I've recently created a problem which uses this as the main approach (and just so happened to chance upon your discussion).

Calvin Lin Staff - 7 years, 11 months ago

Is it about counting the terms when a polynomial is raised to a certain power? Because that's where I got the idea from.

Tim Vermeulen - 7 years, 11 months ago

That's one place where this can arise.

The original place that I was looking at, was in modifying the Chicken Mcnugget Theorem (see Strong Induction), by adding the restriction that we are only allowed to buy a certain number of boxes so as to not appear like a glutton.

These two are related through the theory of generating functions.

Calvin Lin Staff - 7 years, 11 months ago

@Calvin Lin – One BIMC problem this year...................

Zi Song Yeoh - 7 years, 11 months ago

Great Problem! One approach is to note that the first 12 multiples of 7 (7,14,21,...) form a complete set of residues mod 13. Adding up to 100 multiples of 13 gives most numbers up to 1300 (everything except 1,2,3,...71). Subtracting these numbers we have made from 1007+10013=2000 gives everything apart from 1,2,3,...71,1999,1998,...1929. It's possible to show these numbers are impossible, and to generalise the argument. For a and b coprime a result of Sylvester gives (a-1)(b-1) impossible numbers.

David Vaccaro - 7 years, 11 months ago

You might want to read the question again. Note that you can't get above 1300 as $a+b \leq 100$ .

Note: You need to type your equations in the latex syntax using the brackets \ ( \ ). Otherwise, $*$ gets interpreted in Markdown, which would italize your equations instead. I believe that your line 1007+10013 should have been $100 * 7 + 100*13$ instead.

Calvin Lin Staff - 7 years, 11 months ago

Yep. Sorry I thought it was 0<= a,b <= 100 rather then 0<=a+b<=100

David Vaccaro - 7 years, 11 months ago

I don't completely get what your saying. Where does $71$ come from?

By the way, check your formatting, some things went wrong.

Tim Vermeulen - 7 years, 11 months ago

71 is the largest number which can not be made from a combination of 7 and 13.

I misread your question and thought condition was that a and b were both less than or equal to 100, rather than the sum. I found all the values between 0 and 100(7+13) which were not possible.

If the sum a+b is bounded (0<=a+b<=100) then the number of possible values is just 101+100+99+...89=1235 corresponding to the number of the 13s (the larger value) it is possible to put with 0,1,...12 lots of 7s. (You never need 13 or more lots of 7 because it would be better to convert them to 7 lots of 13.) All of these are different because the multiples of 7 will have different residues mod 13.

This should generalize for general k to give (k+1)+k+....(k+2-a) possible values

David Vaccaro - 7 years, 11 months ago

@David Vaccaro – That solutions seems correct, I solved it differently: for every $0 \leq b \leq 100$ , there are $13$ possible values for $a$ , but I need to subtract $12+11+\dots + 1$ because for $b=100$ I counted $13$ values for $a$ while only $a=0$ is valid due to the fact that $a+b \leq 100$ . Similarly, for $b=99$ , $13$ values for $a$ were counted while only 2 are valid, etcetera. So, the answer is $13 \cdot 101 - (12 + 11 + \dots + 1) = 1235$ .

Generalization: denote $\max(m,n)$ by $q$ . The total values $m \cdot a + n \cdot b$ can take if $a+b \leq k$ then is

$\begin{aligned} q \cdot (k+1) - \left( (q-1) + (q-2) + \dots + 1 \right) &= q \cdot (k+1) - \frac{q(q-1)}{2}\\ &= q \left( (k+1) - \frac{q-1}{2} \right)\\ &= \frac{q(-q+2k+3)}{2}. \end{aligned}$

And indeed:

$\begin{aligned} (k+1) + k + \dots + (k+2-a) &= \frac{(k+1)(k+2)}{2} - \frac{(k+2-a)(k+1-a)}{2}\\ &= \frac{(k^2+3k+2) - (k^2+3k+2-2qk-3q+q^2)}{2}\\ &= \frac{-q^2+2qk+3q}{2}\\ &= \frac{q(-q+2k+3)}{2}. \end{aligned}$

Tim Vermeulen - 7 years, 11 months ago

@Tim Vermeulen – That looks good- my a is your q so we agree.

Of course we need to also consider case when m and n are not coprime, where we just need to cancel a common factor.

Also if k is smaller than q we just have k(k+1)/2 possible values, since in my way of thinking of things we can have any of the k possible amounts of m without redundancy.

David Vaccaro - 7 years, 11 months ago

@David Vaccaro – Yes, I had thought about the fact that they need to be coprime, but I forgot to mention it. I had not thought about your last point, but that seems correct.

What I think is much harder, is what the answer would be with more than 2 terms: for instance, $7a + 13b + 29c$ with $a+b+c \leq 100$ . I can't find any way to even begin solving this.

Tim Vermeulen - 7 years, 11 months ago

Math	Appears 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}$