How many ways to write $2010$?

Let $N$ be the number of ways to write $2010$ in the form $2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $a_i$'s are integers, and $0 \le a_i \le 99$. An example of such a representation is $1\cdot10^3 + 3\cdot10^2 + 67\cdot10^1 + 40\cdot10^0$. Find $N$.

I picked the biggest $a_1$ so: $a_1 = 2$, there are only two ways to form $2010$.

Take $a_1 = 1$ now. This opens up to a lot of possibilities.

Specific Casework should work:

Cases 1-1: $a_2 = 10$, then possibilities are: $a_1 = 1, a_0 = 0$ or $a_1 = 0, a_0 = 10$

Actually, I think a number-theoretic way is easier.

But still.

Case 1: $a_1 = 1$ then we must solve:

$100x + 10y + z = 1010$.

Since $0 \le x \le 10$, we can casework $x$ so that:

Case 1-1:$x = 0$. So that:

$10y + z = 1010 \implies z \equiv 0 \pmod{10}, z = 10k$ and $y = 101 - k$.

Hence, $(0, 101 - k, 10k)$. $\min{k} = 0$ and we need to find the max of $k$. We must have, $101 - k \le 99$ and $10k \le 99$. This suggests, $k \le 9$.

Cases 1-2: $x=1$. So that:

$10y + z = 910 \implies z \equiv 0 \pmod{10}$ Again, $z = 10k$ and $y = 91 - k$. Giving a set of $(1, 91 - k, 10k)$.Here again, $\min{k} = 0$ and $10k \le 99$ so $k \le 9$.

I am conjecturing that since we are always increasing $x$ values, the value on the RHS will always be divisible by $10$.

$x = 9$ so that:

$10y + z = 110 \implies z = 10k$ and $y = 11 - k$, which again there are $9$ values.

Except if $x=10$ then there is: $10y + z = 10$ then $z = 10k$ and $y = 1 - k$. Then $k$ must be $1$.

So there are: $10(9) + 1 + 2 = 93$ solutions total.

This is just an attempt!

Bump: anybody have anything?

The generating function for these representations is

$$\frac{x^{100\cdot1000}-1}{x^{1000}-1}\cdot\frac{x^{100\cdot100}-1}{x^{100}-1}\cdot\frac{x^{100\cdot10}-1}{x^{10}-1}\cdot\frac{x^{100}-1}{x-1}=\frac{x^{100000}-1}{x^{10}-1}\cdot\frac{x^{10000}-1}{x-1}\;,$$

which is also the generating function for representations of the form $b_1\cdot10+b_0$ with $0\le b_i\le9999$. Since this latter restriction is irrelevant for representations of $2010$, we are simply looking for the number of ways to represent $2010$ by tens and ones. We can have anything from $0$ to $201$ tens, so the number of such representations is $202$.

In response to Calvin Lin's answer: The cancellation in the generating functions corresponds to a bijection between the two forms of representation, with $b_1=100a_3+a_1$ and $b_0=100a_2+a_0$.

• Interesting approach! Sep 2 '15 at 20:33
• (+1) I am particularly interested here, how did you find that generating function? Sep 3 '15 at 16:13
• @Amad27: The generating function for representations by thousands is $$1+x^{1000}+x^{2\cdot1000}+\cdots=\frac1{1-x^{1000}}\;.$$ If there is a limitation that we can only use up to $99$ thousands, we have to truncate the generating function: $$1+x^{1000}+x^{2\cdot1000}+\cdots+x^{99\cdot1000}=\frac{1-x^{100\cdot1000}}{1-x^{1000}}\;.$$ See e.g. en.wikipedia.org/wiki/Geometric_progression#Derivation. Sep 3 '15 at 16:18
• Yes, but why are we using the "thousands?" Sep 3 '15 at 16:32
• @Amad27: Because the problem says so: "write $2010$ in the form $2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$" -- i.e., represent $2010$ in terms of thousands, hundreds, tens and ones. Sep 3 '15 at 16:34

It's easier to start from the other end. We observe first that $a_0$ can be any multiple of $10$ from $0$ through $90$. There are, of course, ten such values.

Then $a_1$ can be any one- or two-digit value equivalent to $11-(a_0/10) \bmod 10$. Again, there are ten such values.

The choices of $a_2$ are much more limited by the fact that the target sum is only $2010$. In which cases are there two different values? In which cases are there three?

Once $a_0, a_1, a_2$ have been decided, there is only one usable value of $a_3$.

