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}\)?

No vote yet

10 votes

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*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:

TopNewestThis 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).

Log in to reply

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

Log in to reply

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.

Log in to reply

Log in to reply

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 100

7+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.Log in to reply

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 100

7+10013 should have been \( 100 * 7 + 100*13 \) instead.Log in to reply

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

Log in to reply

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

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

Log in to reply

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

Log in to reply

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{align*} 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{align*} \]

And indeed:

\[ \begin{align*} (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{align*} \]

Log in to reply

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.

Log in to reply

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.

Log in to reply