Here's the bijection approach, which is hinted at by Joriki's solution.

Let $a_i = 10 b_i + c_i$, where $0 \leq c_i \leq 9$, $0 \leq b_i \leq 9$.

Then, we have

$$2010 = 10 (1000b_3 + 100 b_2 + 10b_1 + b_0) + ( 1000 c_3 + 100 c_2 + 10 c_1 + c_0)$$

Thus, given any representation of $2010 = 10 B + C$, there is a unique corresponding $b_i, c_i$ (clearly the digits of B and C) that we can create, and vice versa. This establishes the bijection. Hence, the answer is 202.

• Nice interpretatino of Joriki's approach! Sep 6 '15 at 21:42
• The bijection that I had in mind was $2010=10(100a_3+a_1)+(100a_2+a_0)$. I think that corresponds more closely with the cancellation of factors in the generating functions? Sep 7 '15 at 6:16
• @joriki, the coefficient $A(k)$ is the number of ways. So if for example I am finding how many ways to use the $1000$ it would be $A(1000)x^{1000} = 3x^{1000}$ right ? But you have something way different? Sep 7 '15 at 9:26
• @joriki, I know how to use generating functions, but I just don't understand what you were doing Sep 7 '15 at 11:57

In short we have to calculate the number of integer solutions of the Diophantine equation $$1000x+100y+10z+w=2010$$ with the conditions $0\leq x,y,z,w \leq 99$. We have $0\leq x\leq 2$ which gives the three equations $$(1)……100y+10z+w=2010$$ $$(2)……100y+10z+w=1010$$ $$(3)……100y+10z+w=10$$ The equation (3) gives just two solutions $(2,0,1,0)$ and $(2,0,0,10)$.

It remains to compute solutions of (1) and (2). We have for $w$ only ten possible values $w=0,10,20,30,40,50,60,70,80,90$ which gives for (1) the ten equations $(1’)……100y+10z=2010,2000,1990,1980,1970,1960,1950,1940,1930,1920$ that is $$(1’)……10y+z=201,200,199,198,197,196,195,194,193,192$$ And for (2) the ten equations $(2’)……100y+10z=1010,1000,990,980,970,960,950,940,930,920$ that is $$(2’)………10y+z=101,100,99,98,97,96,95,94,93,92$$

The first equation of (1’), $10y+z=201$, gives for $z$ only the ten possible values $1,11,21,31,41,51,61,71,81,91$ with corresponding unique values of y respectively equal to $20,19,18,17,16,15,14,13,12,11$ so ten solutions.

The second one,$10y+z=200$ makes $z=0,10,20,30,40,50,60,70,80,90$ which gives for $y$ the values $20,19,18,17,16,15,14,13,12,11$ so ten solutions.

Pursuing, $10y+z=199$ makes $z=9,19,29,……….,99$ which give ten solutions and so are for the remaining values $198,197,196,195,194,193,192$.

Thus the ten equations (1’) give one hundred solutions. The same procedure goes for ten equations (2’) which give then one hundred solutions.

Finally we have $2+100+100=202$ solutions.

Here's a solution that's not particularly elegant but gives the right answer (checked by brute force).

First express each coefficient uniquely as $b_i\cdot 10 + a_i$.

$2010 = b_3 \cdot 10^4 + a_3 \cdot 10^3 + b_2 \cdot 10^3 + a_2 \cdot 10^2 + b_1 \cdot 10^2 + a_1 \cdot 10 + b_0 \cdot 10 + a_0$.

We must have $b_3 = 0, a_0 = 0$, so

$201 = (a_3 + b_2) \cdot 10^2 + (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$.

Each coefficient is in $0, \ldots, 18$.

If $a_3 + b_2 = 1$, then $101 = (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$. We have $a_2 + b_1 = 9, a_1 + b_0 = 11$ or $a_2 + b_1 = 10, a_1 + b_0 = 1$, this gives $2 \cdot (10 \cdot 8 + 9 \cdot 2) = 196$ solutions.

If $a_3 + b_2 = 2$, then $1 = (a_2 + b_1) \cdot 10^1 + (a_1 + b_0)$. We have $a_2 + b_1 = 0, a_1 + b_0 = 1$, this gives $3 \cdot 2 = 6$ solutions.

So together we have 202 solutions.

• I get the same result that you do, so I think we're on the right track! Sep 2 '15 at 20:25
• Good to know you got the same result! Sep 2 '15 at 20:28
• On the right track at the start, but your cases become complicated. See my solution. Sep 6 '15 at 18:02